Best First Search (Informed Search)
2022/6/17 23:27:10
本文主要是介绍Best First Search (Informed Search),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Best First Search (Informed Search)
https://www.geeksforgeeks.org/best-first-search-informed-search/
最好优先搜索
BFS DFS使用暴力方式盲目搜索。
Best First 方式,使用评价函数来决定最有希望的邻居节点,然后做节点扩展。
实现方式,评价函数中考虑 启发式规则, 此规则利用的Informed信息。
In BFS and DFS, when we are at a node, we can consider any of the adjacent as the next node. So both BFS and DFS blindly explore paths without considering any cost function.
The idea of Best First Search is to use an evaluation function to decide which adjacent is most promising and then explore.
Best First Search falls under the category of Heuristic Search or Informed Search.
Implementation of Best First Search:
使用优先队列或者堆来存储节点的花费
BFS使用queue
DFS使用stack
此方法使用 优先队列
We use a priority queue or heap to store the costs of nodes that have the lowest evaluation function value. So the implementation is a variation of BFS, we just need to change Queue to PriorityQueue.
// Pseudocode for Best First Search Best-First-Search(Graph g, Node start) 1) Create an empty PriorityQueue PriorityQueue pq; 2) Insert "start" in pq. pq.insert(start) 3) Until PriorityQueue is empty u = PriorityQueue.DeleteMin If u is the goal Exit Else Foreach neighbor v of u If v "Unvisited" Mark v "Visited" pq.insert(v) Mark u "Examined" End procedure
算法复杂度中
n -- 对最坏情况下需要访问n元素,
log n -- 使用堆或者优先队列,获取最值得复杂度。
Analysis :
- The worst-case time complexity for Best First Search is O(n * log n) where n is the number of nodes. In the worst case, we may have to visit all nodes before we reach goal. Note that priority queue is implemented using Min(or Max) Heap, and insert and remove operations take O(log n) time.
- The performance of the algorithm depends on how well the cost or evaluation function is designed.
特殊的情况有 贪婪优先搜索 和 A星搜索
Special cases of Best first search:
- Greedy Best first search algorithm
- A* search algorithm
Sample Code
此代码中,仅仅考虑扩展时候的最小代价。
// C++ program to implement Best First Search using priority // queue #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pi; vector<vector<pi> > graph; // Function for adding edges to graph void addedge(int x, int y, int cost) { graph[x].push_back(make_pair(cost, y)); graph[y].push_back(make_pair(cost, x)); } // Function For Implementing Best First Search // Gives output path having lowest cost void best_first_search(int actual_Src, int target, int n) { vector<bool> visited(n, false); // MIN HEAP priority queue priority_queue<pi, vector<pi>, greater<pi> > pq; // sorting in pq gets done by first value of pair pq.push(make_pair(0, actual_Src)); int s = actual_Src; visited[s] = true; while (!pq.empty()) { int x = pq.top().second; // Displaying the path having lowest cost cout << x << " "; pq.pop(); if (x == target) break; for (int i = 0; i < graph[x].size(); i++) { if (!visited[graph[x][i].second]) { visited[graph[x][i].second] = true; pq.push(make_pair(graph[x][i].first,graph[x][i].second)); } } } } // Driver code to test above methods int main() { // No. of Nodes int v = 14; graph.resize(v); // The nodes shown in above example(by alphabets) are // implemented using integers addedge(x,y,cost); addedge(0, 1, 3); addedge(0, 2, 6); addedge(0, 3, 5); addedge(1, 4, 9); addedge(1, 5, 8); addedge(2, 6, 12); addedge(2, 7, 14); addedge(3, 8, 7); addedge(8, 9, 5); addedge(8, 10, 6); addedge(9, 11, 1); addedge(9, 12, 10); addedge(9, 13, 2); int source = 0; int target = 9; // Function call best_first_search(source, target, v); return 0; }
这篇关于Best First Search (Informed Search)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升