Астароподобный алгоритм с неизвестным конечным состоянием

Question

Звездочка используется для нахождения кратчайшего пути между начальным и конечным узлами в графе. Какой алгоритм используется для решения чего-либо, если целевое состояние не известно конкретно, и вместо этого у нас есть только критерий для целевого состояния?

Например, можно ли решить головоломку судоку с помощью Астароподобного алгоритма? Мы не знаем, как будет выглядеть конечное состояние (какое число где), но мы знаем правила судоку, критерий выигравшего состояния. Поэтому У меня есть начальный узел и только критерии для конечного узла, какой алгоритм использовать?

Answer 1

A * требует графика, функции стоимости для обхода этого графа, эвристики относительно того, находится ли узел в графе ближе к цели, чем другой, и проверки, достигнута ли цель.

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

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

Answer 2

Да, A * может использоваться, когда конкретное состояние цели не может быть идентифицировано. ( Ответ Пита Киркхама подразумевает это, но не особо подчеркивает это.)

Когда конкретное целевое состояние не может быть идентифицировано, иногда сложнее придумать полезную эвристическую нижнюю границу оставшейся стоимости, необходимой для завершения частичного решения, и эффективность A * зависит от выбора эффективной эвристики , Но это не значит, что его нельзя применить. Любая проблема , которая может быть решена на компьютере, может быть решена с помощью поиска в ширину, плюс массив флагов, указывающих, было ли состояние замечено ранее; это то же самое, что и A * с эвристической нижней границей, которая всегда равна нулю. (Конечно, это не самый эффективный алгоритм для решения многих задач.)

Answer 3

Вам не нужно знать точное конечное состояние цели. Все сводится к эвристической функции, когда она возвращает 0, вы можете предположить, что нашли (по крайней мере) одно из действительных конечных состояний.

Так что во время a * вместо проверки, если current_node == target_node, проверьте, возвращает ли current_node.h () 0. Если это так, он должен быть бесконечно близко и / или перекрывать цель / конечное состояние.