8 谜题：排序STL Heap/Priorirty 包含成员变量指针的队列

Question

我正在努力实施最佳优先搜索算法来解决作业的 8 拼图问题。根据要求，它必须使用位于 标准模板库 (STL).[= 中的 (min) 优先级队列或堆 来实现。 16=]

我知道使用任一数据结构来按最佳启发式成本（即最小成本）组织扩展的拼图状态会很有用。

从 3x3 矩阵开始（使用数组实现）

Puzzle *current=new Puzzle(initialState, goalState);

每个新的拼图状态（一个对象）都是使用以下方法创建的：

Puzzle *next=(current->moveDown());
Puzzle *next=(current->moveRight());
Puzzle *next=(current->moveUp());
Puzzle *next=(current->moveRight());

我想 .push(next) 到（Puzzle* 的）（最小）优先级队列或堆上，根据 next->FCost.

排序

一般来说，有没有一种方法可以使用这些 STL 数据结构中的任何一个来包含指向对象的指针 - 按每个对象特定的成员变量 (FCost) 排序？

Answer 1

是的，您可以为 priority_queue

指定自定义比较函数

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

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

8 谜题：排序STL Heap/Priorirty 包含成员变量指针的队列

8 Puzzle: Sorting STL Heap/Priorirty Queue containing pointers to object by member variable

c++

stl

sliding-tile-puzzle