Aké sú výhody a nevýhody používania obojsmerného algoritmu vyhľadávania pri ceste?

obojsmerné a* vyhľadávanie:výhody a nevýhody

Obojsmerné a* Vyhľadávanie je algoritmus prenosu, ktorého cieľom je zlepšiť efektívnosť štandardného algoritmu A* súčasným vyhľadávaním zo štartovacích a cieľových uzlov. Preskúmajme jeho výhody a nevýhody:

Výhody:

* potenciálne rýchlejšie: V mnohých scenároch môže obojsmerná a* nájsť optimálnu cestu výrazne rýchlejšiu ako štandard a*. Je to preto, že znižuje vyhľadávací priestor. Pomyslite na to, že dva tímy kopajú tunel z opačných strán hory. Stretávajú sa v strede, ktorý trvá menej času ako jeden tím, ktorý kopá celý tunel. A* vyhľadáva iba od začiatku.

* Menší vyhľadávací priestor: Hľadaním z oboch smerov algoritmus zvyčajne rozširuje menej uzlov celkovo, aby našla optimálnu cestu. Fronty vyhľadávania „stretávajú sa v strede“, čím sa znižuje požadovaný prieskum. Štandard A* musí často skúmať výrazne väčšiu časť vyhľadávacieho priestoru pred dosiahnutím cieľa, najmä vo veľkých alebo zložitých prostrediach.

* sa zaoberá problémami s neznámym koncovým bodom dobre:​​ Zatiaľ čo štandard A* musí poznať presné umiestnenie cieľa, obojsmerné a* sa dá prispôsobiť scenárom, v ktorých je cieľový región menej presný. Algoritmus sa môže zastaviť, keď sa tieto dve fronty vyhľadávania prekrývajú alebo sú dostatočne blízko. Je to užitočné v situáciách, keď sa napríklad snažíte nájsť * akýkoľvek * výstup z bludiska, nie konkrétny.

* Potenciálne nižšie využitie pamäte (v závislosti od implementácie): Aj keď obidve vyžadujú pamäť, menší vyhľadávací priestor * potenciálne * prekladá do nižšej využitia pamäte. Platí to najmä vo veľmi veľkých grafoch, kde môžu byť významné úspory zo zníženej expanzie uzlov. Môže však tiež vyžadovať * viac * pamäte v niektorých scenároch v závislosti od toho, ako implementujete dátové štruktúry na sledovanie hraníc.

Nevýhody:

* zložitosť implementácie: Implementácia obojsmerného a* je zložitejšia ako implementácia štandardného a*. Vyžaduje si to správu dvoch samostatných hraníc vyhľadávania (jedna od začiatku, jedna od cieľa), koordinuje ich rozšírenie a určuje, kedy sa tieto dve vyhľadávania „splnili“. Táto zložitosť môže zvýšiť čas rozvoja a zaviesť viac príležitostí na chyby.

* Obtiažnosť podmienok stretnutia: Určenie presnej „podmienky stretnutia“ medzi týmito dvoma frontami vyhľadávania môže byť zložité. Jednoducho nájdenie spoločného uzla nezaručuje optimálnu cestu. Musíte zaistiť kombináciu ciest od začiatku do spoločného uzla a od spoločného uzla k cieľu vám poskytne najkratšiu celkovú cestu. To často zahŕňa kontrolu hodnôt „G` (náklady na dosiahnutie uzla) z oboch vyhľadávaní a potenciálne pokračovanie hľadania trochu dlhšie na potvrdenie optimality.

* vyžaduje reverzibilné akcie/prechody: Obojstranná A* sa spolieha na to, že bude môcť vyhľadávať* dozadu* od cieľa po začiatok. To znamená, že musíte byť schopní definovať „spätnú“ každej akcie alebo prechodu stavu vo vyhľadávacom priestore. Ak vaša problémová doména zahŕňa ireverzibilné akcie (napr. Určité ireverzibilné chemické reakcie alebo dráha na riadenom grafe, kde sú niektoré hrany jednosmerné), nemožno priamo uplatniť obojsmerné a*.

* Heuristické úvahy: Heuristická funkcia použitá pri oboch vyhľadávaniach musí byť konzistentná (tiež nazývaná prípustná a monotónna). To môže byť ťažšie dosiahnuť, ako len mať prípustnú heuristiku. Nekonzistentná heuristika môže viesť k obojsmernému a* nájdeniu suboptimálnych ciest alebo správneho ukončenia. Heuristika nesmie preceňovať náklady *od uzla k cieľu *.

* Potenciál zvýšeného využitia pamäte (v niektorých prípadoch): Aj keď často znižuje vyhľadávací priestor, potreba udržiavania dvoch samostatných hraníc vyhľadávania môže * niekedy * zvýšiť využitie pamäte, najmä ak sú hranice veľké a zložité. Je to menej pravdepodobné ako celkové zníženie využitia pamäte, ale malo by sa zvážiť.

* Výkon môže byť vysoko variabilný: Zlepšenie výkonnosti obojsmerného a* nad štandardným A* je vysoko závislé od konkrétneho problému a kvality heuristickej funkcie. V niektorých prípadoch by to mohlo fungovať iba okrajovo lepšie alebo ešte horšie ako štandard A*.

v súhrne:

Obojsmerná a* je výkonná technika na zlepšenie účinnosti dráhy, najmä vo veľkých vyhľadávacích priestoroch. Jeho pridaná zložitosť a požiadavky (napríklad reverzibilné akcie a konzistentná heuristika) však robia správne implementáciu a efektívne uplatňovanie. Starostlivo zvážte charakteristiky vašej problémovej oblasti, aby ste zistili, či potenciálne prínosy obojsmerného a* prevažujú nad jej nevýhodami. Ak máte dobre definovaný problém s reverzibilnými akciami, konzistentnou heuristikou a veľkým vyhľadávacím priestorom, oplatí sa preskúmať obojsmerná a*.

• Predchádzajúca strana: Aké je heslo pre všetky smerovače Linksys? 
• Ďalšia strana: Aký je najrýchlejší algoritmus cesty na nájdenie najúčinnejšej trasy medzi dvoma bodmi?