Вычислите минимум перемещается для решения загадки
Я нахожусь в процессе создания игры, где пользователю подарят 2 набора цветных квадратов. Чтобы удостовериться, что загадка разрешима, я запускаю с одного набора, копирую его во второй набор, затем подкачиваю мозаики от одного набора до другого. В настоящее время (и это - то, где моя проблема находится), количество подкачек определяется уровнем, который пользователь играет - 1 подкачка для подкачек уровня 1, 2 для уровня 2 и т.д. Это то же количество подкачек используется в качестве цели в игре. Пользователь должен завершить загадку путем свопинга мозаики от одного набора до другого для создания 2 соответствий наборов (цветом). Порядок мозаик в решенная загадка (пользователя) не имеет значения целый 2 соответствия наборов.
Проблема, которую я имею, состоит в том, что как количество подкачек я раньше генерировал подходы загадки количество мозаик в каждом наборе, загадка становится легче решить. В основном можно просто перетащить от одного набора в любом порядке, в котором Вы нуждаетесь для второго набора и решаете загадку с большим количеством оставленных перемещений. То, что я надеюсь делать, - после того, как я заканчиваю создавать загадку, вычисляю минимальное количество перемещений, требуемых решить загадку. Снова, это - почти всегда меньше, чем количество подкачек раньше создавало загадку, тем более, что количество подкачек приближается к количеству мозаик в каждом наборе.
Моя цель состоит в том, чтобы вычислить лучший вариант развития событий и затем дать пользователю "фактор выдумки" (т.е. 1.2 раза минимальное количество перемещений). Решение загадки в под этим количеством перемещений закончится мимоходом уровень.
Немного фона относительно того, как мне в настоящее время настраивали игру:
Уровни 1 - 10: 9 мозаик в каждом наборе. 5 различных цветных квадратов. Уровни 11 - 20: 12 мозаик в каждом наборе. 7 различных цветных квадратов. Уровни 21 - 25: 15 мозаик в каждом наборе. 10 различных цветных квадратов.
Свопинг в наборе не позволяется.
Для каждого уровня будет по крайней мере 2 мозаики данного цвета (один для каждого набора в решенной загадке).
Есть ли какой-либо тип алгоритма, кто-либо мог рекомендовать вычислить минимальное количество перемещений для решения данной загадки?
3 ответа
Я не совсем понял головоломку из вашего описания, но две общие идеи, часто полезные при решении такого рода головоломок, это обратный путь и ветвление и ограничение.
Алгоритм поиска A*. Идея заключается в том, что у вас есть некоторая мера того, насколько близка позиция к решению. Тогда A* - это поиск "сначала лучшее" в том смысле, что на каждом шаге он рассматривает перемещения от лучшей позиции, найденной на данный момент. Вы сами должны придумать какую-то меру того, насколько близко вы находитесь к решению. (Она не обязательно должна быть точной, это просто эвристика, направляющая поиск). На практике этот метод часто работает гораздо лучше, чем поиск по ширине, поскольку он всегда ориентируется на вашу функцию оценки близости. Но без понимания описания вашей задачи трудно сказать. (Эмпирическое правило гласит, что если есть ощущение "прогресса" во время решения головоломки, а не внезапного объединения в конце, то A* - хороший выбор)
.Минимальное количество ходов для решения головоломки - это, по сути, кратчайший путь от нерешенного состояния к решенному. Ваша игра неявно определяет граф, где вершины - это законные состояния, а ребро между двумя состояниями существует, если есть законный ход, который обеспечивает этот переход.
В зависимости от размера вашего пространства поиска, простой поиск в ширину будет осуществим, и даст вам минимальное количество шагов для достижения любого заданного состояния. На самом деле, вы можете генерировать задачи и таким образом: вместо того, чтобы делать случайные шаги для достижения состояния и проверять его "расстояние" от начального состояния, просто исследуйте пространство поиска в порядке возрастания/уровня, и выберите состояние на заданном "расстоянии" для вашей головоломки.
Похожие вопросы
- Rush Hour - Solving the Game
- BFS используется для решения Rush Hour, с исходным кодом на Java
Альтернатива
ЕСЛИ пространство поиска слишком велико для BFS (а я пока не уверен, что это так), вы можете использовать итеративный углубляющийся поиск в глубину вместо него. Он экономит пространство, как DFS, но (кумулятивно) порядок уровней, как BFS. Даже если узлы будут посещаться много раз, он все равно асимптотически идентичен BFS, но требует гораздо меньше места.