Bidirectional search (original) (raw)
Двунаправленный поиск пути в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в формировании процесса поиска от начальной (прямой поиск) и от конечной вершины (обратный поиск) графа.
| Property | Value |
|---|---|
| dbo:abstract | Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor b, and the distance from start to goal is d, each of the two searches has complexity O(bd/2) (in Big O notation), and the sum of these two search times is much less than the O(bd) complexity that would result from a single search from the beginning to the goal. Andrew Goldberg and others explained the correct termination conditions for the bidirectional version of Dijkstra’s Algorithm. As in A* search, bi-directional search can be guided by a heuristic estimate of the remaining distance to the goal (in the forward tree) or from the start (in the backward tree). Ira Pohl was the first one to design and implement a bi-directional heuristic search algorithm. Search trees emanating from the start and goal nodes failed to meet in the middle of the solution space. The BHFFA algorithm fixed this defect Champeaux (1977). A solution found by the uni-directional A* algorithm using an admissible heuristic has a shortest path length; the same property holds for the BHFFA2 bidirectional heuristic version described in de Champeaux (1983). BHFFA2 has, among others, more careful termination conditions than BHFFA. (en) In der Informatik zählt die Bidirektionale Suche zu den Suchverfahren, spezieller zu den uninformierten Suchverfahren. Wie der A*-Algorithmus und der Dijkstra-Algorithmus ermittelt ein solches Verfahren den Teil eines Graphen der bestimmte Eigenschaften, wie kürzester Weg zwischen zwei gegebenen Knoten (Kürzester Pfad) aufweist. Bei diesem Lösungsverfahren werden zwei Suchen simultan gestartet, jeweils eine an den beiden gegebenen Knoten. Die Suchvorgänge sind gegensätzlich gerichtet, das Verfahren ist abgeschlossen, wenn sich die zwei Teilgraphen kreuzen. Der bidirektionalen Suche liegt der Wunsch nach Verringerung der Komplexität zu Grunde. Dem steht ein erhöhter Aufwand durch die Prüfung auf Aufeinandertreffen der Teilgraphen gegenüber, auch kann das Rückwärts laufen lassen der zweiten Suche die Realisierung erschweren. Und zur Erzielung einer Zeitersparnis müssen die beiden Vorgänge parallel implementiert werden. Daher ist das bidirektionale Verfahren nur selten und unter bestimmten Bedingungen wie dem Fehlen einer geeigneten Heuristik dem A*-Algorithmus vorzuziehen. (de) 双方向探索（英: bidirectional search）とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する。それぞれの探索の計算量は （ランダウの記号）であり、両方を合わせても となり、一方向から全部の探索を行った場合の よりも効率がよい。 しかし、よいことばかりではない。並列に2つの探索を行う複雑さは別として、探索木をどう拡張していくかを各ステップで決定する必要がある。また、最終状態から逆方向に探索できる状況は限られているし、事前に用意が必要になる場合もある。また、2つの探索木の交差を見つける効率的方法も必要になる。このような問題があるため、うまいヒューリスティックがあるならA*の方がよい選択となることが多い。 双方向探索でもヒューリスティックを使うことができる。A*について証明されているように、許容的ヒューリスティックによって最短解が得られる場合がある。 拡張されるノードは、オープンなノード数が最も少なく最も見込みがある最先端から選ばれる。そのようなノードがもう一方の最先端にもある時に、アルゴリズムは終了する。子ノードのf値の計算に当たっては、もう一方の最先端の全てのオープンなノードのg値を考慮しなければならない。そのため、ノードの拡張はA*よりも計算量が多くなる。訪れるノードの数は上で概説したように少なくなることが期待できる。従って、個々の計算量が多くても調べるノード数が少なくなる。参考文献に示した1977年の文献では、A*では解けなかった問題を双方向探索で解いた例が示されている。許容的でないヒューリスティックを使った場合でもより短い経路が見つかっている。これらの検証は Ira Pohl が15パズルで行った。 Ira Pohl は、世界で初めて双方向ヒューリスティック探索アルゴリズムを設計・実装した。最先端の子ノードは、もう一方の側のターゲットについてだけ評価していた。彼の報告によれば、2つの探索木は相手と交差したことを検出できなかったという。 (ja) Двунаправленный поиск пути в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в формировании процесса поиска от начальной (прямой поиск) и от конечной вершины (обратный поиск) графа. (ru) Двонапра́влений по́шук — ускладнений алгоритм пошуку ушир або пошуку углиб, в основі якого лежить така ідея, що можна одночасно проводити два пошуки (в прямому напрямку, від початкового стану, та у зворотному напрямку, від цілі), зупиняючись після того, як два процеси пошуку зустрінуться на середині (Рис. 1). (uk) 双向搜索算法是一种图的遍历算法，用于在中搜索从一个顶点到另一个顶点的最短路径。算法同时运行两个搜索：一个从初始状态正向搜索，另一个从目标状态反向搜索，当两者在中间汇合时搜索停止。在很多情况下该算法更快，假设搜索一棵分支因子b的树，初始节点到目标节点的距离为d，该算法的正向和反向搜索复杂度都是O(bd/2) (大O符号)，两者相加后远远小于普通的单项搜索算法（复杂度为O(bd)）。 在A*搜尋演算法中，双向搜索的可以定义为：正向搜索为到目标节点的距离，反向搜索为到初始节点的距离。 Ira Pohl （）第一个设计并实现了双向启发式搜索算法。Andrew Goldberg和其他人解释了双向搜索版的戴克斯特拉算法的正确完结条件。 (zh) |
| dbo:wikiPageID | 3157516 (xsd:integer) |
| dbo:wikiPageLength | 8186 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1029918810 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Search_algorithms dbr:Branching_factor dbr:Andrew_V._Goldberg dbr:Shortest_path dbr:State_space_search dbc:Graph_algorithms dbr:Tree_(graph_theory) dbr:A*_search_algorithm dbr:Fifteen_puzzle dbr:Directed_graph dbr:Journal_of_the_ACM dbr:Big_O_notation dbr:Heuristic_(computer_science) dbr:Artificial_Intelligence:_A_Modern_Approach dbr:Graph_search_algorithm dbr:Vertex_(graph_theory) dbr:Dijkstra’s_Algorithm dbr:BHFFA dbr:Bidirectional_Heuristic_Front-to-Front_Algorithm |
| dbp:wikiPageUsesTemplate | dbt:Graph_search_algorithm dbt:Citation dbt:Math dbt:Mvar dbt:Reflist dbt:Harvs |
| dcterms:subject | dbc:Search_algorithms dbc:Graph_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software 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 | Двунаправленный поиск пути в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в формировании процесса поиска от начальной (прямой поиск) и от конечной вершины (обратный поиск) графа. (ru) Двонапра́влений по́шук — ускладнений алгоритм пошуку ушир або пошуку углиб, в основі якого лежить така ідея, що можна одночасно проводити два пошуки (в прямому напрямку, від початкового стану, та у зворотному напрямку, від цілі), зупиняючись після того, як два процеси пошуку зустрінуться на середині (Рис. 1). (uk) 双向搜索算法是一种图的遍历算法，用于在中搜索从一个顶点到另一个顶点的最短路径。算法同时运行两个搜索：一个从初始状态正向搜索，另一个从目标状态反向搜索，当两者在中间汇合时搜索停止。在很多情况下该算法更快，假设搜索一棵分支因子b的树，初始节点到目标节点的距离为d，该算法的正向和反向搜索复杂度都是O(bd/2) (大O符号)，两者相加后远远小于普通的单项搜索算法（复杂度为O(bd)）。 在A*搜尋演算法中，双向搜索的可以定义为：正向搜索为到目标节点的距离，反向搜索为到初始节点的距离。 Ira Pohl （）第一个设计并实现了双向启发式搜索算法。Andrew Goldberg和其他人解释了双向搜索版的戴克斯特拉算法的正确完结条件。 (zh) Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor b, and the distance from start to goal is d, each of the two searches has complexity O(bd/2) (in Big O notation), and the sum of these two search times is much less than the O(bd) complexity that would result from a single search from the beginning to the goal. (en) In der Informatik zählt die Bidirektionale Suche zu den Suchverfahren, spezieller zu den uninformierten Suchverfahren. Wie der A*-Algorithmus und der Dijkstra-Algorithmus ermittelt ein solches Verfahren den Teil eines Graphen der bestimmte Eigenschaften, wie kürzester Weg zwischen zwei gegebenen Knoten (Kürzester Pfad) aufweist. Bei diesem Lösungsverfahren werden zwei Suchen simultan gestartet, jeweils eine an den beiden gegebenen Knoten. Die Suchvorgänge sind gegensätzlich gerichtet, das Verfahren ist abgeschlossen, wenn sich die zwei Teilgraphen kreuzen. (de) 双方向探索（英: bidirectional search）とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する。それぞれの探索の計算量は （ランダウの記号）であり、両方を合わせても となり、一方向から全部の探索を行った場合の よりも効率がよい。 しかし、よいことばかりではない。並列に2つの探索を行う複雑さは別として、探索木をどう拡張していくかを各ステップで決定する必要がある。また、最終状態から逆方向に探索できる状況は限られているし、事前に用意が必要になる場合もある。また、2つの探索木の交差を見つける効率的方法も必要になる。このような問題があるため、うまいヒューリスティックがあるならA*の方がよい選択となることが多い。 双方向探索でもヒューリスティックを使うことができる。A*について証明されているように、許容的ヒューリスティックによって最短解が得られる場合がある。 Ira Pohl は、世界で初めて双方向ヒューリスティック探索アルゴリズムを設計・実装した。最先端の子ノードは、もう一方の側のターゲットについてだけ評価していた。彼の報告によれば、2つの探索木は相手と交差したことを検出できなかったという。 (ja) |
| rdfs:label | Bidirektionale Suche (de) Bidirectional search (en) 双方向探索 (ja) Двунаправленный поиск (ru) Двонаправлений пошук (uk) 双向搜索 (zh) |
| owl:sameAs | freebase:Bidirectional search wikidata:Bidirectional search dbpedia-de:Bidirectional search dbpedia-fa:Bidirectional search dbpedia-hu:Bidirectional search dbpedia-ja:Bidirectional search dbpedia-ru:Bidirectional search dbpedia-simple:Bidirectional search dbpedia-sr:Bidirectional search dbpedia-th:Bidirectional search dbpedia-uk:Bidirectional search dbpedia-zh:Bidirectional search https://global.dbpedia.org/id/4nJAV yago-res:Bidirectional search |
| prov:wasDerivedFrom | wikipedia-en:Bidirectional_search?oldid=1029918810&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Bidirectional_search |
| is dbo:wikiPageRedirects of | dbr:Bi-directional_search |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:GraphHopper dbr:Shortest_path_problem dbr:Held–Karp_algorithm dbr:A*_search_algorithm dbr:Dijkstra's_algorithm dbr:Transit_node_routing dbr:Bi-directional_search |
| is foaf:primaryTopic of | wikipedia-en:Bidirectional_search |