Kétirányú keresés

A kétirányú szélességi (vagy mélységi) keresés [1] [2] egy kifinomult szélességi (vagy mélységi ) keresési algoritmus , amelynek az az ötlete, hogy keresési folyamatot hozzon létre a kezdeti ( előre keresés ) és a végső csúcsból ( fordított keresés ) keresés ) a grafikonon .

Ötlet

A kívánt útvonal megtalálása a kezdeti szakasztól valamilyen közteshez, és onnan a végső csúcsig vezető utak meghatározásához vezet. Az egyik vagy mindkét folyamat ellenőrzésével valósítható meg, amikor az egyik keresési fa levele megegyezik egy másik levelével, majd kivonja az adott elemhez vezető útvonalakat. Az utakat összekötve megkapjuk a kívánt utat. Ha két keresést párhuzamosan hajtanak végre  , az egyirányú kereséshez képest még több időt takarít meg a kívánt útvonal eléréséhez.

Előnyök és hátrányok

• Megnövekedett teljesítmény;
• Memóriára van szüksége a keresési fa tárolásához, így ellenőrizheti, hogy egy levél egy másik fához tartozik-e.

Nehézségi pontszám

A teljes algoritmus összetettségét az előre és visszafelé irányuló keresések összetettségének összegeként becsüljük meg, a tagsági ellenőrzés egy művelettel egyenlő, az állandó idő (O (n)), a hash táblához való hozzáférés .

A műveletek számának számolása

Túlságosan az adott helyzettől függ, ha a keresés nem n-áris fán történik .

A növekvő számú művelet aszimptotikus összetettsége

• Ha csak a konkrét kezdeti és célelemek ismeretesek, akkor az előre és visszafelé keresés aszimptotikus időbonyolultsága egyenlő , így a teljes - + , ami sokkal kisebb, mint . Térbeli aszimptotikus komplexitás , a közvetlen helyett , mivel azt a memóriában kell tárolni.
• Ha ismert egy konkrét kezdőelem és egy elemhalmaz, akkor melyik a célelem.

Statisztikai értékelés

A kétirányú keresés egyetlen kezdő és záró elem mellett javíthatja az egyirányú szélesség-első keresést, jellemzően 2-szeresére. A kétirányú keresés legnehezebb esete egy olyan probléma, amelyben csak néhány (esetleg nagyon nagy) célállapot-halmaz implicit leírását adjuk meg a cél ellenőrzésére, például a „sakk” cél sakkmattájának megfelelő összes állapotot. " a sakkban . Fordított keresésnél szükség lenne minden olyan állapot kompakt leírására, amely lehetővé teszi a sakkmattot mozgásokkal stb.; és ezeket a leírásokat össze kellene vetni a közvetlen keresés által generált állapotokkal. Nincs általános módszer egy ilyen probléma hatékony megoldására.

Kétirányú keresési algoritmus

Az algoritmus a következőkből áll:

• közvetlen keresés, hasonló az egyszeri kereséshez;
• fordított keresés;
• műveletek annak meghatározására, hogy egy levél egy másik keresési fához tartozik-e.

A megvalósítás összetettsége

A megvalósítás bonyolultsága a fordított keresési algoritmusban rejlik.

Megvalósítási példák

Gyakorlati alkalmazás

Lásd még

• Szélesség első keresés
• Mélységi első keresés

Jegyzetek

1. ↑ Egyéb: kétirányú elemkeresés - kétirányú vagy körkörös listákban történik a kívánt elemtől mindkét irányban.
2. ↑ [1]  (lefelé irányuló kapcsolat) Ez az algoritmus teljes és optimális (egyenletes lépésköltséggel), ha mindkét keresési folyamat szélesség-első; a módszerek más kombinációiból hiányozhat a teljesség, az optimálisság vagy mindkettő.

Linkek

• Útkereső algoritmusok a pmg.org.ru oldalon
• Modellek és módszerek a problémák megoldására a Mari El.ru oldalon
• C++ implementáció (aisearch.tgz) a www.cs.cmu.edu oldalon

Irodalom

• Stuart Russell és Peter Norvig. 2. rész Problémamegoldás // Mesterséges intelligencia (modern megközelítés) = Artificial Intelligence (A Modern Approach). - 2. kiadás - FGUP. "Nyomtató udvar" Gorkij A. M.: Williams, 2006. - S. 135-136. — ISBN 5-8459-0887-6 .