Горячие Новости

Облако тегов

Вычислена сложность Mario и Donkey Kong

Вычислена сложность Mario и Donkey Kong

Новости инвестиций, игры. Группа ученых из Массачусетского института и Брюссельского университета взялись за исследование степени сложности пяти классических игр, представленных Nintendo. В пятерку вошли, конечно же, серии Donkey Kong, Mario Zelda, Metroid и Pokemon. Результаты были сформированы в статью, однако, на данном этапе ее пока еще не приняли для публикации в журнале с рецензией. Тем не менее, препринт все же удалось найти.


Ученые использовали в своем эксперименте универсальную машину Тьюринга, при помощи нее они формализовали игры. Каждый уровень, практически, во всех указанных играх представляет собой определенный лабиринт с ограничением на размер, в котором предлагается точное количество ловушек. Исследователи задали лишь один вопрос вычислительному устройству, есть ли способ пройти весь лабиринт от начала до конца, если известно состояние ловушек в нем и местоположение врагов.  


Как оказалось, обычная машина Тьюринга может делать выводы и она подошла к поиску ответа легко. Вопрос определения сложности каждого уровня Donkey Kong Country 1-3, Super Mario Bros., Super Mario World,  всех серий Legend of Zelda (кроме, Zelda II), Metroid и Pokemon решался просто – сложность NP. То есть, это означает, что техника может выполнить поставленные задачи за полиномиальное время.

Автор:
Мнение автора может не совпадать с мнением редакции. Если у Вас иное мнение напишите его в комментариях.
Возник вопрос по теме статьи - Задать вопрос »
comments powered by HyperComments
« Предыдущая новость «  » Архив категории «   » Следующая новость »

Рекомендованный брокер №1

Журнал «Биржевой лидер»

Журнал, интересные статьи

Видео

Энциклопедия

wileńskie kościoły oraz pomnik Adama Mickiewicza przy Maironio gatve
Столица Литвы - Вильнюс
Филипп Киркоров
Киркоров Филипп Бедросович
Курс фунта к евро
Курс фунта к евро
Больница
Больница
Попов Александр Павлович
Попов Александр Павлович
Соединенные Штаты Америки карта
Соединенные Штаты Америки