Wikiszótár

nyalábkeresés

Magyar

Kiejtés

  • IPA: [ ˈɲɒlaːpkɛrɛʃeːʃ]

Főnév

nyalábkeresés

  1. (matematika, algoritmusok)

Nyalábkeresés (Beam Search)

A nyalábkeresés egy heurisztikus keresési algoritmus, amelyet gyakran használnak nagy keresési terekben, például természetes nyelvfeldolgozásban és mesterséges intelligenciában (például játékokban). Az algoritmus egy adott számú (“nyaláb szélessége”) legígéretesebb csomópontot tart meg minden iterációban, ahelyett hogy az összes lehetséges csomópontot vizsgálná.


Algoritmus jellemzői

  1. Nyaláb szélessége ((k)): Meghatározza, hogy hány legjobb csomópontot tartson meg az algoritmus minden lépésben.
  2. Heurisztika: Minden csomópontot egy értékkel (pontszám, költség, vagy valószínűség) rangsorol.
  3. Helyi optimalizáció: Csak a legjobb (k) csomópontot vizsgálja tovább.


Pszeudokód

function BeamSearch(start, goal, k):
    Nyitott = [start]  # Kezdő csomópont
    amíg Nyitott nem üres:
        Következő = []  # Következő nyaláb
        minden csomópont n a Nyitott listában:
            ha n == cél:
                térj vissza az útvonalra
            minden szomszéd s n csomóponthoz:
                értékeld ki a s csomópontot
                add hozzá Következő-hez
        Rendezd Következő-t a heurisztikus értékek szerint
        Nyitott = Következő első k eleme

    térj vissza "Nem található megoldás"

Python implementáció

import heapq

def beam_search(start, goal, get_neighbors, evaluate, beam_width):
    """
    Beam Search algoritmus.
    :param start: Kezdő csomópont
    :param goal: Cél csomópont
    :param get_neighbors: Függvény, amely egy csomópont szomszédjait adja vissza
    :param evaluate: Heurisztikus érték számítás
    :param beam_width: A nyaláb szélessége
    :return: Megtalált útvonal vagy üres lista
    """
    open_list = [(evaluate(start), start)]  # Prioritási sor (heurisztika, csomópont)
    path = {start: [start]}  # Útvonal nyomon követése

    while open_list:
        next_beam = []
        for _, current in open_list:
            if current == goal:
                return path[current]

            for neighbor in get_neighbors(current):
                new_path = path[current] + [neighbor]
                path[neighbor] = new_path
                heapq.heappush(next_beam, (evaluate(neighbor), neighbor))

        # Csak a legjobb 'beam_width' csomópontot tartjuk meg
        open_list = heapq.nsmallest(beam_width, next_beam)

    return []

# Példa használat
def example_neighbors(node):
    graph = {
        'A': ['B', 'C', 'D'],
        'B': ['E', 'F'],
        'C': ['G'],
        'D': ['H'],
        'E': [],
        'F': [],
        'G': [],
        'H': ['I'],
        'I': []
    }
    return graph.get(node, [])

def example_heuristic(node):
    heuristic = {
        'A': 6,
        'B': 4,
        'C': 5,
        'D': 7,
        'E': 3,
        'F': 2,
        'G': 5,
        'H': 6,
        'I': 1
    }
    return heuristic.get(node, float('inf'))

start_node = 'A'
goal_node = 'I'
beam_width = 2

result = beam_search(start_node, goal_node, example_neighbors, example_heuristic, beam_width)
print("Talált útvonal:", result)

Példa kimenet

Talált útvonal: ['A', 'D', 'H', 'I']

C++ implementáció

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>
#include <functional>
#include <algorithm>

using namespace std;

struct Node {
    string name;
    int heuristic;

    bool operator>(const Node& other) const {
        return heuristic > other.heuristic;
    }
};

vector<string> beam_search(
    const string& start,
    const string& goal,
    function<vector<Node>(const string&)> get_neighbors,
    int beam_width
) {
    priority_queue<Node, vector<Node>, greater<Node>> open_list;
    unordered_map<string, vector<string>> path;
    open_list.push({start, 0});
    path[start] = {start};

    while (!open_list.empty()) {
        vector<Node> next_beam;
        while (!open_list.empty()) {
            Node current = open_list.top();
            open_list.pop();

            if (current.name == goal) {
                return path[current.name];
            }

            for (const auto& neighbor : get_neighbors(current.name)) {
                path[neighbor.name] = path[current.name];
                path[neighbor.name].push_back(neighbor.name);
                next_beam.push_back(neighbor);
            }
        }

        sort(next_beam.begin(), next_beam.end(), greater<Node>());
        next_beam.resize(min(beam_width, (int)next_beam.size()));
        for (const auto& node : next_beam) {
            open_list.push(node);
        }
    }

    return {};
}

vector<Node> example_neighbors(const string& node) {
    unordered_map<string, vector<Node>> graph = {
        {"A", {{"B", 4}, {"C", 5}, {"D", 7}}},
        {"B", {{"E", 3}, {"F", 2}}},
        {"C", {{"G", 5}}},
        {"D", {{"H", 6}}},
        {"H", {{"I", 1}}}
    };
    return graph[node];
}

int main() {
    string start = "A";
    string goal = "I";
    int beam_width = 2;

    vector<string> result = beam_search(start, goal, example_neighbors, beam_width);

    if (!result.empty()) {
        cout << "Talált útvonal: ";
        for (const auto& node : result) {
            cout << node << " ";
        }
        cout << endl;
    } else {
        cout << "Nem található megoldás." << endl;
    }

    return 0;
}

Példa kimenet

Talált útvonal: A D H I

Összegzés

A nyalábkeresés hatékony heurisztikus algoritmus, különösen nagy keresési terekben. A keresés hatékonysága és pontossága nagymértékben függ a nyaláb szélességétől és a heurisztika minőségétől. Bár nem garantálja az optimális megoldást, sok alkalmazásban, például természetes nyelvfeldolgozásban vagy AI alapú játékokban, gyors és praktikus megoldást nyújt.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=nyalábkeresés&oldid=3480180”