Поиск / удаление из очереди приоритетов STL?

Question

Мне поручено запрограммировать алгоритм поиска A* для задания, которое включает решение "8-головоломки".

Один из шагов алгоритма:

Добавьте все расширенные пути к Q. Если состояние потомка уже находится в Q, оставьте только более короткий путь к состоянию в Q (где Q - это очередь приоритета (PQ)).

Таким образом, мне нужно будет выполнить поиск в PQ, если идентичное состояние существует, но имеет более короткий путь. Если идентичное состояние уже существует, но у него более длинный путь, мне нужно будет удалить это состояние из PQ.

Мне было предложено использовать STL PQ, а не мою собственную реализацию. Мне удалось реализовать другие типы поиска, используя приведенное ниже, чтобы создать Min PQ, который работает по желанию.

auto cmp = [](Puzzle* a, Puzzle* b) { 
    return a->getHCost() > b->getHCost();
};


std::priority_queue<Puzzle*, std::vector<Puzzle*>, decltype(cmp)> Q(cmp);           

---

Как я могу расширить свою реализацию так, чтобы...

• Я могу выполнить поиск методом перебора - перебрать каждый элемент STL PQ?
• Я могу удалить элемент где-нибудь в STL PQ по его индексу? - перетасовка элементов "вверх", если необходимо.

Answer 1

У вас может быть вторичный массив с именем shorttest[], где самый короткий [i] будет самым коротким известным путем к состоянию i. Затем всякий раз, когда вы попадаете в верхнюю часть PQ элемента с состоянием x, вы проверяете самый короткий [x], действительно ли он является самым коротким из найденных, и делаете с ним все, что хотите, иначе удаляете элемент из верхней части PQ.

Однако, учитывая, что состояния взяты из 8-головоломки, вам нужно придумать эффективный способ дать им уникальный идентификационный номер и возможность эффективно вернуть его. За O(1) можно сделать и то, и другое. Я не уверен, стоит ли мне испортить свою личную идею, учитывая, что это, в конце концов, задание, и вы должны взять на себя такой вызов.