Wikiszótár

A* algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɒ*ɒlɡoritmuʃ] érvénytelen IPA-karakterek (*)

Főnév

A* algoritmus

  1. (matematika, informatika, algoritmusok) Az A* egy informált keresési algoritmus, amelyet széles körben használnak grafok és hálózatok rövid útjainak keresésére. Az algoritmus különösen hatékony, mivel egy heurisztikus függvényt alkalmaz, amely vezeti a keresést az optimális megoldás felé, miközben minimalizálja a vizsgálandó csomópontok számát.


Elmélet

  1. Cél:
    • Egy gráfban megtalálni a legolcsóbb utat a kiindulási csomópontból ((start)) a célcsomópontba ((goal)).
  2. Heurisztikus keresés:
    • Az A* algoritmus a g(n) + h(n) függvényt optimalizálja, ahol:
      • (g(n)): Az út költsége a kiindulási csomópontból (n)-be.
      • (h(n)): A heurisztikus becslés az (n)-ből a célba vezető útra.
  3. Adott feltétel:
    • A heurisztikus függvény ((h(n))) admisszibilis, ha soha nem becsül túl, azaz (h(n) ).
  4. Működés:
    • Nyitott halmaz ((Open)): Az összes csomópont, amelyet vizsgálunk.
    • Zárt halmaz ((Closed)): Az összes csomópont, amelyet már megvizsgáltunk.
    • Az algoritmus mindig a legkisebb (f(n) = g(n) + h(n)) értékkel rendelkező csomópontot vizsgálja.


Pszeudokód

AStar(start, goal):
    Open = üres prioritásos sor
    Closed = üres halmaz
    g[start] = 0
    f[start] = h(start)
    Open.helyezd_el(start)

    amíg Open nem üres:
        current = Open.min_f()
        ha current == goal:
            térj vissza az útvonalra

        Open.távolítsd_el(current)
        Closed.helyezd_el(current)

        minden szomszéd in current.szomszédai:
            ha szomszéd in Closed:
                folytasd
            tentative_g = g[current] + cost(current, szomszéd)
            ha szomszéd not in Open vagy tentative_g < g[szomszéd]:
                g[szomszéd] = tentative_g
                f[szomszéd] = g[szomszéd] + h(szomszéd)
                ha szomszéd not in Open:
                    Open.helyezd_el(szomszéd)

    térj vissza "Nincs út"

Python implementáció

import heapq

def a_star(graph, start, goal, h):
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    f_score = {node: float('inf') for node in graph}
    f_score[start] = h[start]

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]

        for neighbor, cost in graph[current].items():
            tentative_g_score = g_score[current] + cost
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + h[neighbor]
                if not any(neighbor == item[1] for item in open_set):
                    heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return "Nincs elérhető út"

# Példa gráf
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# Heurisztikus függvény
h = {
    'A': 7,
    'B': 6,
    'C': 2,
    'D': 0
}

start = 'A'
goal = 'D'
path = a_star(graph, start, goal, h)
print("Útvonal:", path)

Kimenet: 

Útvonal: ['A', 'B', 'C', 'D']

C++ implementáció

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
using namespace std;

struct Node {
    string name;
    double cost;
    bool operator>(const Node& other) const {
        return cost > other.cost;
    }
};

vector<string> reconstruct_path(unordered_map<string, string>& came_from, string current) {
    vector<string> path;
    while (came_from.find(current) != came_from.end()) {
        path.push_back(current);
        current = came_from[current];
    }
    reverse(path.begin(), path.end());
    return path;
}

vector<string> a_star(
    unordered_map<string, unordered_map<string, double>>& graph,
    unordered_map<string, double>& h,
    string start,
    string goal) {
    priority_queue<Node, vector<Node>, greater<Node>> open_set;
    unordered_map<string, double> g_score;
    unordered_map<string, double> f_score;
    unordered_map<string, string> came_from;

    for (auto& node : graph) {
        g_score[node.first] = numeric_limits<double>::infinity();
        f_score[node.first] = numeric_limits<double>::infinity();
    }
    g_score[start] = 0;
    f_score[start] = h[start];
    open_set.push({start, f_score[start]});

    while (!open_set.empty()) {
        string current = open_set.top().name;
        open_set.pop();

        if (current == goal) {
            return reconstruct_path(came_from, current);
        }

        for (auto& neighbor : graph[current]) {
            double tentative_g_score = g_score[current] + neighbor.second;
            if (tentative_g_score < g_score[neighbor.first]) {
                came_from[neighbor.first] = current;
                g_score[neighbor.first] = tentative_g_score;
                f_score[neighbor.first] = g_score[neighbor.first] + h[neighbor.first];
                open_set.push({neighbor.first, f_score[neighbor.first]});
            }
        }
    }

    return {"Nincs elérhető út"};
}

int main() {
    unordered_map<string, unordered_map<string, double>> graph = {
        {"A", {{"B", 1}, {"C", 4}}},
        {"B", {{"A", 1}, {"C", 2}, {"D", 5}}},
        {"C", {{"A", 4}, {"B", 2}, {"D", 1}}},
        {"D", {{"B", 5}, {"C", 1}}}
    };

    unordered_map<string, double> h = {
        {"A", 7},
        {"B", 6},
        {"C", 2},
        {"D", 0}
    };

    string start = "A";
    string goal = "D";

    vector<string> path = a_star(graph, h, start, goal);
    cout << "Útvonal: ";
    for (auto& node : path) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Kimenet: 

Útvonal: A B C D

Összegzés

Előnyök:

  1. Hatékony, mivel csak az ígéretes csomópontokat vizsgálja.
  2. Optimalitás: Garantáltan megtalálja a legrövidebb utat, ha (h(n)) admisszibilis.

Hátrányok:

  1. Nagy memóriaigény, mivel sok csomópontot kell tárolni.
  2. A heurisztikus függvény minősége erősen befolyásolja a teljesítményt.

Az A* algoritmus kiváló választás útvonaltervezési problémákra, például térképészeti alkalmazásokban, mesterséges intelligenciában és robotikában.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=A*_algoritmus&oldid=3479513”