Dubbelriktad sökning

Dubbelriktad bredd (eller djup) sökning [1] [2] är en sofistikerad bredd (eller djup ) sökalgoritm , vars idé är att bilda en sökprocess från den initiala ( framåtsökningen ) och från den slutliga vertexen ( omvänd sökning ) i grafen .

Idé

Att hitta den önskade vägen handlar om att bestämma banorna från den initiala till någon mellanliggande, och från den till den slutliga vertexen. Implementeras genom att checka in en eller båda processerna när ett blad från ett sökträd matchar ett blad från ett annat, varefter sökvägar till det elementet extraheras. Genom att koppla ihop stigarna får vi den önskade vägen. Om två sökningar görs parallellt  sparar detta ännu mer tid för att få den önskade sökvägen jämfört med en enkelriktad sökning.

Fördelar och nackdelar

• Ökad prestanda;
• Du behöver minne för att lagra sökträdet så att du kan kontrollera om ett löv tillhör ett annat träd.

Svårighetsgrad

Komplexiteten för hela algoritmen uppskattas som summan av komplexiteten av sökningar framåt och bakåt, medlemskontroll lika med en operation, konstant tid (O (n)), tillgång till hashtabellen .

Räknar antalet operationer

För beroende av den specifika situationen om sökningen inte sker på ett n-ärt träd .

Asymptotisk komplexitet av ökande antal operationer

• Om de enda specifika initiala och målelementen är kända, är den asymptotiska tidskomplexiteten för sökningarna framåt och bakåt lika med , därav den totala - + , som är mycket mindre än . Rumslig asymptotisk komplexitet , istället för den direkta, eftersom den måste lagras i minnet.
• Om ett specifikt startelement och en uppsättning element är kända, varav ett är målelementet.

Statistisk utvärdering

Dubbelriktad sökning, givet ett enda start- och slutelement, kan förbättra enkelriktad bredd-först-sökning, vanligtvis med en faktor 2. Det svåraste fallet för en dubbelriktad sökning är ett sådant problem där endast en implicit beskrivning av någon (möjligen mycket stor) uppsättning måltillstånd ges för att kontrollera målet, till exempel alla tillstånd som motsvarar målets schackmatt "Schack "i schack . I omvänd sökning skulle det vara nödvändigt att skapa kompakta beskrivningar av alla tillstånd som tillåter schackmatt med drag , etc.; och dessa beskrivningar skulle behöva kontrolleras mot de tillstånd som genereras av direkt sökning. Det finns inget generellt sätt att effektivt lösa ett sådant problem.

Dubbelriktad sökalgoritm

Algoritmen består av:

• direkt sökning, liknande enstaka sökning;
• omvänd sökning;
• operationer för att avgöra om ett löv tillhör ett annat sökträd.

Implementeringens komplexitet

Komplexiteten i implementeringen ligger i den omvända sökalgoritmen.

Implementeringsexempel

Praktisk tillämpning

Se även

• Utöka första sökningen
• Djup första sökning

Anteckningar

1. ↑ Övrigt: dubbelriktad elementsökning - utförs i dubbelriktade eller cirkulära listor från det önskade elementet i båda riktningarna.
2. ↑ [1]  (nedlänk) Denna algoritm är komplett och optimal (med enhetliga stegkostnader) om båda sökprocesserna är breddförsta; andra kombinationer av metoder kan sakna fullständighet, optimalitet eller båda.

Länkar

• Pathfinding- algoritmer på pmg.org.ru
• Modeller och metoder för att lösa problem på Mari El.ru
• C++-implementering (aisearch.tgz) på www.cs.cmu.edu

Litteratur

• Stuart Russell och Peter Norvig. Del 2. Problemlösning // Artificiell intelligens (Modern Approach) = Artificiell intelligens (A Modern Approach). - 2:a uppl. - FGUP. "Tryckgård" A.M. Gorky: Williams, 2006. - S. 135-136. — ISBN 5-8459-0887-6 .