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

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

Да, A * может использоваться, когда конкретное состояние цели невозможно идентифицировать. (Pete Kirkham's answer подразумевает это, но не подчеркивает его.)

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