Рассчитать минимальные ходы, чтобы решить головоломку

Question

Я нахожусь в процессе создания игры, где пользователю будут представлены 2 набора цветных плиток. Чтобы убедиться, что головоломка разрешима, я начинаю с одного набора, копирую его во второй набор, а затем меняю плитки из одного набора в другой. В настоящее время (и в этом моя проблема) количество свопов определяется уровнем, в котором играет пользователь - 1 своп для уровня 1, 2 свопа для уровня 2 и т. Д. Это то же количество свопов используется в качестве цели в игра. Пользователь должен завершить головоломку, поменяв плитку с одного набора на другой, чтобы два набора соответствовали (по цвету). Порядок плиток в (решаемой пользователем) головоломке не имеет значения, если совпадают 2 набора.

Проблема, с которой я столкнулся, заключается в том, что, поскольку количество перестановок, которые я использовал для создания головоломки, приближается к числу плиток в каждом наборе, головоломка становится легче решать. По сути, вы можете просто перетащить из одного сета в любом порядке, который вам нужен для второго сета, и решить головоломку, оставив множество ходов. Что я собираюсь сделать, так это после того, как я закончу строить головоломку, подсчитать минимальное количество ходов, необходимое для решения головоломки. Опять же, это почти всегда меньше, чем количество свопов, использованных для создания головоломки, особенно когда количество свопов приближается к числу плиток в каждом наборе.

Моя цель - рассчитать сценарий наилучшего случая, а затем дать пользователю «коэффициент выдумки» (т. Е. В 1,2 раза больше минимального количества ходов). Решение головоломки под этим количеством ходов приведет к прохождению уровня.

Небольшая предыстория того, как у меня настроена игра:

Уровни от 1 до 10: 9 плиток в каждом наборе. 5 разноцветных плиток. Уровни с 11 по 20: 12 плиток в каждом наборе. 7 разноцветных плиток. Уровни с 21 по 25: 15 плиток в каждом наборе. 10 разноцветных плиток.

Обмен внутри набора недопустим.

Для каждого уровня будет минимум 2 плитки определенного цвета (по одной на каждый набор в решаемой головоломке).

Есть ли какой-нибудь алгоритм, который кто-нибудь мог бы порекомендовать, чтобы вычислить минимальное количество ходов для решения данной головоломки?

Answer 1

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

В зависимости от размера пространства поиска, простое поиск в ширину был бы возможен и дал бы вам минимальное количество шагов для достижения любого состояния.Фактически, вы можете создавать проблемы и таким способом: вместо того, чтобы делать случайные шаги для достижения состояния и проверки его «расстояния» от начального состояния, просто исследуйте пространство поиска в ширину / уровень-порядок , и выберите состояние на заданном «расстоянии» для вашей головоломки.

Похожие вопросы

• Час пик - решение игры
  • BFS используется для решения Rush Hour с исходным кодом на Java

---

Альтернатива

IF пространство поиска слишком велико для BFS (и я пока не уверен, что так оно и есть), вы можете вместо этого использовать итеративное углубление поиска в глубину .Он экономит пространство, как DFS, но (кумулятивно) упорядочен по уровням, как BFS.Несмотря на то, что узлы посещались бы много раз, они по-прежнему асимптотически идентичны BFS, но требуют гораздо меньшего пространства.

Answer 2

Алгоритм поиска A * . Идея в том, что у вас есть некоторая мера того, насколько близка позиция к решению. A * - это тогда поиск «лучший сначала» в том смысле, что на каждом шаге он рассматривает ходы из наилучшей позиции, найденной на данный момент. Вы должны придумать какую-то меру того, насколько вы близки к решению. (Он не должен быть точным, это просто эвристика, чтобы вести поиск.) На практике он часто работает намного лучше, чем поиск в ширину, потому что он всегда руководствуется вашей функцией оценки близости. Но без понимания вашего описания проблемы трудно сказать. (Эмпирическое правило заключается в том, что если во время выполнения головоломки есть смысл «делать успехи», а не все это внезапно объединяется в конце, то A * - хороший выбор.)

Answer 3

Я не совсем понял загадку из вашего описания, но две общие идеи, часто полезные для решения такого рода головоломок: возврат и ответвление и ограничение .