В игре Final Fantasy XIII-3 игроку предлагается пара головоломок. Первая представленная головоломка называется Tile Trial. Она представляет игроку сетку плиток, на некоторых из которых есть кристаллы. Цель состоит в том, чтобы собрать все кристаллы и добраться до выхода, наступая на каждую плитку не более одного раза.
Автор http://arxiv.org/pdf/1203.1633v1.pdf заявил, что это задача является NP-трудной, поскольку конкретный случай можно свести к гамильтонову циклу. Я считаю, что это наивное предположение, потому что он разработал особую головоломку, которая, хотя и соответствует правилам игры, просто включает в себя гамильтоновы циклы.
Рассмотрим общий случай: мы можем смоделировать каждую плитку головоломки как вершину графа. Вершина имеет ребро к другой вершине, если две плитки являются смежными. Задача состоит в том, чтобы найти путь от начального тайла к конечному, пройдя все вершины, в которых есть кристаллы, и не посещая ни одну вершину более одного раза.
Я считаю, что это можно свести к TSP (задаче коммивояжера), где нам нужно посетить только подмножество городов. Предположим, что существует обычная задача TSP с n городами. Однако в этой конкретной задаче нам не нужно посещать все n города, а только определенное их подмножество, m, где m‹=n< /эм>. Города в n, но не в m, не нужно посещать, но можно, если путь m1->m2 больше, чем m1->n1->m2 например.
Однако является ли эта «более простая» задача TSP все еще NP-сложной? Кто-нибудь знает лучшую NP-сложную задачу, которую можно было бы использовать в качестве сокращения?
