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

Question

Я делаю 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значение?Просто найдите минимальное значение, или мы должны изменить список, когда у нас есть добавляемое состояние (сортировать список, когда мы добавляем это состояние), чтобы минимальное значение было в первой позиции.

Answer 1

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

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

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