Предварительный результат A*
В настоящее время узнаю о A* алгоритм поиска и использовать его, чтобы найти самое быстрое решение N-Puzzle, Для некоторого случайного начального числа начального начального состояния головоломка может быть неразрешимой, что привело бы к очень долгому времени ожидания, пока алгоритм не выполнит поиск по всему пространству поиска и определит, что не существует решения для данного начального состояния.
Мне было интересно, если есть метод предварительного расчета, является ли A* Алгоритм не сможет избежать такого сценария. Я прочитал немного о том, как это возможно, но не могу найти прямой ответ относительно метода, в котором это можно сделать.
Любое руководство или варианты приветствуются.
2 ответа
Я думаю, что A* не предлагает вам механизма, чтобы узнать, разрешима ли проблема. Специально для N-PuzzleЯ думаю, что это может помочь вам проверить, может ли это быть решено или нет:
http://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/
Кажется, что если вы находитесь в состоянии, в котором у вас инверсия нечетного количества, вы точно знаете, что проблема для этой перестановки невозможна.
В частности, для N-головоломки есть только две возможные четности, поэтому вам просто нужно проверить, какой четности является текущая головоломка.
Существует подробное объяснение того, как сделать это на математическом стеке обмена
Для общих задач A* нет, нет никакого способа предварительно вычислить, разрешим ли граф.