Каков наиболее эффективный способ найти узел с наименьшим значением для расширения в звезду с помощью эвристики?

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

 a part of psedocode(from wiki)
 while openset is not empty
     x := the node in openset having the lowest f_score[] value
     if x = goal
         return reconstruct_path(came_from, came_from[goal])
     ................................

Итак, как лучше всего найти наименьшее значение f_score? Просто найдите минимальное значение, или мы должны изменить список, когда у нас есть состояние для добавления (отсортируйте список при добавлении состояния), чтобы минимальное значение было на первой позиции.


artificial-intelligence a-star heuristics
person khpn    schedule 05.04.2011    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Поддерживайте кучу.

Имея n элементы, вы можете со временем O(n) превратить их в кучу. Когда они образуют кучу, вы можете добавлять и удалять элементы во времени O(log(n)), и вы можете находить наименьший элемент во времени O(1).

Все, что вам нужно для реализации, - это массив. Корневой узел - это 0, а узлы ниже i находятся в 2*i+1 и 2*i + 2. Условие кучи состоит в том, что каждый узел меньше, чем узлы над ним. Самый маленький - всегда корень. Чтобы добавить элемент, просто вставьте его в массив и дайте ему «упасть» до своего естественного уровня. Чтобы удалить элемент, извлеките корневой элемент, уберите последний элемент из массива, поместите его в корень и позвольте ему «всплыть» в нужное место. (На этапе «всплытия» вы меняете его местами с меньшим из двух дочерних узлов до тех пор, пока под ним не останется меньших дочерних узлов.) Чтобы эффективно создать массив, вы начинаете с среднего элемента и позволяете каждому элементу «пузыриться». вверх". Эта операция выглядит как O(n log(n)), но тщательный анализ показывает, что это всего лишь O(n).

person btilly    schedule 05.04.2011
comment
В этом случае вы используете кучу как приоритетную очередь. Выбранный вами язык может уже предоставлять приоритетную очередь, которая более эффективна, чем самостоятельное ведение двоичной кучи. - person DataWraith; 05.04.2011
comment
@DataWraith Хорошее замечание. Однако @khpn, вероятно, пытается реализовать решатель головоломок 8 в образовательных целях. Написание собственной кучи - это познавательный опыт. - person btilly; 05.04.2011