Cea mai bună-prima căutare

Această intrare pe subiectele algoritmilor și teoriei graficelor este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia .

Cea mai bună-prima căutare
Clasă	Algoritm de căutare
Structură de date	Copac
Cel mai rău caz din punct de vedere temporal	${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">b</span></span>}}^{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">m</span></span>}}}${\ displaystyle b ^ {m}}
Cel mai rău caz spațial	${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">b</span></span>}}^{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">m</span></span>}}}${\ displaystyle b ^ {m}}
Optim	Nu
Costum de afaceri	da
Manual

Cea mai bună căutare este o strategie de căutare informată utilizată pentru rezolvarea problemelor bazată pe cercetare și este fundamentul algoritmilor moderni de AI . În comparație cu strategiile de cercetare neinformate , care sunt utilizate în cazul în care informațiile specifice privind starea problemei nu sunt disponibile dincolo de definiția problemei, cele mai bune cercetări, la fel ca toate celelalte strategii de cercetare în cunoștință de cauză, exploatează cunoștințele mai multe detalii despre starea a problemei de rezolvat.

Se presupune că problema este reprezentată ca un copac de căutare , în care fiecare nod reprezintă o stare specifică a problemei, iar nodurile frunze constituie stările obiective. Rădăcina este starea inițială a problemei. Fiecare cale de la rădăcină la orice frunză a copacului reprezintă o soluție la problemă. Scopul este de a găsi cea mai eficientă soluție în ceea ce privește viteza de execuție și ocuparea memoriei.

Cea mai bună strategie de căutare implementează o funcție de evaluare dedicată ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">f</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">(</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">n</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">)</span></span>}${\ displaystyle f (n)} care are sarcina de a selecta, la fiecare pas al căutării, următorul nod care urmează să fie extins. Prin urmare, la fiecare pas, dintre toate nodurile posibile care urmează să fie extinse, algoritmul alege nodul cu cea mai mică funcție de evaluare (deci best-first). O funcție de acest tip se numește în general euristică și are sarcina de a selecta, din când în când, nodul care pare să ducă la soluția optimă a problemei.

Bibliografie

• Stuart J. Russell, Peter Norvig, Inteligența artificială: o abordare modernă , Pearson Education Italia, 2005. ISBN 887192228X .

Elemente conexe

• Cercetare lacomă
• Algoritmul A *
• Recursive best-first search
• Căutare grindă

linkuri externe

• ( EN ) Definiție tehnică a celei mai bune căutări , pe encyclopedia.com .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT