Iti0210lab2 - Redigeerimiste ajalugu

PriitJ – 7. veebruar 2019, kell 12:42

2019-02-07T12:42:01Z

←Vanem redaktsioon		Redaktsioon: 7. veebruar 2019, kell 14:42
85. rida:		85. rida:

	def minu_otsing(kaart):		def minu_otsing(kaart):
	# ~~leia~~ start, näiteks tuple kujul (x, y)		# start (algolek) on näiteks tuple kujul (x, y)

	frontier = Queue()		frontier = Queue()

PriitJ: /* Ettevalmistus */

2019-02-07T08:47:41Z

Ettevalmistus

←Vanem redaktsioon		Redaktsioon: 7. veebruar 2019, kell 10:47
55. rida:		55. rida:
	== Ettevalmistus ==		== Ettevalmistus ==

	Enne, kui otsingut saab alustada, tuleb kindlaks ~~teha, kus~~ alguspunkt on. Seega otsusta, mida tähistad ''x'' ja ''y'' koordinaatidena (üks peaks olema read, teine veerud) ~~ning leia "s"~~-~~i koordinaadid~~. Samuti tee kindlaks kaardi suurus ''x'' ja ''y'' suunas. Otsingu implementeerimisel tuleb paratamatult kontrollida, kas mingi koordinaadipaar on kaardil või sellest väljas.		Enne, kui otsingut saab alustada, tuleb kindlaks määrata alguspunkt. Seega otsusta, mida tähistad ''x'' ja ''y'' koordinaatidena (üks peaks olema read, teine veerud). Mõlemal kaardil on alguspunkt 14. reas, 16. veerus, kusjuures Pythoni indeksite nummerdamine hakkab 0-st.

			Samuti tee kindlaks kaardi suurus ''x'' ja ''y'' suunas. Otsingu implementeerimisel tuleb paratamatult kontrollida, kas mingi koordinaadipaar on kaardil või sellest väljas.

	== Laiutiotsing ==		== Laiutiotsing ==

PriitJ: /* Sissejuhatus */

2019-02-07T08:44:20Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 7. veebruar 2019, kell 10:44
24. rida:		24. rida:
	" s ",		" s ",
	]		]
			start_row=14
			start_col=16
	</pre>		</pre>

45. rida:		47. rida:
	" s ",		" s ",
	]		]
			start_row=14
			start_col=16
	</pre>		</pre>

PriitJ: /* Laiutiotsing */

2018-09-10T13:58:08Z

Laiutiotsing

←Vanem redaktsioon		Redaktsioon: 10. september 2018, kell 15:58
95. rida:		95. rida:
	for next in graph.neighbors(current): # see osa tuleb suht palju ümber teha.		for next in graph.neighbors(current): # see osa tuleb suht palju ümber teha.
	# tuleb leida sobivad naaberruudud kaardilt		# tuleb leida sobivad naaberruudud kaardilt
	# nagu ta meile ette on antud		# nagu ta meile ette on antud (ülal, all,
			# paremal ja vasakul olev ruut)
	if next not in came_from:		if next not in came_from:
	frontier.put(next)		frontier.put(next)

PriitJ: /* Sissejuhatus */

2018-09-10T13:56:53Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 10. september 2018, kell 15:56
3. rida:		3. rida:
	== Sissejuhatus ==		== Sissejuhatus ==

	Antud on kaks kaarti. Kaardi formaat on ASCII-art - ebakonventsionaalne, aga harjutusülesandeks kõlbab küll. Tuleb leida tee kaardil alguspunktist "s" teemandini "D". Seejuures ei tohi tee läbida kohti, kus on laava (tähistus "*").		Antud on kaks kaarti. Kaardi formaat on ASCII-art - ebakonventsionaalne, aga harjutusülesandeks kõlbab küll. Tuleb leida tee kaardil alguspunktist "s" teemandini "D". Seejuures ei tohi tee läbida kohti, kus on laava (tähistus "*"). Liikuda tohib ainult neljas suunas: üles, alla, vasakule ja paremale (mitte diagonaalis).

	Kaart 1:		Kaart 1:

