A Legjobbat először keresés (Best-First Search, BFS) egy informált gráfkeresési algoritmus, amely mindig azt a csomópontot választja ki a vizsgálatra, amelynek a legígéretesebb a becsült költsége a célhoz. A leggyakrabban heurisztikus függvényeket használ a legígéretesebb csomópont kiválasztására.
function BestFirstSearch(graph, start, goal):
nyílt = prioritási_sor
zárt = üres
while nyílt nem üres:
jelenlegi = nyílt.remove_legkisebb() # Legkisebb h(n)
ha jelenlegi == goal:
térj vissza az útvonalra
add jelenlegit a zárt listához
minden szomszéd a jelenlegihez:
ha szomszéd nincs a zártban:
nyílt.add(szomszéd, h(szomszéd))
import heapq
class Graph:
def __init__(self):
self.edges = {}
self.h_values = {}
def add_edge(self, from_node, to_node, cost):
if from_node not in self.edges:
self.edges =
self.edges.append((to_node, cost))
def set_heuristic(self, node, h_value):
self.h_values = h_value
def get_neighbors(self, node):
return self.edges.get(node, )
def get_heuristic(self, node):
return self.h_values.get(node, float('inf'))
def best_first_search(graph, start, goal):
open_list =
heapq.heappush(open_list, (graph.get_heuristic(start), start))
closed_list = set()
while open_list:
_, current = heapq.heappop(open_list)
if current == goal:
print(f"Cél elérve: {current}")
return True
closed_list.add(current)
for neighbor, cost in graph.get_neighbors(current):
if neighbor not in closed_list:
heapq.heappush(open_list, (graph.get_heuristic(neighbor), neighbor))
print("Nem található út a célhoz.")
return False
# Példa használat
graph = Graph()
graph.add_edge('A', 'B', 1)
graph.add_edge('A', 'C', 3)
graph.add_edge('B', 'D', 4)
graph.add_edge('C', 'D', 2)
graph.add_edge('C', 'E', 5)
graph.add_edge('D', 'F', 1)
graph.add_edge('E', 'F', 2)
graph.set_heuristic('A', 6)
graph.set_heuristic('B', 5)
graph.set_heuristic('C', 4)
graph.set_heuristic('D', 3)
graph.set_heuristic('E', 6)
graph.set_heuristic('F', 0)
best_first_search(graph, 'A', 'F')
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <functional>
using namespace std;
class Graph {
public:
unordered_map<string, vector<pair<string, int>>> edges;
unordered_map<string, int> h_values;
void addEdge(const string& from, const string& to, int cost) {
edges.emplace_back(to, cost);
}
void setHeuristic(const string& node, int h_value) {
h_values = h_value;
}
vector<pair<string, int>> getNeighbors(const string& node) {
return edges;
}
int getHeuristic(const string& node) {
return h_values;
}
};
void bestFirstSearch(Graph& graph, const string& start, const string& goal) {
auto cmp = (pair<int, string> left, pair<int, string> right) {
return left.first > right.first;
};
priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(cmp)> openList(cmp);
unordered_map<string, bool> closedList;
openList.emplace(graph.getHeuristic(start), start);
while (!openList.empty()) {
auto = openList.top();
openList.pop();
if (current == goal) {
cout << "Cél elérve: " << current << endl;
return;
}
closedList = true;
for (auto& : graph.getNeighbors(current)) {
if (!closedList) {
openList.emplace(graph.getHeuristic(neighbor), neighbor);
}
}
}
cout << "Nem található út a célhoz." << endl;
}
int main() {
Graph graph;
graph.addEdge("A", "B", 1);
graph.addEdge("A", "C", 3);
graph.addEdge("B", "D", 4);
graph.addEdge("C", "D", 2);
graph.addEdge("C", "E", 5);
graph.addEdge("D", "F", 1);
graph.addEdge("E", "F", 2);
graph.setHeuristic("A", 6);
graph.setHeuristic("B", 5);
graph.setHeuristic("C", 4);
graph.setHeuristic("D", 3);
graph.setHeuristic("E", 6);
graph.setHeuristic("F", 0);
bestFirstSearch(graph, "A", "F");
return 0;
}