Я ищу алгоритм для решения "скользящей головоломки", типа головоломки, где у вас есть изображение, разбитое на 16 частей в кадре 4x4
Я ищу алгоритм для решения "скользящей головоломки", типа головоломки, в которой у вас есть изображение, разбитое на 16 частей в кадре 4x4, которое вы пытаетесь собрать для получения зашифрованной стартовой позиции. Эта конкретная головоломка имеет ограничение: строки перемещаются только вправо (и обтекание), весь ряд сразу, а столбцы перемещаются только вверх (и обтекание), весь столбец сразу, оба шага в одну клетку. Математика слишком сложна? Кто-нибудь имеет опыт работы с такой проблемой?
2 ответа
Эта ссылка предоставит вам ответ. Они говорят о различных функциях расстояния, используемых эвристикой. A* проще найти реализации с открытым исходным кодом.
Что касается практически любой проблемы, один "простой / простой" метод для решения такой проблемы состоит в представлении состояний головоломки в виде графа и использовании алгоритма поиска / поиска по графику (DFS,BFS,Dijkstra,A* и т. д.)., Возможно, есть какой-то гениальный специальный алгоритм, который лучше подходит для этой задачи, но вам, вероятно, понадобится много понимания, чтобы стать лучше, чем A* / двунаправленная dijkstra.