Vienas perėjimas prieš 214

Pirmame žingsnyje užsirašei spėjimą: kiek ilgesnis bus DFS kelias?

$ algo gen -n 1000 -seed 3
$ algo net
nodes 1000, edges 744
  degree: mean 1.49, median 1, max 10
  components 446, largest 555 (55.5% of the library)

  path from 0 to 705

                             hops edges looked at         time
  BFS (queue)                   1              5           0s
  DFS (stack)                 214           1251           0s
  DFS (recursive)               1              5            -

  DFS path is 214.0x longer than the shortest

Vienas perėjimas prieš 214

Knyga 705 yra tiesioginė knygos 0 kaimynė. Viena briauna. BFS ją randa peržiūrėjęs penkias briaunas.

DFS praeina 214 knygų, kad pasiektų tą, kuri buvo šalia nuo pat pradžių.

Priežastis matoma antrame žingsnyje. DFS sudeda visus kaimynus į steką ir tada ima paskutinį. Jei knyga 705 buvo įdėta pirma, ji lauks steko dugne, kol bus ištirta viskas, kas guli virš jos — o tai buvo visas 214 knygų ilgio pėdsakas.

Ji vis tiek randama. Kelias tikras. Tik jis nėra atsakymas į klausimą „per kiek perėjimų".

Bet vienas atvejis yra anekdotas

Todėl komanda tikrina visas pasiekiamas kryptis:

  every reachable destination from 0 (554 of them):
    DFS found the shortest path   20 (3.6%)
    DFS found a longer path       534 (96.4%)
    mean DFS/BFS hop ratio        26.45x
    worst case                    214 hops vs 1 (214.0x)

96.4 % atvejų DFS klysta, o vidutiniškai jo kelias yra 26 kartus ilgesnis.

Tai ne „kartais nepasiseka". Tai beveik visada, ir tai nėra klaida — DFS niekada nė nežadėjo trumpiausio kelio. Blogai tik tada, jei paklausei trumpiausio.

Kodėl BFS gali pažadėti

Eilė lanko sluoksniais: pirma viską per vieną perėjimą, tada viską per du.

Kai to pasirodo pirmą kartą, visi trumpesni sluoksniai jau išsemti — jei ten būtų buvęs kelias, jis būtų atrastas anksčiau. Todėl pirmas radimas ir yra trumpiausias.

Stekas sluoksnių neturi. Jis eina gilyn, kol atsiremia, ir tik tada grįžta — taigi pirmas radimas yra tiesiog pirmas, o ne geriausias.

BFS atsako „per kiek perėjimų". DFS atsako „ar apskritai pasiekiama". Antram klausimui BFS irgi tinka, bet DFS jam pigesnis atmintimi.

Ir dar viena eilutė lentelėje

  components 446, largest 555 (55.5% of the library)

Bibliotekos tinklas nėra vientisas. Iš knygos 0 pasiekiama 555 knygos — 55.5 % rinkinio; likusios 445 sudaro dar 445 atskiras salas, dažniausiai po vieną knygą, kurios niekas nesiskolino kartu su kita.

Tai irgi BFS darbas: Components paleidžia paiešką iš kiekvienos dar nepasiektos viršūnės. Kiekviena viršūnė aplankoma lygiai kartą per visą procesą, tad kaina lieka O(V + E) — ne V atskirų paieškų.