Используете алгоритм A* для решения скользящей головоломки и N ферзей?

Вам необходимо правильно определить функцию перехода, функцию стоимости и эвристику. Вместо того, чтобы объяснять вам каждый пример, если вы знаете основы A*, вам может быть полезно взглянуть на реализацию проблема N-Queens и N-головоломка библиотека Hipster. Если вы не реализуете свой код на Java, не волнуйтесь, код достаточно ясен, чтобы вы знали, как это сделать.

Надеюсь, мой ответ поможет.

Адриан

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

Таким образом, вы должны решить, какие узлы в этом графе. Для поиска пути в сетке узлы соответствуют позициям в сетке.

Затем вы определяете способ (или несколько) генерации соседей из узла. Думая о графе, это функция от узла к набору его исходящих ребер. Для поиска пути в сетке это то, где вы создаете, возможно, 4 соседние позиции (или 8 или что-то еще). По сути, вы определяете «шаги», которые можно предпринять.

Эти шаги имеют свою цену. Это не G, это просто то, на что вы увеличиваете G. Часто это просто 1. Если снова взять поиск пути в сетке в качестве примера, иногда он определяется как 10 для шага на север/восток/юг/запад и 12 для шага по диагонали (аппроксимирует евклидово расстояние с небольшими целыми числами, с которыми легко работать) .

Затем вы найдете допустимую эвристику (та, которая не завышает фактическую стоимость), которая в некотором роде что такое A*. Без этого поиск был бы тупым, эвристика делает его информированным, и он должен быть допустимым для обеспечения оптимальности. Поиск допустимых эвристик, которые также являются хорошими (то есть достаточно высокими), может быть сложным. Если вы найдете несколько из них, скажем, функции h0 и h1, то вы можете взять max(h0, h1), но, конечно, это поможет только в том случае, если ни одна из них не является явным "победителем" в том смысле, что она всегда не ниже другой ( и, очевидно, еще допустимым). Если есть есть явный победитель, вы, очевидно, можете просто использовать его и забыть о другом.

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