資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的貪婪最佳優先搜尋演算法
計算機科學中的良好問題解決很大程度上依賴於高效的演算法，例如貪婪最佳優先搜尋 (GBFS)。GBFS 已經確立了作為路徑查詢或最佳化問題的最佳解決方案方法的可信度。因此，我們在本文中深入探討了 GBFS，同時探索了使用 C++ 的實現方法。
語法
void greedyBestFirstSearch(Graph graph, Node startNode, Node goalNode);
演算法
貪婪最佳優先搜尋演算法旨在找到圖中從給定起始節點到目標節點的路徑。以下是演算法的常規步驟：
初始化一個空優先佇列。
將起始節點入隊到優先佇列中。
建立一個空集合來跟蹤已訪問的節點。
當優先佇列不為空時：
從佇列中出隊優先順序最高的節點。
如果出隊的節點是目標節點，則演算法終止，並且找到路徑。
否則，將出隊的節點標記為已訪問。
將出隊的節點的所有未訪問的相鄰節點入隊到優先佇列中。
如果在到達目標節點之前優先佇列變空，則不存在路徑。
方法 1：基於歐幾里得距離的啟發式函式
示例
#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
#include <unordered_set>
using namespace std;
// Structure to represent a node in the graph
struct Node {
int x, y; // Coordinates of the node
int cost; // Cost to reach this node
};
// Euclidean distance heuristic function
double euclideanDistance(int x1, int y1, int x2, int y2) {
return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2));
}
// Custom comparison function for nodes in the priority queue
struct NodeCompare {
bool operator()(const Node& node1, const Node& node2) const {
return node1.cost > node2.cost;
}
};
// Greedy Best-First Search function
void greedyBestFirstSearch(vector<vector<int>>& graph, Node start, Node goal) {
int rows = graph.size();
int cols = graph[0].size();
// Priority queue for nodes to be explored
priority_queue<Node, vector<Node>, NodeCompare> pq;
// Visited nodes set
unordered_set<int> visited;
// Add the start node to the priority queue
pq.push(start);
while (!pq.empty()) {
// Get the node with the lowest cost
Node current = pq.top();
pq.pop();
// Check if the current node is the goal node
if (current.x == goal.x && current.y == goal.y) {
cout << "Goal node reached!" << endl;
return;
}
// Mark the current node as visited
int nodeId = current.x * cols + current.y;
visited.insert(nodeId);
// Explore the neighboring nodes
int dx[] = {-1, 1, 0, 0}; // Possible x-direction movements
int dy[] = {0, 0, -1, 1}; // Possible y-direction movements
for (int i = 0; i < 4; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];
// Check if the neighboring node is within the graph boundaries
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
// Calculate the heuristic value for the neighboring node
double heuristicValue = euclideanDistance(newX, newY, goal.x, goal.y);
// Check if the neighboring node has not been visited
if (visited.find(newX * cols + newY) == visited.end()) {
// Create a new node for the neighboring position
Node neighbor;
neighbor.x = newX;
neighbor.y = newY;
neighbor.cost = current.cost + graph[newX][newY];
// Add the neighboring node to the priority queue
pq.push(neighbor);
}
}
}
}
cout << "Goal node not reachable!" << endl;
}
int main() {
// Example graph represented as a 2D vector
vector<vector<int>> graph = {
{3, 5, 1, 2},
{1, 3, 2, 4},
{5, 2, 6, 7},
{4, 3, 1, 2}
};
Node start;
start.x = 0; // Starting x-coordinate
start.y = 0; // Starting y-coordinate
start.cost = 0; // Cost to reach the starting node
Node goal;
goal.x = 3; // Goal x-coordinate
goal.y = 3; // Goal y-coordinate
// Run Greedy Best-First Search algorithm
greedyBestFirstSearch(graph, start, goal);
return 0;
}
輸出
Goal node reached!
解釋
這段程式碼包含兩個關鍵元素。首先，它包含 Graph 類的定義，該類使用鄰接表表示圖結構。
其次，它引入了 CompareEuclideanDistance - 一個自定義比較器，用於透過使用歐幾里得距離公式估計節點與目標節點的距離來評估節點。
greedyBestFirstSearch 函式實現了貪婪最佳優先搜尋演算法。它使用優先佇列根據啟發式值儲存節點。
該演算法首先將起始節點入隊到優先佇列中。
在每次迭代中，它都出隊優先順序最高的節點，並檢查它是否為目標節點。
如果找到目標節點，則列印“路徑已找到！”訊息。否則，該演算法將出隊的節點標記為已訪問，並將其未訪問的相鄰節點入隊。
如果優先佇列在未找到目標節點的情況下變空，則列印“不存在路徑！”訊息。
main 函式透過建立圖、定義起始和目標節點以及呼叫 greedyBestFirstSearch 函式來演示演算法的使用。
方法 2：基於曼哈頓距離的啟發式函式
我們解決此問題的策略是使用依賴於曼哈頓距離概念的啟發式函式。這種距離度量，有時稱為計程車距離，涉及將節點之間的水平和垂直距離加起來。
示例
#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
#include <unordered_set>
using namespace std;
// Structure to represent a node in the graph
struct Node {
int x, y; // Coordinates of the node
int cost; // Cost to reach this node
};
// Manhattan distance heuristic function
int manhattanDistance(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
// Custom comparison function for nodes in the priority queue
struct NodeCompare {
bool operator()(const Node& node1, const Node& node2) const {
return node1.cost > node2.cost;
}
};
// Greedy Best-First Search function
void greedyBestFirstSearch(vector<vector<int>>& graph, Node start, Node goal) {
int rows = graph.size();
int cols = graph[0].size();
// Priority queue for nodes to be explored
priority_queue<Node, vector<Node>, NodeCompare> pq;
// Visited nodes set
unordered_set<int> visited;
// Add the start node to the priority queue
pq.push(start);
while (!pq.empty()) {
// Get the node with the lowest cost
Node current = pq.top();
pq.pop();
// Check if the current node is the goal node
if (current.x == goal.x && current.y == goal.y) {
cout << "Goal node reached!" << endl;
return;
}
// Mark the current node as visited
int nodeId = current.x * cols + current.y;
visited.insert(nodeId);
// Explore the neighboring nodes
int dx[] = {-1, 1, 0, 0}; // Possible x-direction movements
int dy[] = {0, 0, -1, 1}; // Possible y-direction movements
for (int i = 0; i < 4; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];
// Check if the neighboring node is within the graph boundaries
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
// Calculate the heuristic value for the neighboring node
int heuristicValue = manhattanDistance(newX, newY, goal.x, goal.y);
// Check if the neighboring node has not been visited
if (visited.find(newX * cols + newY) == visited.end()) {
// Create a new node for the neighboring position
Node neighbor;
neighbor.x = newX;
neighbor.y = newY;
neighbor.cost = current.cost + graph[newX][newY];
// Add the neighboring node to the priority queue
pq.push(neighbor);
}
}
}
}
cout << "Goal node not reachable!" << endl;
}
int main() {
// Example graph represented as a 2D vector
vector<vector<int>> graph = {
{3, 5, 1, 2},
{1, 3, 2, 4},
{5, 2, 6, 7},
{4, 3, 1, 2}
};
Node start;
start.x = 0; // Starting x-coordinate
start.y = 0; // Starting y-coordinate
start.cost = 0; // Cost to reach the starting node
Node goal;
goal.x = 3; // Goal x-coordinate
goal.y = 3; // Goal y-coordinate
// Run Greedy Best-First Search algorithm
greedyBestFirstSearch(graph, start, goal);
return 0;
}
輸出
Goal node reached!
解釋
該程式碼的結構與方法 1 類似，但使用了一個自定義比較器 CompareManhattanDistance，該比較器使用曼哈頓距離公式根據節點到目標節點的估計距離對節點進行比較。
greedyBestFirstSearch 函式使用曼哈頓距離啟發式實現了貪婪最佳優先搜尋演算法。
main 函式演示了演算法的使用，建立了一個圖，定義了起始和目標節點，並呼叫了 greedyBestFirstSearch 函式。
結論
在本文中，我們探討了貪婪最佳優先搜尋演算法及其在 C++ 中的實現。透過使用這些方法，程式設計師可以有效地在圖中找到路徑並解決最佳化問題。啟發式函式（例如歐幾里得距離或曼哈頓距離）的選擇會顯著影響演算法在不同場景下的效能。
更新於：2023-07-25
1K+ 閱讀量
廣告