Căutare bidirecțională

Căutarea bidirecțională pe lățime (sau adâncime) [1] [2] este un algoritm sofisticat de căutare pe lățime (sau adâncime ) , ideea căruia este de a forma un proces de căutare de la începutul ( căutare înainte ) și de la vârful final ( revers ). căutare ) a graficului .

Idee

Găsirea căii dorite se reduce la determinarea căilor de la inițial la unele intermediare și de la acesta până la vârful final. Implementat prin verificarea unuia sau ambelor procese atunci când o frunză a unui arbore de căutare se potrivește cu o frunză a altuia, după care sunt extrase căile către acel element. Conectând căile obținem calea dorită. Dacă două căutări sunt efectuate în paralel  , acest lucru economisește și mai mult timp pentru a obține calea dorită, comparativ cu o căutare unidirecțională.

Avantaje și dezavantaje

• Performanță crescută;
• Aveți nevoie de memorie pentru a stoca arborele de căutare, astfel încât să puteți verifica dacă o frunză aparține altui arbore.

Scorul de dificultate

Complexitatea întregului algoritm este estimată ca suma complexității căutărilor înainte și înapoi, verificarea apartenenței egală cu o operație, timp constant (O (n)), acces la tabelul hash .

Numărarea numărului de operații

Prea dependent de situația specifică dacă căutarea nu este pe un arbore n-ari .

Complexitatea asimptotică a numărului tot mai mare de operații

• Dacă sunt cunoscute singurele elemente inițiale și țintă specifice, atunci complexitatea timpului asimptotic a căutărilor înainte și înapoi este egală cu , de unde totalul - + , care este mult mai mic decât . Complexitatea asimptotică spațială , în locul celei directe, deoarece trebuie stocată în memorie.
• Dacă se cunosc un anumit element de pornire și un set de elemente, dintre care unul este elementul țintă.

Evaluare statistică

Căutarea bidirecțională, având în vedere un singur element de început și de sfârșit, poate îmbunătăți căutarea unidirecțională pe lățimea întâi, de obicei cu un factor de 2. Cel mai dificil caz pentru o căutare bidirecțională este o astfel de problemă în care este dată doar o descriere implicită a unui set (posibil foarte mare) de stări țintă pentru a verifica scopul, de exemplu, toate stările corespunzătoare șahmat-ului obiectivului „Șah”. „la șah . În căutarea inversă, ar fi necesar să se creeze descrieri compacte ale tuturor stărilor care permit șahmat cu mișcări etc.; iar aceste descrieri ar trebui verificate în raport cu stările generate de căutarea directă. Nu există o modalitate generală de a rezolva eficient o astfel de problemă.

Algoritm de căutare bidirecțională

Algoritmul constă din:

• căutare directă, similară căutării unice;
• căutare inversă;
• operații pentru a determina dacă o frunză aparține unui alt arbore de căutare.

Complexitatea implementării

Complexitatea implementării constă în algoritmul de căutare inversă.

Exemple de implementare

Aplicație practică

Vezi și

• Lățimea prima căutare
• Profunzime prima căutare

Note

1. ↑ Altele: căutare bidirecțională a elementului - efectuată în liste bidirecționale sau circulare de la elementul dorit în ambele direcții.
2. ↑ [1]  (downlink) Acest algoritm este complet și optim (cu costuri de pași uniforme) dacă ambele procese de căutare sunt pe primul loc; alte combinații de metode pot lipsi completitatea, optimitatea sau ambele.

Link -uri

• Algoritmi de căutare pe pmg.org.ru
• Modele și metode de rezolvare a problemelor pe Mari El.ru
• Implementarea C++ (aisearch.tgz) la www.cs.cmu.edu

Literatură

• Stuart Russell și Peter Norvig. Partea 2. Rezolvarea problemelor // Inteligența artificială (abordare modernă) = inteligență artificială (abordare modernă). - Ed. a II-a. - FGUP. „Cortea de tipărire” A.M. Gorky: Williams, 2006. - S. 135-136. — ISBN 5-8459-0887-6 .