Wikiszótár

legjobbat először keresés

Magyar

Kiejtés

  • IPA: [ ˈlɛɡjobːɒt ˈɛløːsør ˈkɛrɛʃeːʃ]

Főnév

legjobbat először keresés

  1. (matematika, algoritmusok)

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.


Algoritmus jellemzői

  1. Heurisztikus alapú: Egy heurisztikus függvény ( h(n) ) alapján rangsorolja a csomópontokat. Ez a függvény a csomópontból a célba vezető út várható költségét becsüli.
  2. Prioritási sor: Az algoritmus prioritási sort használ, hogy mindig a legkisebb ( h(n) )-nel rendelkező csomópontot válassza.
  3. Nem garantált optimális megoldás: Csak akkor optimális, ha a heurisztika admisszibilis (soha nem becsül túl).


Algoritmus lépései

  1. Kezdd a kezdő csomóponttal.
  2. Helyezd a kezdő csomópontot egy prioritási sorba az ( h(n) ) értékével.
  3. Amíg a prioritási sor nem üres:
    • Vedd ki a legkisebb ( h(n) )-értékű csomópontot.
    • Ha ez a célcsomópont, akkor megtaláltad a megoldást.
    • Ellenkező esetben vizsgáld meg az összes szomszédját:
      • Számítsd ki a szomszédok heurisztikus értékét.
      • Add hozzá a szomszédokat a prioritási sorhoz.
  4. Ha a prioritási sor üres, és nincs megoldás, a keresés sikertelen.


Pszeudokód

function BestFirstSearch(graph, start, goal):
    nyílt = prioritási_sor [(start, h(start))]
    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))

Python implementáció

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[from_node] = []
        self.edges[from_node].append((to_node, cost))

    def set_heuristic(self, node, h_value):
        self.h_values[node] = 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')

C++ implementáció

#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[from].emplace_back(to, cost);
    }

    void setHeuristic(const string& node, int h_value) {
        h_values[node] = h_value;
    }

    vector<pair<string, int>> getNeighbors(const string& node) {
        return edges[node];
    }

    int getHeuristic(const string& node) {
        return h_values[node];
    }
};

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 [h_value, current] = openList.top();
        openList.pop();

        if (current == goal) {
            cout << "Cél elérve: " << current << endl;
            return;
        }

        closedList[current] = true;

        for (auto& [neighbor, cost] : graph.getNeighbors(current)) {
            if (!closedList[neighbor]) {
                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;
}

Összegzés

  • Heurisztikus keresés: A legjobbat először keresés informált heurisztikus keresési algoritmus.
  • Időbonyolultság: Az algoritmus hatékonysága a prioritási sor karbantartásán és a heurisztikus függvény pontosságán múlik.
  • Előnyök: Gyorsan megtalálhatja a célcsomópontot a megfelelő heurisztikával.
  • Hátrányok: Nem garantált optimális megoldás, ha a heurisztika inadmisszibilis.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=legjobbat_először_keresés&oldid=3480171”