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

Question

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

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

Добавьте все расширенные пути к 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 [], где shorttest [i] будет кратчайшим известным путем к состоянию i. Затем, когда вы попадаете в верхнюю часть PQ элемента с состоянием x, вы проверяете самый короткий [x], если он действительно найден самым коротким, и делаете все, что хотите, в противном случае удаляете элемент из верхней части PQ.

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