Á dýptina fyrst

Á dýptina fyrst eða DF (e. Depth-first search), er vinsæl leitaraðferð sem notuð er í leitartrjám.

DF ólíkt á breiddina fyrst leitar strax á mesta dýpi og hún getur. Þ.e.a.s. leitin byrjar á að skoða hnúta eins djúpt til vinstri í leitartrénu og hún getur. Ef hún finnur ekki lausn þar þá bakkar hún upp um einn hnút (í foreldri), velur næsta hnút undir honum (sem hún hefur ekki leitað í) og leitar eins langt og hún getur til vinstri undir honum og hún getur. Þetta gerir leitin og skilar hún fyrstu lausn sem hún finnur í trénu.

DF gerir lægri minniskröfur í keyrslu heldur en systur aðferðin sín á breiddina fyrst. Einungis þarf minni tölvunnar að geta geymt jafn marga hnúta í minni eins og dýpsta mögulega leitin þarf að skoða.

Sauðakóði

dyptin_fyrst( innsendur hnútur ):
   ef innsendur hnútur er markmið okkar:
      skila já

   fyrir hvern undirhnút innsends hnúts (frá vinstri til hægri):
      svar = dyptin_fyrst( undirhnútur )
      ef svar er já þá:
         vista hnút í lausnar mengi og skila já
      annars:
         skila nei

Kallað er í upphafi á reikniritið með rót leitartrésins.

Kostir

1. Hefur margfalt lægri minniskröfur heldur en á breiddina fyrst. Getur þar af leiðandi leitað í mun stærri leitartrjám
2. Hentar best fyrir vélbúnað sem hefur takmarkaðar auðlindir

Ókostir

1. Engin leið til að hindra að sömu undirtré séu skoðuð margsinnis
2. Getur fest í því að leita endalaust niður ákveðna grein leitartrésins (hafi hún óendanlega dýpt) þó svo að lausn liggji annarsstaðar í trénu.

Kröfur

Minniskröfur: <math>O(d)</math> þar sem d er mesta dýpt sem hnútur í leitartrénu liggur á.
Tímakröfur:

Aðrar útfærslur

Á dýptina fyrst með dýptar aukningu (e. Depth-first Iterative Deepening)