diff options
author | Anton Luka Šijanec <anton@sijanec.eu> | 2023-01-27 15:55:37 +0100 |
---|---|---|
committer | Anton Luka Šijanec <anton@sijanec.eu> | 2023-01-27 15:55:37 +0100 |
commit | e1ca97ded1258fea7c5cef33b35a318c72b41836 (patch) | |
tree | ce02977031891257e44500ce6a724706ada81b6f /inf/rtkš/5.txt | |
parent | Merge branch 'master' of ssh://ni.sijanec.eu/var/lib/git/sijanec/sola-gimb-4 (diff) | |
download | sola-gimb-4-e1ca97ded1258fea7c5cef33b35a318c72b41836.tar sola-gimb-4-e1ca97ded1258fea7c5cef33b35a318c72b41836.tar.gz sola-gimb-4-e1ca97ded1258fea7c5cef33b35a318c72b41836.tar.bz2 sola-gimb-4-e1ca97ded1258fea7c5cef33b35a318c72b41836.tar.lz sola-gimb-4-e1ca97ded1258fea7c5cef33b35a318c72b41836.tar.xz sola-gimb-4-e1ca97ded1258fea7c5cef33b35a318c72b41836.tar.zst sola-gimb-4-e1ca97ded1258fea7c5cef33b35a318c72b41836.zip |
Diffstat (limited to 'inf/rtkš/5.txt')
-rw-r--r-- | inf/rtkš/5.txt | 25 |
1 files changed, 25 insertions, 0 deletions
diff --git a/inf/rtkš/5.txt b/inf/rtkš/5.txt new file mode 100644 index 0000000..ed9ac28 --- /dev/null +++ b/inf/rtkš/5.txt @@ -0,0 +1,25 @@ +Inicializacija: + Omrežje jam si predstavljamo kot graf, predstavljen v 2D tabeli enobitnih podatkov (drži=1/ne drži=0) --- omrežje[i][j]. Ta tabela je velikosti n*n, omrežje[i][j] v tej tabeli pa pove, da je med jamama i in j prehod. Začnemo s tabelo, polno ničel. + Tabelo jamskega omrežja izpolnimo z zanko z lokalno spremenljivko i, ki gre od 0 do m: + omrežje[a[i]][b[i]] := 1 in omrežje[b[i]][a[i]] := 1 + Nastavimo tudi 1D tabelo obiskanih jam dolžine n, torej obiskane[n]. Inicializiramo ga na 0, prav tako vsebuje dvojiške podatke v celicah. + obiskane[s] := 1 + Definiramo podprogram išči(referenca na omrežje, referenca na obisakane), ki na koncu vrne skalarno stanje iskanja izmed neuspel, novo ali cilj. Postopek podprograma: + stanje := neuspel + Zanka od 1 do n z lokalno spremenljivko obiskana: + Če drži obiskane[obiskana]: + Zanka od 1 do n z lokalno spremenljivko nova: + Če drži bodisi omrežje[jama][nova] bodisi omrežje[nova][jama]: + obiskane[nova] := 1 + stanje := novo + Če c[obiskana] != -1: + omrežje[c[obiskana]][d[obiskana]] := 1 + omrežje[d[obiskana]][c[obiskana]] := 1 + stanje := novo + Če je obiskana enako t: + stanje := cilj +Neskončna zanka: + Dokler funkcija išči vrača novo, jo neprestano kličemo, s čimer odpremo vse možne skrinje in pogledamo po omrežjem grafu vse možne jame, če so slučajno ciljne in dostopne. Ko funkcija ne vrne novo, je ali našla t (stanje == cilj), kar pomeni, da je pot mogoča, ali pa ne dostopala do nobenih novih jam ali odprla nobenih novih skrinj, kar pomeni, da se bo isto zgodilo v naslednjem potencialnem ciklu, zato iskanje prekinemo, saj pot od s do t ni možna. + +Prostorska zahtevnost je polinomska s številom jam --- S(n^2). Teoretično manj, ker lahko hranimo le tabelo velikosti n*n/2 trikotniške oblike. +Časovna zahtevnost je v najslabšem primeru O(n*globina), kjer je globina število prehodov od s do najbolj oddaljene jame, ko so vse dosegljive skrinje že odprte, in v najboljšem O(n), ko je s enak t. |