Căutare limitată de adâncime

Căutare limitată de adâncime
Clasă	Algoritm de căutare
Structură de date	Grafic
Cel mai rău caz din punct de vedere temporal	$O(\|V\|+\|E\|)$ ${\ displaystyle O (\| V \| + \| E \|)}$ ${\ displaystyle O (\| V \| + \| E \|)}$
Cel mai rău caz spațial	$O(\|V\|)$ ${\ displaystyle O (\| V \|)}$ ${\ displaystyle O (\| V \|)}$
Optim	Nu
Costum de afaceri	Nu
Manual

În informatică , căutarea cu adâncime limitată ( DLS ) este un algoritm de căutare pentru explorarea vârfurilor unui grafic . Este o versiune modificată a căutării în profunzime și este utilizată, de exemplu, în algoritmul de aprofundare iterativă .

Concept de bază

Ca și prima căutare în profunzime, căutarea în adâncime limitată este un tip de căutare neinformată. Funcționează exact ca o căutare în prima adâncime, dar previne dezavantajul completității prin impunerea unei limite pentru adâncimea maximă de căutare. Chiar dacă ar fi posibil să se continue extinderea unui vârf la o adâncime dată, acest lucru nu se va întâmpla și, prin urmare, nu va continua să meargă la nesfârșit în adâncimea unei căi sau să se blocheze într-o buclă . Prin urmare, căutarea cu adâncime limitată va găsi o soluție numai dacă se află într-o anumită limită de adâncime, ceea ce garantează cel puțin completitudinea tuturor graficelor.

Algoritm (informal)

Determinarea punctului de plecare și atribuirea limitei maxime de adâncime
Verificați dacă vârful curent este cel de destinație:
- Nu: nu face nimic
- Da: întoarceți-vă
Verificați dacă vârful curent are o adâncime mai mică decât limita impusă:
- Nu: nu face nimic
- Da:
  1. Extinderea Vertex și salvarea succesorilor săi într-un stack
  2. Apelați recursiv la DLS pentru toate vârfurile din stivă, apoi Pasul 2 din nou

Pseudo cod

 DLS (nod, destinație, adâncime) {
	if (adâncime> = 0) {
		if (nod == destinație)
			nod de retur
		pentru fiecare copil din extensie (nod)
			DLS (copil, destinație, adâncime - 1)
	}
}

Proprietate

Complexitatea spațială

Același subiect în detaliu: Teoria complexității computaționale .

Deoarece căutarea cu adâncime limitată profită de căutarea cu adâncime întâi , complexitatea spațială este echivalentă cu căutarea normală cu adâncime întâi.

Complexitatea timpului

Același subiect în detaliu: Teoria complexității computaționale .

Întrucât căutarea cu adâncime limitată utilizează căutarea la prima adâncime , complexitatea este echivalentă cu cea a căutării normale la adâncime prima sau $O(|V|+|E|)$ ${\ displaystyle O (| V | + | E |)}$ ${\ displaystyle O (| V | + | E |)}$ , unde este $|V|$ ${\ displaystyle | V |}$ ${\ displaystyle | V |}$ este numărul de vârfuri și $|E|$ ${\ displaystyle | E |}$ ${\ displaystyle | E |}$ numărul de muchii din graficul explorat. Rețineți că căutarea cu adâncime limitată nu explorează întregul grafic, ci doar partea inclusă în limita specificată.

Completitudine

Același subiect în detaliu: NP-Complete .

Deoarece căutarea cu adâncime limitată nu poate analiza căi infinit de lungi sau nu poate rămâne blocată în bucle, în general nu este un algoritm complet, deoarece nu găsește nicio soluție dincolo de limita impusă. Cu toate acestea, dacă limita de adâncime aleasă este mai mare decât adâncimea arborelui, algoritmul devine complet.

Optimitate

Căutarea la adâncime limitată nu este optimă, deoarece, la fel ca și căutarea la prima adâncime, explorează complet o cale, implicând astfel posibilitatea de a găsi o soluție mai scumpă decât alta.

Elemente conexe

prima căutare în profunzime

Portal IT

Portalul de matematică