| dbo:abstract
|
- Uspořádané prohledávání (anglicky best-first search) je jeden z algoritmů na prohledávání stavového prostoru. Na rozdíl od prohledávání do hloubky, které vždy pokračuje v hledání v nejvzdálenějším dostupném stavu, a prohledávání do šířky, které pokračuje naopak z jednoho k počátku nejbližších stavů, funguje uspořádané prohledávání tak, že si z vrcholů k prohledávání vybere ten z hlediska hledaného stavu nejslibnější. Přirozená implementace uspořádaného prohledávání použije k ukládání prioritní frontu, zatímco prohledávání do šířky používá obyčejnou frontu a prohledávání do hloubky zásobník (obvykle se jedná v rámci rekurze o zásobník volání). Na rozdíl od dvou ostatních zmíněných algoritmů je uspořádané prohledávání algoritmem informovaným, neboť se při uspořádávání vrcholů opírá vstupní data. Ty mohou obsahovat známou cenu vrcholů nebo hran nebo heuristiku, kterou se odhaduje jejich slibnost. Zejména u čistě lokální heuristiky se tím také jedná o algoritmus hladový. Obdobnou myšlenku má nebo rozvíjí řada specializovanějších vyhledávacích algoritmů, například Dijkstrův algoritmus, A*, nebo paprskové prohledávání. Naopak na samotný algoritmus uspořádaného prohledávání se lze dívat jako na rozšíření gradientního prohledávání o paměť. (cs)
- أفضل-البحث الأول هو خوارزمية بحث تستكشف مجموعة البيانات (Graph) من خلال توسيع نطاق العقدة الأكثر نجاحاً أي الأكثر مطابقة لقاعدة محددة يتم البحث بواسطتها. يهودا بيرل وصف البحث الأول الأفضل من خلال تقدير تقدير نجاح تلك العقدة n «وذلك وفقاً لدالة تقييم إرشادية (heuristic evaluation function) والتي قد تعتمد بشكل عام على كل من: وصف n، وصف الهدف، المعلومات التي تم جمعها بواسطة البحث عن تلك النقطة، والأهم من ذلك كله، أي معلومات إضافية حول نطاق المعضلة (problem domain)» استخدم بعض الكتاب «البحث الأول-الأفضل» للإشارة على وجه التحديد إلى البحث بواسطة خوارزمية الكشف عن مجريات الأمور (heuristic) التي تحاول التنبؤ بمدى قرب نهاية الطريق من الحل، بحيث توسّع المسارات التي تعتبر أقرب إلى الحل للوصول إلى الحل بشكل أسرع. ويسمى هذا النوع من البحث بـ الأول-الأفضل الجشع أو البحث الإرشادي النقي (pure heuristic search) - بحث الكشف النقي عن مجريات الأمور. عادةً ما يتم تنفيذ كفاءة اختيار أفضل مرشح ليتم توسيعه باستخدام طابور الأولوية (priority queue). خوارزمية البحث بأولوية الأفضل هي مثال على البحث الأول-الأفضل (تعرف بـ A* بالإنجليزية)، أما الخوارزمية المعروفة بـ (B*) فهي تستخدم غالباً لإيجاد المسارات في (combinatorial search). ولا تعتبر أي من أ* أو ب* خوارزمية بحث أول-أفضل جشع حيث أن كلاهما لا تتناغمان مع المسافة المقطوعة من البداية مجموعة مع المسافات المقدرة نحو الهدف وهي صفة خوارزمية البحث الأول-الأفضل الجشع. (ar)
- Bestensuche (engl. best-first search) ist ein Algorithmus zum Durchsuchen eines Graphen, bei dem in jeder Iteration der vielversprechendste Knoten gewählt wird, bewertet nach einer gewissen Heuristik. Damit zählt er zu den informierten Such-Algorithmen. Judea Pearl beschrieb die Bestensuche als das Abschätzen der Kosten eines Knotens n nach einer "heuristischen Bewertungsfunktion , die im Allgemeinen abhängig von der Beschreibung von n ist, der Beschreibung des Ziels, den vom Algorithmus bis zu diesem Zeitpunkt gesammelten Informationen und vor allem vom Zusatzwissen über die Problemdomäne selbst." Um den vielversprechendsten Folgeknoten zu bestimmen, wird in konkreten Implementierungen oftmals eine Vorrangwarteschlange verwendet. Ein bekanntes Beispiel für die Bestensuche ist der A*-Algorithmus. Zur Wegfindung wird Bestensuche auch oftmals in der kombinatorischen Optimierung eingesetzt. (de)
- Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estimating the promise of node n by a "heuristic evaluation function which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most importantly, on any extra knowledge about the problem domain." Some authors have used "best-first search" to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution (or, goal), so that paths which are judged to be closer to a solution (or, goal) are extended first. This specific type of search is called greedy best-first search or pure heuristic search. Efficient selection of the current best candidate for extension is typically implemented using a priority queue. The A* search algorithm is an example of a best-first search algorithm, as is B*. Best-first algorithms are often used for path finding in combinatorial search. Neither A* nor B* is a greedy best-first search, as they incorporate the distance from the start in addition to estimated distances to the goal. (en)
- La recherche best-first (littéralement : le meilleur en premier) est un algorithme de recherche qui parcourt un graphe en explorant le nœud le plus "prometteur" selon une règle spécifique. Judea Pearl décrit la recherche best-first comme l'estimation de la qualité d'un nœud n par une "fonction heuristique d'évaluation qui, en général, peut dépendre de la description de n, de l'état d'arrivée, des informations amassées par l'algorithme au moment de l'évaluation et, surtout, de connaissances supplémentaires à propos du problème". Certains auteurs utilisent le terme best-first pour désigner spécifiquement une recherche dont l'heuristique essaie de prédire la distance entre la fin d'un chemin et la solution, de sorte à explorer en priorité le chemin le plus proche de la solution. Ce type précis de recherche est nommé best-first glouton. La sélection du meilleur candidat à l'exploration est typiquement implémentée en utilisant une file à priorités. L'algorithme A* est un exemple de recherche best-first. Ce type de recherche est souvent utilisée pour rechercher des chemins en optimisation combinatoire. (fr)
- 최상 우선 탐색은 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색하는 방법이다. (ko)
- Best-first search (letteralmente "ricerca prima il migliore") è una strategia di utilizzata per la risoluzione di problemi basati sulla ricerca ed è alla base dei moderni algoritmi di intelligenza artificiale. Rispetto alle strategie di , di cui si fa uso nel caso in cui non si hanno informazioni specifiche sugli stati del problema oltre la definizione del problema, la ricerca best-first, come tutte le altre strategie di ricerca informata, sfrutta la conoscenza di ulteriori dettagli sugli stati del problema da risolvere. Si presuppone che il problema sia rappresentato come un albero di ricerca, in cui ogni nodo rappresenta uno stato ben preciso del problema e i nodi foglia costituiscono gli stati obiettivi. La radice è lo stato iniziale del problema. Ogni singolo cammino dalla radice ad una qualsiasi foglia dell'albero rappresenta una soluzione al problema. L'obiettivo è quello di trovare la soluzione più efficiente in termini di velocità di esecuzione e di occupazione di memoria. La strategia di best-first search implementa un'apposita funzione di valutazione che ha il compito di selezionare, ad ogni passo della ricerca, il prossimo nodo da espandere. Ad ogni passo, dunque, tra tutti i nodi possibili da espandere l'algoritmo sceglie il nodo con la funzione di valutazione più bassa (da cui best-first). Una funzione di questo tipo viene generalmente detta euristica e ha il compito di selezionare, di volta in volta, il nodo che sembra condurre alla soluzione ottimale del problema. (it)
- 最良優先探索（さいりょうゆうせんたんさく、英: best-first search）は、幅優先探索（英: breadth-first search）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。 探索ノードを効率的に選択するには優先度付きキュー（英: priority queue）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。 最良優先探索の例としてはダイクストラ法（英: Dijkstra's algorithm）やA*アルゴリズム（英: A* search algorithm）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先探索を拡張した物が使われている。 (ja)
- O algoritmo de busca melhor-primeiro ou "best-first" usa a função heurística F(n)=h(n) de procura ao nó de destino. Esta procura expandir o nó que é mais próximo ao objetivo, implicando numa condução rápida até o nó destino. A heurística é aplicada globalmente, isto é, o caminho a ser seguido é selecionado entre todos os nós abertos até o momento, o nó aberto com a melhor nota é escolhido para a expansão. (pt)
- Поиск «лучший — первый» (англ. best-first search) — алгоритм поиска, исследующий граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом. Джуда Перл (англ. Judea Pearl) описал поиск «лучший — первый», взяв в качестве оценки узла значение некоторой «эвристической функции оценки , которая, вообще говоря, может зависеть от природы , описания цели, информации собранной поиском на данный момент и, самое главное, от каких-либо дополнительных знаний о предметной области». Некоторые авторы использовали поиск «лучший — первый» специально для описания поиска с эвристикой, служащей мерой близости к целевому состоянию, поэтому пути с лучшей эвристической оценкой рассматриваются первыми. Этот специфический тип поиска называется жадным поиском «лучший — первый». Эффективный выбор текущего лучшего кандидата для продолжения поиска может быть реализован с помощью очереди с приоритетом. Алгоритм поиска A* (А-звездочка) является примером оптимального поиска «лучший — первый». Алгоритм «лучший — первый» часто используются для поиска пути в комбинаторном поиске. (ru)
- По́шук «Найкра́щий — пе́рший» — це алгоритм пошуку, який досліджує граф шляхом розширення найперспективніших вузлів, які обираються відповідно до визначеного правила. (uk)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3773 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 최상 우선 탐색은 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색하는 방법이다. (ko)
- 最良優先探索（さいりょうゆうせんたんさく、英: best-first search）は、幅優先探索（英: breadth-first search）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。 探索ノードを効率的に選択するには優先度付きキュー（英: priority queue）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。 最良優先探索の例としてはダイクストラ法（英: Dijkstra's algorithm）やA*アルゴリズム（英: A* search algorithm）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先探索を拡張した物が使われている。 (ja)
- O algoritmo de busca melhor-primeiro ou "best-first" usa a função heurística F(n)=h(n) de procura ao nó de destino. Esta procura expandir o nó que é mais próximo ao objetivo, implicando numa condução rápida até o nó destino. A heurística é aplicada globalmente, isto é, o caminho a ser seguido é selecionado entre todos os nós abertos até o momento, o nó aberto com a melhor nota é escolhido para a expansão. (pt)
- По́шук «Найкра́щий — пе́рший» — це алгоритм пошуку, який досліджує граф шляхом розширення найперспективніших вузлів, які обираються відповідно до визначеного правила. (uk)
- أفضل-البحث الأول هو خوارزمية بحث تستكشف مجموعة البيانات (Graph) من خلال توسيع نطاق العقدة الأكثر نجاحاً أي الأكثر مطابقة لقاعدة محددة يتم البحث بواسطتها. يهودا بيرل وصف البحث الأول الأفضل من خلال تقدير تقدير نجاح تلك العقدة n «وذلك وفقاً لدالة تقييم إرشادية (heuristic evaluation function) والتي قد تعتمد بشكل عام على كل من: وصف n، وصف الهدف، المعلومات التي تم جمعها بواسطة البحث عن تلك النقطة، والأهم من ذلك كله، أي معلومات إضافية حول نطاق المعضلة (problem domain)» عادةً ما يتم تنفيذ كفاءة اختيار أفضل مرشح ليتم توسيعه باستخدام طابور الأولوية (priority queue). (ar)
- Uspořádané prohledávání (anglicky best-first search) je jeden z algoritmů na prohledávání stavového prostoru. Na rozdíl od prohledávání do hloubky, které vždy pokračuje v hledání v nejvzdálenějším dostupném stavu, a prohledávání do šířky, které pokračuje naopak z jednoho k počátku nejbližších stavů, funguje uspořádané prohledávání tak, že si z vrcholů k prohledávání vybere ten z hlediska hledaného stavu nejslibnější. Přirozená implementace uspořádaného prohledávání použije k ukládání prioritní frontu, zatímco prohledávání do šířky používá obyčejnou frontu a prohledávání do hloubky zásobník (obvykle se jedná v rámci rekurze o zásobník volání). Na rozdíl od dvou ostatních zmíněných algoritmů je uspořádané prohledávání algoritmem informovaným, neboť se při uspořádávání vrcholů opírá vstupní d (cs)
- Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estimating the promise of node n by a "heuristic evaluation function which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most importantly, on any extra knowledge about the problem domain." Efficient selection of the current best candidate for extension is typically implemented using a priority queue. (en)
- Bestensuche (engl. best-first search) ist ein Algorithmus zum Durchsuchen eines Graphen, bei dem in jeder Iteration der vielversprechendste Knoten gewählt wird, bewertet nach einer gewissen Heuristik. Damit zählt er zu den informierten Such-Algorithmen. Um den vielversprechendsten Folgeknoten zu bestimmen, wird in konkreten Implementierungen oftmals eine Vorrangwarteschlange verwendet. Ein bekanntes Beispiel für die Bestensuche ist der A*-Algorithmus. Zur Wegfindung wird Bestensuche auch oftmals in der kombinatorischen Optimierung eingesetzt. (de)
- La recherche best-first (littéralement : le meilleur en premier) est un algorithme de recherche qui parcourt un graphe en explorant le nœud le plus "prometteur" selon une règle spécifique. Judea Pearl décrit la recherche best-first comme l'estimation de la qualité d'un nœud n par une "fonction heuristique d'évaluation qui, en général, peut dépendre de la description de n, de l'état d'arrivée, des informations amassées par l'algorithme au moment de l'évaluation et, surtout, de connaissances supplémentaires à propos du problème". (fr)
- Best-first search (letteralmente "ricerca prima il migliore") è una strategia di utilizzata per la risoluzione di problemi basati sulla ricerca ed è alla base dei moderni algoritmi di intelligenza artificiale. Rispetto alle strategie di , di cui si fa uso nel caso in cui non si hanno informazioni specifiche sugli stati del problema oltre la definizione del problema, la ricerca best-first, come tutte le altre strategie di ricerca informata, sfrutta la conoscenza di ulteriori dettagli sugli stati del problema da risolvere. (it)
- Поиск «лучший — первый» (англ. best-first search) — алгоритм поиска, исследующий граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом. Джуда Перл (англ. Judea Pearl) описал поиск «лучший — первый», взяв в качестве оценки узла значение некоторой «эвристической функции оценки , которая, вообще говоря, может зависеть от природы , описания цели, информации собранной поиском на данный момент и, самое главное, от каких-либо дополнительных знаний о предметной области». (ru)
|
| rdfs:label
|
- بحث أول-أفضل (ar)
- Uspořádané prohledávání (cs)
- Bestensuche (de)
- Best-first search (en)
- Algorithme de recherche best-first (fr)
- Best-first search (it)
- 최상 우선 탐색 (ko)
- 最良優先探索 (ja)
- Поиск по первому наилучшему совпадению (ru)
- Best-first Search (pt)
- Пошук за першим найкращим збігом (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |