A* algoritmus

• IPA: érvénytelen IPA-karakterek (*)

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.

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.

AStar(start, goal):
    Open = üres prioritásos sor
    Closed = üres halmaz
    g = 0
    f = 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 + cost(current, szomszéd)
            ha szomszéd not in Open vagy tentative_g < g:
                g = tentative_g
                f = g + h(szomszéd)
                ha szomszéd not in Open:
                    Open.helyezd_el(szomszéd)

    térj vissza "Nincs út"

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 = 0
    f_score = {node: float('inf') for node in graph}
    f_score = h

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

        if current == goal:
            path = 
            while current in came_from:
                path.append(current)
                current = came_from
            return path

        for neighbor, cost in graph.items():
            tentative_g_score = g_score + cost
            if tentative_g_score < g_score:
                came_from = current
                g_score = tentative_g_score
                f_score = g_score + h
                if not any(neighbor == item for item in open_set):
                    heapq.heappush(open_set, (f_score, 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: 

#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;
    }
    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 = numeric_limits<double>::infinity();
        f_score = numeric_limits<double>::infinity();
    }
    g_score = 0;
    f_score = h;
    open_set.push({start, f_score});

    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) {
            double tentative_g_score = g_score + neighbor.second;
            if (tentative_g_score < g_score) {
                came_from = current;
                g_score = tentative_g_score;
                f_score = g_score + h;
                open_set.push({neighbor.first, f_score});
            }
        }
    }

    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

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.

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.

• A* algoritmus - Értelmező szótár (MEK)
• A* algoritmus - Etimológiai szótár (UMIL)
• A* algoritmus - Szótár.net (hu-hu)
• A* algoritmus - DeepL (hu-de)
• A* algoritmus - Яндекс (hu-ru)
• A* algoritmus - Google (hu-en)
• A* algoritmus - Helyesírási szótár (MTA)
• A* algoritmus - Wikidata
• A* algoritmus - Wikipédia (magyar)