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