Tas pats algoritmas, kitas atsakymas

Penktoje pamokoje parodei, kad rekursija ir atskiras stekas yra tas pats algoritmas, ir tai pamatavai:

rekursinis                       80             40
iteracinis (tavo stekas)         80             40
identiški — tas pats algoritmas, tik stekas laikomas kitoje vietoje

Čia turi abu variantus grafe. Ir jie nesutampa.

  path from 0 to 705
  DFS (stack)                 214
  DFS (recursive)               1

  the two DFS versions agree: false

Testas sako, kiek dažnai:

the two DFS versions took different paths to 552 destinations

Iš 554 pasiekiamų — 552.

Ar penkta pamoka klydo

Ne. Ji tebėra teisinga, tik reikia tiksliai pasakyti, apie ką.

Tas pats liko tas pats. Abi versijos aplanko tas pačias viršūnes, atlieka tą patį darbo kiekį, kainuoja O(V + E) ir sutaria, kas pasiekiama — TestBothSearchesAgreeOnReachability to reikalauja ir jis praeina.

Skiriasi kaimynų eilės tvarka. Steko versija sudeda visus kaimynus ir ima paskutinį, tad juos apeina atbulai. Rekursinė eina iš eilės nuo pirmo. Ta pati aikštė, priešingos kryptys.

„Tas pats algoritmas" reiškia „skaičiuoja tą patį", ne „grąžina tą patį atsakymą". Kai atsakymų yra daug ir visi teisingi, tvarka nusprendžia, kurį gausi.

DFS grąžina kažkokį kelią. Nė vienas šių dviejų nėra teisingesnis už kitą.

Kur lygybė iš tikrųjų baigiasi

Penkta pamoka rado ir antrą skirtumą — gylį. Štai jis grafe, grandinės pavidalo bibliotekoje:

n= 4000000  iteracinis DFS: ok=true  hops=3999999
n= 4000000  rekursinis DFS: ok=true  hops=3999999

n=12000000  iteracinis DFS: ok=true  hops=11999999
n=12000000  rekursinis DFS:
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

Keturi milijonai — abu veikia. Dvylika milijonų — iteracinis nueina visą grandinę, rekursinis nulūžta.

Priežastis ta pati, kurią penkta pamoka pamatavo: kvietimų stekas auga iki 1 GB ribos ir sustoja. Tavo stekas yra griežinys krūvoje, o jam tokios ribos nėra.

Ir dabar tai nebe demonstracija:

• rekursija trumpesnė — DFS telpa į šešias eilutes vietoj dešimties;
• iteracija neturi gylio ribos ir leidžia valdyti aplankymo tvarką;
• BFS rekursijos net neturi — sluoksniams reikia eilės, o kvietimų stekas yra stekas.

Ketvirtoje pamokoje buvo pasakyta, kad transit rašo savo BFS iteraciškai su atskira eile. Dabar aišku, kad kitaip ir negalėtų: rekursija duoda steką, o BFS reikia eilės. Pasirinkimo ten nėra — jis yra tik DFS.