Beste førstesøk - Best-first search

Graf og tre
søkealgoritmer
Oppføringer
relaterte temaer

Best-first-søk er en søkealgoritme som utforsker en graf ved å utvide den mest lovende noden som er valgt i henhold til en spesifisert regel.

Judea Pearl beskrev best-first search som å estimere løftet om node n ved en "heuristisk evalueringsfunksjon som generelt kan avhenge av beskrivelsen av n , beskrivelsen av målet, informasjonen som er samlet inn av søket fram til det punktet, og viktigst av alt om ekstra kunnskap om problemdomenet. "

Noen forfattere har brukt "best-first search" for å referere spesifikt til et søk med en heurist som prøver å forutsi hvor nær enden av en bane er til en løsning (eller et mål), slik at stier som vurderes å være nærmere en løsning (eller mål) utvides først. Denne spesifikke typen søk kalles grådig best-first-søk eller rent heuristisk søk .

Effektivt valg av den nåværende beste kandidaten for utvidelse implementeres vanligvis ved hjelp av en prioritetskø .

Den A * søkealgoritme er et eksempel på et best første søkealgoritme, som er B * . De beste først-algoritmene brukes ofte til å finne stier i kombinatorisk søk . Verken A* eller B* er et grådig best-first-søk, ettersom de inkorporerer avstanden fra starten i tillegg til estimerte avstander til målet.

Grådig BFS

Ved å bruke en grådig algoritme kan du utvide den første etterfølgeren til forelder. Etter at en etterfølger er generert:

  1. Hvis etterfølgerens heuristikk er bedre enn forelder, settes etterfølgeren foran i køen (med forelder satt inn igjen bak den), og sløyfen starter på nytt.
  2. Ellers blir etterfølgeren satt inn i køen (på et sted bestemt av dens heuristiske verdi). Prosedyren vil evaluere de gjenværende etterfølgerne (hvis noen) av forelder.

Nedenfor er et pseudokodeeksempel på denne algoritmen, der kø representerer en prioritetskø som bestiller noder basert på deres heuristiske avstander fra målet. Denne implementeringen holder oversikt over besøkte noder, og kan derfor brukes til ustyrte grafer . Den kan endres for å hente banen. 

procedure GBS(start, target) is:
  mark start as visited
  add start to queue
  while queue is not empty do:
    current_node ← vertex of queue with min distance to target
    remove current_node from queue
    foreach neighbor n of current_node do:
      if n not in visited then:
        if n is target:
          return n
        else:
          mark n as visited
          add n to queue
  return failure

Se også

Referanser

  1. ^ Pearl, J. Heuristics: Intelligente søkestrategier for problemløsning av datamaskiner . Addison-Wesley, 1984. s. 48.
  2. ^ a b Russell, Stuart J .; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2. utg.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2. s. 94 og 95 (merknad 3).
  3. ^ Korf, Richard E. (1999). "Søkealgoritmer for kunstig intelligens". I Atallah, Mikhail J. (red.). Handbook of Algorithms and Theory of Computation . CRC Press. ISBN 0849326494.
  4. ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search når EHC mislykkes, Carnegie Mellon

Eksterne linker