Решить 8-головоломку
Я пытаюсь написать решатель для 8-головоломок на C++, но у меня много проблем при этом. В настоящее время программа работает, но для решения головоломки требуется слишком много шагов. Я имею в виду, что иногда он может найти оптимальное решение, иногда требуется 400 шагов для его решения. Мое главное сомнение заключается в следующем. Представьте, что у меня есть эта диаграмма (это всего лишь черновик):
Я использую Manhattan Distance в качестве эвристической функции. После первого шага у нас есть два состояния, где f(n)=5, поэтому я расширил дерево. После расширения я все еще получил два состояния, где f(n)=2. Вот моё сомнение. Нужно ли мне расширять дерево, пока я не получу уникальный самый низкий f(n)?
Заранее спасибо!
3 ответа
Нужно ли еще расширять дерево
Вы не можете решить эту загадку жадно: всегда выбирая ветвь с более низким эвристическим значением, вы не будете каждый раз получать окончательное решение. Таким образом, вы должны держать другие состояния вокруг для возврата. Порядок их расширения, будь то простой BFS или эвристический A*, зависит от вас.
Здесь вы можете найти апплет обработки, который использует алгоритм A*, чтобы найти кратчайший путь от начального состояния до состояния цели. Код в апплете доступен бесплатно.
То, что вы описываете, это не A*, а какой-то вариант восхождения на гору Это не может гарантировать решение, не говоря уже об оптимальном.
Чтобы гарантировать полноту (т. Е. Всегда находить решение, если оно существует), вам необходимо отслеживать альтернативы на каждом этапе, чтобы можно было вернуться к ним, когда они станут более перспективными.
Я написал пост об алгоритме поиска A* и предоставил реализацию задачи N-головоломки, используя A* и расстояние Манхэттена в качестве эвристики: объяснение поиска * и реализация Python N-головоломки