Meklēšana dziļumā

Meklēšana dziļumā
	Virsotņu apstaigāšanas secība
Klase	Meklēšanas algoritms
Datu struktūra	Grafs
Sliktākā ātrdarbība
Sliktākais atmiņas patēriņš
Optimāls	jā (grafiem bez svariem)
Pilnīgs	jā

Meklēšana dziļumā (angļu: depth-first search, DFS) ir pārlases (angļu: brute force) grafa traversēšanas un grafa virsotņu meklēšanas algoritms. Algoritma tipu sauc arī par naivo, vai neinformēto algoritmu. Atšķirībā no meklēšanas plašumā, meklēšanas dziļumā laikā katrs zars tiek izpētīts līdz galam, pirms apstrādāt jaunu zaru.^[1] Šādā veidā tiek apmeklētas visas no starta virsotnes sasniedzamās virsotnes. Grafos, kuros ir nedaudzi, bet ļoti gari ceļi, iespējams izmantot arī ierobežotu meklēšanu dziļumā, kura katru iesākto ceļu apseko tikai līdz noteiktam dziļumam. Uzlabota meklēšana dziļumā ir iteratīvā meklēšana dziļumā.

Vispārēji

Meklēšana dziļumā ir pārlases meklēšanas algoritms, kas katru uzieto zaru pārmeklē pilnībā, pirms uzsākt meklēšanu citos zaros. Kādā kārtībā tiek kārtotas virsotnes, kas ir sasniedzamas, no aktuālās virsotnes, ir atkarīgs no grafa reprezentācijas vai tā pieraksta. Saistību matricas (angļu: adjacency matrix) gadījumā, sekojošās virsotnes tiek apmeklētas to rindas kārtībā saistību matricā. Piemēra animācijā tiek pēc noklusējuma pieņemts, ka kaimiņu virsotnes tiek apmeklētas kārtībā no kreisās uz labo pusi.

Neformāls algoritms

Izvēlies sākuma virsotni.
Ja virsotne ir meklētā virsotne, apstrādes beigas.
Atzīmē virsotni kā apmeklētu.
Saglabā kaimiņu virsotnes stekā.
Kamēr steks nav tukšs, izņem kaimiņvirsotni no steka.
- Ja virsotne vēl nav apmeklēta, rekursīvi izsauc meklēšanas algoritmu (atgriežas punktā 2).

Pseidokods

DFS(node, goal)
{
  if (node == goal) {
    return node;
  } else
  {
    mark(node);
    stack := expand (node);
    while (stack is not empty)
    {
      node' := pop(stack);
      if (not marked(node')) {
         DFS(node', goal);
    }
  }
}

Algoritma sarežģītība

Ja grafs definēts kā saistību saraksts (angļu: adjacency list), ļaunākajā gadījumā algoritms testē visas iespējamās šķautnes un visas iespējamās virsotnes. Šādai meklēšanai dziļumā Landau pierakstā piemīt sarežģītība ${\mathcal {O}}(\vert V\vert +\vert E\vert )$ , kur $\vert V\vert$ ir virsotņu skaits un $\vert E\vert$ — šķautņu skaits.^[2]

Ja grafs ir definēts kā saistību matrica, algoritmam piemīt sarežģītība ${\mathcal {O}}(\vert V\vert ^{2})$ .^[3]

Ja grafs ir bezizmēra vai algoritmā tiek izlaista pārbaude, vai virsotne jau ir tikusi apmeklēta, algoritms var neterminēt.

Pielietojums

Meklēšana dziļumā ir citu grafu algoritmu sastāvdaļa.
Ar meklēšanas dziļumā palīdzību ar kompleksitāti ${\mathcal {O}}(\vert V\vert +\vert E\vert )$ iespējams noteikt grafa cikliskumu un ciklam piederīgās šķautnes.^[4]
Neciklisku grafu ar kompleksitāti ${\mathcal {O}}(\vert V\vert +\vert E\vert )$ iespējams sakārtot topoloģiski.

Meklēšana dziļumā nav optimāla, ja šķautņu svari dziļumā ir monotoni augoši. Šādā gadījumā var tikt atrasts daudz garāks ceļš, nekā optimālais. Salīdzinājumam – atmiņu vairāk patērējošā meklēšana plašumā šādā gadījumā atrastu optimālo risinājumu. Abu meklēšanas algoritmu apvienojums ir iteratīvā meklēšana dziļumā.

Literatūra

Stuart Russell, Peter Norvig : Artificial Intelligence: A Modern Approach, 2. Auflage, 2002, Prentice Hall. (angļu val.)
Sven Oliver Krumke, Hartmuts Noltemeiers : Graphentheoretische Konzepte und Algorithmen. Springer Vieweg, 3. Auflage, 2012, ISBN 978-3-8348-1849-2 (vācu val.)

Atsauces

↑ Volker Turau. Algorithmische Graphentheorie (3 izd.). München : Oldenbourg Wissenschaftsverlag, 2009. 94–98. lpp. ISBN 9783486590579.
↑ Thomas Ottmann, Peter Widmayer. Algorithmen und Datenstrukturen (5 izd.). Heidelberg : Spektrum Akademischer Verlag, 2012. 589–668. lpp. ISBN 978-3-8274-2803-5.
↑ «Graphen» (PDF; 73 kB). Arhivēts no oriģināla, laiks: 2003-05-23. Skatīts: 2012-07-25.
↑ Sven Oliver Krumke, Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen (3 izd.). Wiesbaden : Springer Vieweg, 2012. 152−157. lpp. ISBN 978-3-8348-1849-2.

Ārējās saites

Meklēšanas dziļumā piemērs (vāciski)

[1] Volker Turau. Algorithmische Graphentheorie (3 izd.). München : Oldenbourg Wissenschaftsverlag, 2009. 94–98. lpp. ISBN 9783486590579.

[2] Thomas Ottmann, Peter Widmayer. Algorithmen und Datenstrukturen (5 izd.). Heidelberg : Spektrum Akademischer Verlag, 2012. 589–668. lpp. ISBN 978-3-8274-2803-5.

[3] «Graphen» (PDF; 73 kB). Arhivēts no oriģināla, laiks: 2003-05-23. Skatīts: 2012-07-25.

[Krumke2012-4] Sven Oliver Krumke, Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen (3 izd.). Wiesbaden : Springer Vieweg, 2012. 152−157. lpp. ISBN 978-3-8348-1849-2.

[1]

[2]

[3]

[4]