最佳优先搜索（Best First Search）是一种启发式搜索算法，它根据评估函数选择最有希望的节点进行扩展。它利用启发式方法对搜索空间中的节点进行优先级排序，以估计它们的潜力。通过迭代选择最有希望的节点，它旨在高效地导航至目标状态，这使得它在解决优化问题时特别有效。
给定一个图的边列表，其中每条边表示为 (u, v, w)。这里 u、v 和 w 分别代表边的源节点、目标节点和权重。我们需要对该图执行最佳优先搜索（下一步选择代价最小的边）。
示例：
> 输入：source = 0, target = 9
> edgeList = [ [ 0, 1, 3 ], [ 0, 2, 6 ], [ 0, 3, 5 ], [ 1, 4, 9 ],
> [ 1, 5, 8 ], [ 2, 6, 12 ], [ 2, 7, 14 ], [ 3, 8, 7 ],
> [ 8, 9, 5 ], [ 8, 10, 6 ], [ 9, 11, 1 ], [ 9, 12, 10 ], [ 9, 13, 2 ] ]
> 输出：0 1 3 2 8 9
> 解释：以下描述了最佳优先搜索的工作原理：
>
> – 从节点 0 开始。在其邻居中，节点 1 的代价最低（边代价为 3），因此从 0 移动到 1。
> – 从节点 1 出发，由于前方没有更好的路径可用，回溯到节点 0。
> – 从节点 0 开始，选择下一个最好的邻居——节点 3（边代价为 5）——并移动到节点 3。
> – 在节点 3 处，发现移动到节点 2 会带来更低的增量代价。
> – 然后从节点 2 移动到节点 8，最后从节点 8 移动到节点 9（目标节点）。
>
> 输入：source = 0, target = 8
> edgeList = [ [ 0, 1, 3 ], [ 0, 2, 6 ], [ 0, 3, 5 ], [ 1, 4, 9 ],
> [ 1, 5, 8 ], [ 2, 6, 12 ], [ 2, 7, 14 ], [ 3, 8, 7 ],
> [ 8, 9, 5 ], [ 8, 10, 6 ], [ 9, 11, 1 ], [ 9, 12, 10 ], [ 9, 13, 2 ] ]
> 输出：0 1 3 2 8
> 解释：以下描述了最佳优先搜索的工作原理：
>
> – 从节点 0 开始。在其邻居中，节点 1 的代价最低（边代价为 3），因此从 0 移动到 1。
> – 从节点 1 出发，由于前方没有更好的路径可用，回溯到节点 0。
> – 从节点 0 开始，选择下一个最好的邻居——节点 3（边代价为 5）——并移动到节点 3。
> – 在节点 3 处，发现移动到节点 2 会带来更低的增量代价。
> – 然后从节点 2 移动到节点 8（目标节点）。
算法思路：
> 我们可以使用优先队列或堆来存储具有最低评估函数值的边代价，其操作类似于 广度优先搜索（BFS） 算法。
请遵循以下步骤：
- 初始化一个空的优先队列，命名为 pq。
- 将起始节点插入 pq。
- 当 pq 不为空时：
- 从 pq 中移除评估值最低的节点 u。
- 如果 u 是目标节点，则终止搜索。
- 否则，对于 u 的每个邻居 v：如果 v 尚未被访问，将 v 标记为已访问并将 v 插入 pq。
- 将 u 标记为已检查。
- 当达到目标或 pq 变空时结束该过程。
图解说明：
让我们考虑下面的例子：
> !Best-First-Search-Informed-Search最佳优先搜索（启发式搜索）
> – 我们从源点“S”开始，使用给定的代价和最佳优先搜索来寻找目标“I”。
> – pq 最初包含 S。
> – 我们从 pq 中移除 S，并将 S 未被访问的邻居加入 pq。
> – pq 现在包含 {A, C, B}（C 排在 B 之前，因为 C 的代价更小）。
> – 我们从 pq 中移除 A，并将 A 未被访问的邻居加入 pq。
> – pq 现在包含 {C, B, E, D}。
> – 我们从 pq 中移除 C，并将 C 未被访问的邻居加入 pq。
> – pq 现在包含 {B, H, E, D}。
> – 我们从 pq 中移除 B，并将 B 未被访问的邻居加入 pq。
> – pq 现在包含 {H, E, D, F, G}。
> – 我们从 pq 中移除 H。
> – 由于我们的目标“I”是 H 的邻居，我们返回结果。
下面是 具体实现：
C++
`
#include
using namespace std;
// 执行最佳优先搜索的函数
vector bestFirstSearch(vector<vector> edges,
int src, int target, int n) {
// 创建邻接表
vector<vector<vector>> adj(n);
for (int i = 0; i < edges.size(); i++) {
adj[edges[i][0]].push_back({edges[i][1], edges[i][2]});
adj[edges[i][1]].push_back({edges[i][0], edges[i][2]});
}
// 创建一个 visited 数组来
// 跟踪已访问的节点
vector visited(n, false);
// 创建最小堆来存储节点
// 基于代价排序
priority_queue<vector, vector<vector>,
greater<vector>> pq;
// 将源节点推入最小堆
pq.push({0, src});
// 标记源节点为已访问
visited[src] = true;
// 存储路径
vector path;
// 循环直到最小堆为空
while (!pq.empty())