| dbo:abstract
|
- L'algorisme de cerca A* (en anglès, A-star algorithm) és un algorisme heurístic de cerca del camí més curt, molt eficient i generalitzable, motiu pel qual s'utilitza sovint en molts camps de la informàtica, com ara en la robòtica o en aplicacions com ara videojocs. Peter Hart, Nils Nilsson i Bertram Raphael de l'Institut de Recerca de Stanford (ara SRI International) van publicar l'algorisme per primera vegada el 1968. Es pot veure com una extensió de l'algorisme de Dijkstra, però amb un millor rendiment mitjançant l'heurística per guiar la cerca en direcció a l'objectiu, és a dir, emprant mètodes com la distància de Manhattan, la distància de Txebixov, la distància euclidiana o bé la . (ca)
- خوارزمية البحث بأولوية الأفضل، (بالإنجليزية: A* search algorithm) هي تبسيط عن خوارزمية *A التي قدمها بيتر هارت في العام 1968. تستخدم هذه الخوارزمية الأدوات التالية: 1.
* قائمة (OPEN) للعقد التي ولدت وطبقت دالة الكشف (Heuristic Function) عليها ولكن لم تفحص بعد أي لم يتم توليد عقد تابعة منها. هذه القائمة هي من نوع صف تفضيل للأولوية (Priority Queue) حيث العقد ذات القيم الأعلى في دالة الكشف لها أولوية أكبر. 2.
* قائمة (CLOSED) للعقد التي فحصت وتم توليد العقد التابعة منها. هذه القائمة تبقى في الذاكرة لفحصها عند توليد عقد جديدة لمعرفة إن كانت مولدة سابقاً وتم المرور بها. 3.
* دالة الكشف (Heuristic Function) التي تخمن أحقية كل عقدة يتم توليدها. هذه الدالة تمكن الخوارزمية من البحث في الطرق الواعدة في الوصول للهدف أولاً. 4.
* الدالة g التي تقيس التكلفة للوصول من العقدة الابتدائية إلى العقدة الحالية. هذه الدالة تعطي قيم حقيقية وليست تقدير. 5.
* الدالة 'h التي تخمن التكلفة الإضافية للوصول من العقدة الحالية إلى العقدة الهدف. هي إذن قياس لتكلفة الوصول للحل أي العقد الأفضل تأخذ قيماً دنيا والعقد الأسوء تأخذ قيماً عليا، وليست قياس لجودة العقد أي العقد الأفضل تأخذ قيماً أعلى. 6.
* الدالة 'f التي تعرف كحاصل جمع للدالتين السابقتين أي ('g + h) و قيمتها إذن تمثل تخمين للوصول من الحالة الابتدائية إلى الحالة الهدف عن طريق العقدة الحالية. (ar)
- A* (A star) je počítačový algoritmus používaný pro vyhledávání optimálních cest v kladně ohodnocených grafech. Byl vytvořen v roce 1968 , a . Používá stejné principy jako Dijkstrův algoritmus, ale přidává navíc heuristický prvek. (cs)
- A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases. Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search. Compared to Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified source to a specified goal, and not the shortest-path tree from a specified source to all possible goals. This is a necessary trade-off for using a specific-goal-directed heuristic. For Dijkstra's algorithm, since the entire shortest-path tree is generated, every node is a goal, and there can be no specific-goal-directed heuristic. (en)
- Der A*-Algorithmus („A Stern“ oder englisch „a star“, auch A*-Suche) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er wurde das erste Mal 1968 von , Nils J. Nilsson und beschrieben. Der Algorithmus gilt als Verallgemeinerung und Erweiterung des Dijkstra-Algorithmus, in vielen Fällen kann aber umgekehrt A* auch auf Dijkstra reduziert werden. Im Gegensatz zu uninformierten Suchalgorithmen verwendet der A*-Algorithmus eine Schätzfunktion (Heuristik), um zielgerichtet zu suchen und damit die Laufzeit zu verringern. Der Algorithmus ist vollständig und optimal. Das heißt, dass immer eine optimale Lösung gefunden wird, falls eine existiert. (de)
- En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle. L'algorithme A* a été créé pour que la première solution trouvée soit l'une des meilleures, c'est pourquoi il est célèbre dans des applications comme les jeux vidéo privilégiant la vitesse de calcul sur l'exactitude des résultats. Cet algorithme a été proposé pour la première fois par Peter E. Hart, Nils John Nilsson et Bertram Raphael en 1968. Il s'agit d'une extension de l'algorithme de Dijkstra de 1959 (p. 30-31 dans ). (fr)
- El algoritmo de búsqueda A* (pronunciado "A asterisco", "A estrella" o "A star" en inglés) se clasifica dentro de los algoritmos de búsqueda en grafos de tipo heurístico o informado. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo. (es)
- Algoritme A-Star (A*),(ditemukan pertama kali oleh Peter Hart, Nils Nilsson, dan Bertram Raphael pada tahun 1968) adalah algoritme pencarian rute terpendek (shortest path) yang merupakan perbaikan dari Algoritme BFS dengan memodifikasi fungsi heuristiknya untuk memberikan hasil yang optimal. Dimana menggabungkan fungsi heuristik [h(n)] dan jarak sesungguhnya/cost [g(n)]. Keterangan: 1.
* f(n) adalah jumlah dari g(n) dan h(n). ini adalah perkiraan jalur terpendek sementara. maka f(n) adalah jalur terpendek yang sebenarnya yang tidak ditelusuri sampai Algoritme A-Star (A*) diselesaikan. 2.
* g(n)/Geographical Cost adalah total jarak yang didapat dari verteks awal ke verteks sekarang (halangan). 3.
* h(n)/Heuristic Cost adalah perkiran jarak dari vertek sekarang (yang sedang dikunjungi) ke vertek tujuan. sebuah fungsi heuristic digunakan untuk membuat perkiraan seberapa jauh lintasan yang akan diambil ke vertek tujuan. (in)
- A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。最良優先探索を拡張したに、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの。h は ヒューリスティック関数と呼ばれる。 (ja)
- In informatica, A* (pronunciato /eɪ stɑːr/ in inglese) è un algoritmo di ricerca su grafi che individua un percorso da un dato nodo iniziale verso un dato nodo goal (o che passi un test di goal dato). Utilizza una "stima euristica" che classifica ogni nodo attraverso una stima della strada migliore che passa attraverso tale nodo. Visita il nodo in base a tale stima euristica. L'algoritmo A* è anche un esempio di ricerca best-first. L'algoritmo è stato descritto nel 1968 da , Nils Nilsson, e . (it)
- 정보과학 분야에 있어서, A* 알고리즘(A* algorithm 에이 스타 알고리즘[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나이다. 이 알고리즘은 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값 " 을 매기는 방법을 이용한다는 것이다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류할 수 있다. 이 알고리즘은 1968년 , , 이 처음 기술하였다. 그 3명의 논문에서, 이 알고리즘은 A 알고리즘(algorithm A)이라고 불렸다. 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 그러므로 A* 알고리즘이라고 불린다. A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지의 최적 경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 꼭짓점에 대한 평가 함수를 정의해야 한다. 이를 위한 평가 함수 은 다음과 같다.
* : 출발 꼭짓점으로부터 꼭짓점 까지의 경로 가중치
* : 꼭짓점 으로부터 목표 꼭짓점까지의 추정 경로 가중치 (ko)
- Algorytm A* – algorytm heurystyczny znajdowania najkrótszej ścieżki w grafie ważonym z dowolnego wierzchołka do wierzchołka spełniającego określony warunek zwany testem celu. Algorytm jest zupełny i optymalny, w tym sensie, że znajduje ścieżkę, jeśli tylko taka istnieje, i przy tym jest to ścieżka najkrótsza. Stosowany głównie w dziedzinie sztucznej inteligencji do rozwiązywania problemów i w grach komputerowych do imitowania inteligentnego zachowania. Algorytm został opisany pierwotnie w 1968 roku przez Petera Harta, Nilsa Nilssona oraz Bertrama Raphaela. W ich pracy naukowej został nazwany algorytmem A. Ponieważ jego użycie daje optymalne zachowanie dla danej heurystyki, nazwano go A*. (pl)
- A*, uitgesproken als A-star of A-ster, is een algoritme om in een graaf de kortste weg te vinden tussen twee knopen in die graaf. Het algoritme zoekt een pad van een beginknoop naar een eindknoop door middel van een heuristische schatting, die elke knoop rangschikt volgens een schatting van de beste route door die knoop. Het algoritme gaat de knopen in de zo bepaalde volgorde na. Het werd in 1968 voor het eerst beschreven door Peter Hart, Nils Nilsson en Bertram Raphael. (nl)
- Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет), и функции эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x)). Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. Этот алгоритм был впервые описан в 1968 году , и . Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Новый алгоритм достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*. Обобщением для него является двунаправленный эвристический алгоритм поиска. (ru)
- A* (uttalad "A star" eller "A-stjärna") är en sökalgoritm för att effektivt navigera genom knutpunkter i en graf. A* är känt för att vara effektiv och exakt och används ofta inom artificiell intelligens. A* använder en förlängning av Dijkstras algoritm. A* använder sig av heuristik för att effektivisera sökningen. Algoritmen beskrivs först år 1968 av Peter Hart, Nils Nilsson och Bertram Raphael på SRI-International (f.d ) i Förenta Staterna. (sv)
- Algoritmo A* (Lê-se: A-estrela) é um algoritmo para Busca de Caminho. Ele busca o caminho em um grafo de um vértice inicial até um vértice final. Ele é a combinação de aproximações heurísticas como do algoritmo Breadth First Search (Busca em Largura) e da formalidade do Algoritmo de Dijkstra. O algoritmo foi descrito pela primeira vez em 1968 por Peter Hart, Nils Nilsson, e Bertram Raphael. Na publicação deles, ele foi chamado de algoritmo A; usando este algoritmo com uma heurística apropriada atinge-se um comportamento ótimo, e passou a ser conhecido por A*. Sua aplicação vai desde aplicativos para encontrar rotas de deslocamento entre localidades a resolução de problemas, como a resolução de um quebra-cabeças. Ele é muito usado em jogos. (pt)
- Алгоритм пошуку А* («А зірочка» або англ. «A star») — належить до евристичних алгоритмів пошуку. Використовується для пошуку найкоротшого шляху між двома вершинами графу з додатніми вагами ребер. Описаний 1968 р. , та . Алгоритм використовує допоміжну функцію (евристику), аби скеровувати напрям пошуку та скорочувати його тривалість. Алгоритм повний в тому сенсі, що завжди знаходить оптимальний розв'язок, якщо він існує. (uk)
- A*搜索算法（A* search algorithm）是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於遊戲中的NPC的移動計算，或网络游戏的BOT的移動計算上。 该算法综合了和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。 在此算法中，如果以表示从起点到任意顶点的实际距离，表示任意顶点到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么A*算法的估算函数为： 这个公式遵循以下特性：
* 如果为0，即只计算任意顶点到目标的评估函数，而不计算起点到顶点的距离，则算法转化为使用贪心策略的，速度最快，但可能得不出最优解；
* 如果不大于顶点到目標頂點的實際距離，则一定可以求出最优解，而且越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；
* 如果为0，即只需求出起点到任意顶点的最短路径，而不计算任何评估函数，则转化为最短路问题问题，即Dijkstra算法，此时需要计算最多的顶点； (zh)
|
| rdfs:comment
|
- A* (A star) je počítačový algoritmus používaný pro vyhledávání optimálních cest v kladně ohodnocených grafech. Byl vytvořen v roce 1968 , a . Používá stejné principy jako Dijkstrův algoritmus, ale přidává navíc heuristický prvek. (cs)
- El algoritmo de búsqueda A* (pronunciado "A asterisco", "A estrella" o "A star" en inglés) se clasifica dentro de los algoritmos de búsqueda en grafos de tipo heurístico o informado. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo. (es)
- A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。最良優先探索を拡張したに、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの。h は ヒューリスティック関数と呼ばれる。 (ja)
- In informatica, A* (pronunciato /eɪ stɑːr/ in inglese) è un algoritmo di ricerca su grafi che individua un percorso da un dato nodo iniziale verso un dato nodo goal (o che passi un test di goal dato). Utilizza una "stima euristica" che classifica ogni nodo attraverso una stima della strada migliore che passa attraverso tale nodo. Visita il nodo in base a tale stima euristica. L'algoritmo A* è anche un esempio di ricerca best-first. L'algoritmo è stato descritto nel 1968 da , Nils Nilsson, e . (it)
- A*, uitgesproken als A-star of A-ster, is een algoritme om in een graaf de kortste weg te vinden tussen twee knopen in die graaf. Het algoritme zoekt een pad van een beginknoop naar een eindknoop door middel van een heuristische schatting, die elke knoop rangschikt volgens een schatting van de beste route door die knoop. Het algoritme gaat de knopen in de zo bepaalde volgorde na. Het werd in 1968 voor het eerst beschreven door Peter Hart, Nils Nilsson en Bertram Raphael. (nl)
- A* (uttalad "A star" eller "A-stjärna") är en sökalgoritm för att effektivt navigera genom knutpunkter i en graf. A* är känt för att vara effektiv och exakt och används ofta inom artificiell intelligens. A* använder en förlängning av Dijkstras algoritm. A* använder sig av heuristik för att effektivisera sökningen. Algoritmen beskrivs först år 1968 av Peter Hart, Nils Nilsson och Bertram Raphael på SRI-International (f.d ) i Förenta Staterna. (sv)
- Алгоритм пошуку А* («А зірочка» або англ. «A star») — належить до евристичних алгоритмів пошуку. Використовується для пошуку найкоротшого шляху між двома вершинами графу з додатніми вагами ребер. Описаний 1968 р. , та . Алгоритм використовує допоміжну функцію (евристику), аби скеровувати напрям пошуку та скорочувати його тривалість. Алгоритм повний в тому сенсі, що завжди знаходить оптимальний розв'язок, якщо він існує. (uk)
- A*搜索算法（A* search algorithm）是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於遊戲中的NPC的移動計算，或网络游戏的BOT的移動計算上。 该算法综合了和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。 在此算法中，如果以表示从起点到任意顶点的实际距离，表示任意顶点到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么A*算法的估算函数为： 这个公式遵循以下特性：
* 如果为0，即只计算任意顶点到目标的评估函数，而不计算起点到顶点的距离，则算法转化为使用贪心策略的，速度最快，但可能得不出最优解；
* 如果不大于顶点到目標頂點的實際距離，则一定可以求出最优解，而且越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；
* 如果为0，即只需求出起点到任意顶点的最短路径，而不计算任何评估函数，则转化为最短路问题问题，即Dijkstra算法，此时需要计算最多的顶点； (zh)
- خوارزمية البحث بأولوية الأفضل، (بالإنجليزية: A* search algorithm) هي تبسيط عن خوارزمية *A التي قدمها بيتر هارت في العام 1968. تستخدم هذه الخوارزمية الأدوات التالية: 1.
* قائمة (OPEN) للعقد التي ولدت وطبقت دالة الكشف (Heuristic Function) عليها ولكن لم تفحص بعد أي لم يتم توليد عقد تابعة منها. هذه القائمة هي من نوع صف تفضيل للأولوية (Priority Queue) حيث العقد ذات القيم الأعلى في دالة الكشف لها أولوية أكبر. 2.
* قائمة (CLOSED) للعقد التي فحصت وتم توليد العقد التابعة منها. هذه القائمة تبقى في الذاكرة لفحصها عند توليد عقد جديدة لمعرفة إن كانت مولدة سابقاً وتم المرور بها. 3.
* دالة الكشف (Heuristic Function) التي تخمن أحقية كل عقدة يتم توليدها. هذه الدالة تمكن الخوارزمية من البحث في الطرق الواعدة في الوصول للهدف أولاً. 4.
* الدالة g التي تقيس التكلفة للوصول من العقدة الابتدائية إلى العقد (ar)
- L'algorisme de cerca A* (en anglès, A-star algorithm) és un algorisme heurístic de cerca del camí més curt, molt eficient i generalitzable, motiu pel qual s'utilitza sovint en molts camps de la informàtica, com ara en la robòtica o en aplicacions com ara videojocs. (ca)
- A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases. (en)
- Der A*-Algorithmus („A Stern“ oder englisch „a star“, auch A*-Suche) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er wurde das erste Mal 1968 von , Nils J. Nilsson und beschrieben. Der Algorithmus gilt als Verallgemeinerung und Erweiterung des Dijkstra-Algorithmus, in vielen Fällen kann aber umgekehrt A* auch auf Dijkstra reduziert werden. (de)
- Algoritme A-Star (A*),(ditemukan pertama kali oleh Peter Hart, Nils Nilsson, dan Bertram Raphael pada tahun 1968) adalah algoritme pencarian rute terpendek (shortest path) yang merupakan perbaikan dari Algoritme BFS dengan memodifikasi fungsi heuristiknya untuk memberikan hasil yang optimal. Dimana menggabungkan fungsi heuristik [h(n)] dan jarak sesungguhnya/cost [g(n)]. Keterangan: (in)
- En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle. L'algorithme A* a été créé pour que la première solution trouvée soit l'une des meilleures, c'est pourquoi il est célèbre dans des applications comme les jeux vidéo privilégiant la vitesse de calcul sur l'exactitude des résultats. Cet algorithme a été proposé pour la première fois par Peter E. Hart, Nils John Nilsson et Bertram Raphael en 1968. Il s'agit d'une extension de l'algorithme de Dijkstra (fr)
- 정보과학 분야에 있어서, A* 알고리즘(A* algorithm 에이 스타 알고리즘[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나이다. 이 알고리즘은 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값 " 을 매기는 방법을 이용한다는 것이다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류할 수 있다. 이 알고리즘은 1968년 , , 이 처음 기술하였다. 그 3명의 논문에서, 이 알고리즘은 A 알고리즘(algorithm A)이라고 불렸다. 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 그러므로 A* 알고리즘이라고 불린다. A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지의 최적 경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 꼭짓점에 대한 평가 함수를 정의해야 한다. 이를 위한 평가 함수 은 다음과 같다. (ko)
- Algorytm A* – algorytm heurystyczny znajdowania najkrótszej ścieżki w grafie ważonym z dowolnego wierzchołka do wierzchołka spełniającego określony warunek zwany testem celu. Algorytm jest zupełny i optymalny, w tym sensie, że znajduje ścieżkę, jeśli tylko taka istnieje, i przy tym jest to ścieżka najkrótsza. Stosowany głównie w dziedzinie sztucznej inteligencji do rozwiązywania problemów i w grach komputerowych do imitowania inteligentnego zachowania. (pl)
- Algoritmo A* (Lê-se: A-estrela) é um algoritmo para Busca de Caminho. Ele busca o caminho em um grafo de um vértice inicial até um vértice final. Ele é a combinação de aproximações heurísticas como do algoritmo Breadth First Search (Busca em Largura) e da formalidade do Algoritmo de Dijkstra. O algoritmo foi descrito pela primeira vez em 1968 por Peter Hart, Nils Nilsson, e Bertram Raphael. Na publicação deles, ele foi chamado de algoritmo A; usando este algoritmo com uma heurística apropriada atinge-se um comportamento ótimo, e passou a ser conhecido por A*. (pt)
- Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. (ru)
|
