summaryrefslogblamecommitdiffstats
path: root/inf/rtkš/5.txt
blob: ed9ac28d7bd823b7661e1d328fe773f694efd86d (plain) (tree)
























                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          
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.