Tip:
Highlight text to annotate it
X
Gitt dybde-først søkets ikke-optimalitet,
hvorfor ville noen velge å bruke det?
Vel, svaret har å gjøre med lagringsbehov.
Her har jeg illustrert et tilstandsrom
bestående av svært store, ja til og med uendelige binære trær.
Når vi går til nivå 1, 2, 3, ned til nivå n,
vokser treet større og større.
La oss se på grensen for hvert av disse søkealgoritmene.
For bredde-først søk vet vi at grensen ser slik ut,
så når vi kommer ned til nivå n, trenger vi en lagringskapasitet på
2 i n-te for å lykkes med et bredde-først søk.
For billigste først, blir grensen mer komplisert.
Den kommer til å komme fram til denne type kostnad,
men kommer til å ha et lignende antall noder.
Men for dybde-først søk, ettersom vi går nedover treet, går vi først ned denne grenen,
går tilbake opp, men for ethvert punkt, kommer grensen bare til å ha n noder
i motsetning til 2 i n-te noder, så vi slipper mye billigere unna et dybde-først søk.
Selvsagt, dersom vi også holder orden på utforsket samlingen,
så blir ikke innsparelsen like stor
Men uten utforsket-samlingen, har dybde-først en stor fordel
sett ut ifra lagringsbesparelse.
En egenskap til å utforske ved algoritmene
er egenskapen fullstendighet, som betyr at dersom det finnes et mål ett eller annet sted,
vil så algoritmen finne det?
La oss gå fra veldug store trær til uendelige trær,
og la oss si at det finnes et mål gjemt dypt der nede et sted.
Da er spørsmålet: er hver av disse algoritmene fullstendige?
Altså, er det garantert at de finner en rute fram til det målet?
Sett et kryss for de algoritmene du tror er fullstendige i denne betydningen.