A* search algorithm (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/SRI_Shakey_with_callouts.jpg?width=300 |
| dbo:wikiPageExternalLink | https://briangrinstead.com/blog/astar-search-algorithm-in-javascript-updated/ http://theory.stanford.edu/~amitp/GameProgramming/ https://archive.org/details/principlesofarti00nils https://web.archive.org/web/20090917155722/http:/www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf https://web.archive.org/web/20200215174913/https:/briangrinstead.com/blog/astar-search-algorithm-in-javascript-updated/ |
| dbo:wikiPageID | 100558 (xsd:integer) |
| dbo:wikiPageLength | 36432 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1113605932 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Natural_language_processing dbr:Parsing dbr:Bertram_Raphael dbr:Binary_heap dbr:Branch_and_bound dbr:Algorithm dbr:Any-angle_path_planning dbr:Anytime_A* dbr:Best-first_search dbr:Pathfinding dbr:D* dbr:Depth-first_search dbr:Incremental_heuristic_search dbr:Lifelong_Planning_A* dbr:LIFO_(computing) dbr:Shakey_the_robot dbc:Combinatorial_optimization dbc:Search_algorithms dbr:SRI_International dbr:Fringe_search dbr:Graph_(data_structure) dbr:Branching_factor dbr:Consistent_heuristic dbr:Theta* dbr:Logarithm dbr:Stochastic_context-free_grammar dbr:Computational_complexity_theory dbr:Priority_queue dbc:Articles_with_example_pseudocode dbc:Game_artificial_intelligence dbc:Graph_algorithms dbc:Graph_distance dbc:Greedy_algorithms dbc:Routing_algorithms dbr:Admissible_heuristic dbr:Tree_(data_structure) dbr:Weighted_graph dbr:Jump_point_search dbr:Dynamic_programming dbr:Breadth-first_search dbr:Graph_traversal dbr:Iterative_deepening_A* dbr:Reachability dbr:Hash_table dbr:Bidirectional_search dbr:Heuristic dbr:Heuristic_(computer_science) dbr:Reduced_cost dbr:Dijkstra's_algorithm dbr:Fibonacci_heap dbr:Great-circle_distance dbr:Greedy_algorithm dbr:Polynomial_time dbr:Search_algorithm dbr:Manhattan_distance dbr:SMA* dbr:Euclidean_distance dbr:Exponential_time dbr:Pseudocode dbr:Peter_E._Hart dbr:Space_complexity dbr:Nils_Nilsson_(researcher) dbr:Travel-routing_system dbr:Amortized_time dbr:Informed_search_algorithm dbr:Node_(graph_theory) dbr:File:A*_Search_Example_on_North_American_Freight_Train_Network.gif dbr:File:A_Star_Algorithm.webm dbr:File:AstarExampleEn.gif dbr:File:Astar_progress_animation.gif dbr:File:Astarpathfinding.gif dbr:File:SRI_Shakey_with_callouts.jpg dbr:File:Weighted_A_star_with_eps_5.gif dbr:Fringe_(Computer_science) dbr:Open_set_(Computer_science) |
| dbp:class | dbr:Search_algorithm |
| dbp:data | dbr:Graph_(data_structure) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Cite_book dbt:Cite_web dbt:Efn dbt:Math dbt:Mvar dbt:Notelist dbt:Reference_needed dbt:Reflist dbt:See_also dbt:Short_description dbt:Tmath dbt:Infobox_algorithm dbt:Tree_search_algorithm |
| dct:subject | dbc:Combinatorial_optimization dbc:Search_algorithms dbc:Articles_with_example_pseudocode dbc:Game_artificial_intelligence dbc:Graph_algorithms dbc:Graph_distance dbc:Greedy_algorithms dbc:Routing_algorithms |
| rdf:type | owl:Thing yago:WikicatRoutingAlgorithms yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| 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) |
| rdfs:label | خوارزمية البحث بأولوية الأفضل (ar) Algorisme de cerca A* (ca) A* (cs) A*-Algorithmus (de) A* search algorithm (en) Algoritmo de búsqueda A* (es) Algoritma a-star (in) Algoritmo A* (it) Algorithme A* (fr) A* 알고리즘 (ko) A* (ja) A*-algoritme (nl) Algorytm A* (pl) Algoritmo A* (pt) A* (ru) A* Sökalgoritm (sv) Алгоритм пошуку A* (uk) A*搜尋演算法 (zh) |
| rdfs:seeAlso | dbr:Dijkstra's_algorithm |
| owl:sameAs | freebase:A* search algorithm yago-res:A* search algorithm dbpedia-commons:A* search algorithm wikidata:A* search algorithm dbpedia-ar:A* search algorithm dbpedia-bg:A* search algorithm dbpedia-ca:A* search algorithm dbpedia-cs:A* search algorithm dbpedia-de:A* search algorithm dbpedia-es:A* search algorithm dbpedia-fa:A* search algorithm dbpedia-fi:A* search algorithm dbpedia-fr:A* search algorithm dbpedia-he:A* search algorithm dbpedia-hu:A* search algorithm http://hy.dbpedia.org/resource/Ա* dbpedia-id:A* search algorithm dbpedia-it:A* search algorithm dbpedia-ja:A* search algorithm dbpedia-ko:A* search algorithm dbpedia-nl:A* search algorithm dbpedia-no:A* search algorithm dbpedia-pl:A* search algorithm dbpedia-pt:A* search algorithm dbpedia-ru:A* search algorithm dbpedia-simple:A* search algorithm dbpedia-sr:A* search algorithm dbpedia-sv:A* search algorithm dbpedia-th:A* search algorithm dbpedia-tr:A* search algorithm dbpedia-uk:A* search algorithm dbpedia-vi:A* search algorithm dbpedia-zh:A* search algorithm https://global.dbpedia.org/id/2ak7M |
| prov:wasDerivedFrom | wikipedia-en:A*_search_algorithm?oldid=1113605932&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/A*_Search_Example_on_North_American_Freight_Train_Network.gif wiki-commons:Special:FilePath/AstarExampleEn.gif wiki-commons:Special:FilePath/Astar_progress_animation.gif wiki-commons:Special:FilePath/Astarpathfinding.gif wiki-commons:Special:FilePath/SRI_Shakey_with_callouts.jpg wiki-commons:Special:FilePath/Weighted_A_star_with_eps_5.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:A*_search_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:A_(disambiguation) dbr:A* |
| is dbo:wikiPageRedirects of | dbr:TBA* dbr:New_Bidirectional_A* dbr:A*_algorithm dbr:A*_search dbr:A-star dbr:A-star_algorithm dbr:A-star_search_algorithm dbr:A_Star dbr:A_Star_Search_Algorithm dbr:A_star_search dbr:A_star_search_algorithm |
| is dbo:wikiPageWikiLink of | dbr:A_(disambiguation) dbr:Protein_design dbr:List_of_algorithms dbr:Monotonic_function dbr:Progol dbr:Bertram_Raphael dbr:Branch_and_bound dbr:Any-angle_path_planning dbr:Anytime_A* dbr:Best-first_search dbr:List_of_SRI_International_people dbr:Pathfinding dbr:D* dbr:Incremental_heuristic_search dbr:Lifelong_Planning_A* dbr:Shakey_the_robot dbr:15_puzzle dbr:General_Problem_Solver dbr:Online_analytical_processing dbr:Timeline_of_algorithms dbr:Fringe_search dbr:Geoffrey_J._Gordon dbr:GraphHopper dbr:Myth:_The_Fallen_Lords dbr:Consistent_heuristic dbr:Theta* dbr:Navigation_mesh dbr:State_space dbr:Vector_Field_Histogram dbr:Shlomo_Zilberstein dbr:Shortest_path_problem dbr:Combinatorial_search dbr:Priority_queue dbr:Spanning_tree dbr:TBA* dbr:Micromouse dbr:Viterbi_algorithm dbr:Admissible_heuristic dbr:Jump_point_search dbr:Dwarf_Fortress dbr:F.E.A.R._(video_game) dbr:Nils_John_Nilsson dbr:Goal_node_(computer_science) dbr:Graph_edit_distance dbr:Hill_climbing dbr:Iterative_deepening_A* dbr:Journey_planner dbr:Knowledge_representation_and_reasoning dbr:A* dbr:Asterisk dbr:ASD_OptiPlant dbr:John_Gerrard_(artist) dbr:Bidirectional_search dbr:Symbolic_artificial_intelligence dbr:Collaborative_diffusion dbr:Dijkstra's_algorithm dbr:Artificial_intelligence_in_video_games dbr:B* dbr:Greedy_algorithm dbr:Astar_(disambiguation) dbr:Search_algorithm dbr:Lost_Souls_(MUD) dbr:Routing dbr:SMA* dbr:SSS* dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Tree_alignment dbr:Motion_planning dbr:Multi-agent_pathfinding dbr:Outline_of_artificial_intelligence dbr:Peter_E._Hart dbr:Rapidly-exploring_random_tree dbr:New_Bidirectional_A* dbr:A*_algorithm dbr:A*_search dbr:A-star dbr:A-star_algorithm dbr:A-star_search_algorithm dbr:A_Star dbr:A_Star_Search_Algorithm dbr:A_star_search dbr:A_star_search_algorithm |
| is foaf:primaryTopic of | wikipedia-en:A*_search_algorithm |