PriitJ: /* Sissejuhatus */

2018-02-08T09:30:40Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 8. veebruar 2018, kell 11:30
47. rida:		47. rida:
	</pre>		</pre>

	Seda kaarti võib vaadata kui ruudustikku, kus iga ruutu tähistab tema ''x'' ja ''y'' koordinaat. Tee leidmiseks kasutame laiutiotsingut (''breadth first search, BFS''). ~~Laiutiotsing~~ tööpõhimõtte animatsioone vaata [https://www.redblobgames.com/pathfinding/a-star/introduction.html siit lehelt]. Sel viisil otsides laava vältimine on tegelikult lihtne - tuleb lihtsalt laavaga ruute käsitleda, nagu läbimatut seina. Kui algoritm on tee leidnud, siis uurime ka, kuidas tema leitud tulemust tõlgendada ja visualiseerida.		Seda kaarti võib vaadata kui ruudustikku, kus iga ruutu tähistab tema ''x'' ja ''y'' koordinaat. Tee leidmiseks kasutame laiutiotsingut (''breadth first search, BFS''). Laiutiotsingu tööpõhimõtte animatsioone vaata [https://www.redblobgames.com/pathfinding/a-star/introduction.html siit lehelt]. Sel viisil otsides laava vältimine on tegelikult lihtne - tuleb lihtsalt laavaga ruute käsitleda, nagu läbimatut seina. Kui algoritm on tee leidnud, siis uurime ka, kuidas tema leitud tulemust tõlgendada ja visualiseerida.

	== Ettevalmistus ==		== Ettevalmistus ==

PriitJ: /* Laiutiotsing */

2018-02-08T09:29:49Z

Laiutiotsing

←Vanem redaktsioon		Redaktsioon: 8. veebruar 2018, kell 11:29
101. rida:		101. rida:


	# Kui teemant on leitud, tuleb ka teekond rekonstrueerida		# Kui teemant on leitud, tuleb ka teekond rekonstrueerida
	# mis andmestruktuurina teekonda esitada, pole oluline,		# mis andmestruktuurina teekonda esitada, pole oluline,
	# aga loomulik viis oleks list		# aga loomulik viis oleks list
	return path		return path
	</pre>		</pre>

PriitJ: /* Visualiseerimine */

2018-02-08T09:27:55Z

Visualiseerimine

←Vanem redaktsioon		Redaktsioon: 8. veebruar 2018, kell 11:27
108. rida:		108. rida:

	== Visualiseerimine ==		== Visualiseerimine ==

			Mittekohustuslik, aga väga kasulik lisaülesanne:

	Kirjuta kood, mis leitud teekonna väljastab sellisel ASCII-art kujul (kujutatud tee on suvaline näide):		Kirjuta kood, mis leitud teekonna väljastab sellisel ASCII-art kujul (kujutatud tee on suvaline näide):

PriitJ: Uus lehekülg: '= Esimene katsetus otsinguga = == Sissejuhatus == Antud on kaks kaarti. Kaardi formaat on ASCII-art - ebakonventsionaalne, aga harjutusülesandeks kõlbab küll. Tuleb leida te...'

2018-02-08T09:27:07Z

Uus lehekülg: '= Esimene katsetus otsinguga = == Sissejuhatus == Antud on kaks kaarti. Kaardi formaat on ASCII-art - ebakonventsionaalne, aga harjutusülesandeks kõlbab küll. Tuleb leida te...'

Uus lehekülg

= Esimene katsetus otsinguga =

== Sissejuhatus ==

Antud on kaks kaarti. Kaardi formaat on ASCII-art - ebakonventsionaalne, aga harjutusülesandeks kõlbab küll. Tuleb leida tee kaardil alguspunktist "s" teemandini "D". Seejuures ei tohi tee läbida kohti, kus on laava (tähistus "*").

Kaart 1:
<pre>
lava_map1 = [
" ** ** ",
" *** D *** ",
" *** ",
" ***** ",
" **** ******** ",
" *** *******",
" ** ******",
"***** **** *** ",
"***** ** ",
"*** ",
" ** ******",
"** *** *******",
"*** ***** ",
" ",
" s ",
]
</pre>

Kaart 2:
<pre>
lava_map2 = [
" ********************** ",
" ******* D ********** ",
" ******* ",
" **************** **********",
"*********** ******** ",
" *******************",
" ******** ******************",
"******** ****",
"***** ************ ",
"*** ********* ",
"* ****** ************",
"***************** *******",
"*** **** ***** ",
" ",
" s ",
]
</pre>

Seda kaarti võib vaadata kui ruudustikku, kus iga ruutu tähistab tema ''x'' ja ''y'' koordinaat. Tee leidmiseks kasutame laiutiotsingut (''breadth first search, BFS''). Laiutiotsing tööpõhimõtte animatsioone vaata [https://www.redblobgames.com/pathfinding/a-star/introduction.html siit lehelt]. Sel viisil otsides laava vältimine on tegelikult lihtne - tuleb lihtsalt laavaga ruute käsitleda, nagu läbimatut seina. Kui algoritm on tee leidnud, siis uurime ka, kuidas tema leitud tulemust tõlgendada ja visualiseerida.

== Ettevalmistus ==

Enne, kui otsingut saab alustada, tuleb kindlaks teha, kus alguspunkt on. Seega otsusta, mida tähistad ''x'' ja ''y'' koordinaatidena (üks peaks olema read, teine veerud) ning leia "s"-i koordinaadid. Samuti tee kindlaks kaardi suurus ''x'' ja ''y'' suunas. Otsingu implementeerimisel tuleb paratamatult kontrollida, kas mingi koordinaadipaar on kaardil või sellest väljas.

== Laiutiotsing ==

Kasutame kooditükki [https://www.redblobgames.com/pathfinding/a-star/introduction.html siit].

<pre>
frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
</pre>

Antud kood alustab otsimist <code>start</code> punktist ning leiab tegelikult teed kõikidesse punktidesse graafil <code>graph</code>. Seejuures saab leitud teid rekonstrueerida selle alusel, et kui <code>came_from[A] == B</code> siis tee punktist ''A'' alguspunkti läheb läbi ''B'' - see tähendab, et tee tuleb rekonstrueerida tagurpidi sihtpunktist alguspunkti.

Kuna meie ülesanne on pisut erinev, siis peame koodi pisut kohandama. Lisaks realiseerime selle funktsioonina, nii et oleks mugav erinevaid kaarte ette anda.

<pre>
from queue import Queue

def minu_otsing(kaart):
# leia start, näiteks tuple kujul (x, y)

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
current = frontier.get()

# meid ei huvita kõik teed, seega peaks kontrollima, kas current on teemant.
# Kui on, siis katkestame otsingu
# (ja loomulikult jätame teemandi koordinaadid meelde)

for next in graph.neighbors(current): # see osa tuleb suht palju ümber teha.
# tuleb leida sobivad naaberruudud kaardilt
# nagu ta meile ette on antud
if next not in came_from:
frontier.put(next)
came_from[next] = current

# Kui teemant on leitud, tuleb ka teekond rekonstrueerida
# mis andmestruktuurina teekonda esitada, pole oluline,
# aga loomulik viis oleks list
return path
</pre>

== Visualiseerimine ==

Kirjuta kood, mis leitud teekonna väljastab sellisel ASCII-art kujul (kujutatud tee on suvaline näide):

<pre>
** **
*** D.... ***
*** .
. *****
**** . ********
*** . *******
** . ******
***** .**** ***
***** . **
*** .
** . ******
** ***. *******
*** .. *****
.
s
</pre>