PriitJ – 2. veebruar 2021, kell 06:56

2021-02-02T06:56:02Z

←Vanem redaktsioon		Redaktsioon: 2. veebruar 2021, kell 08:56
217. rida:		217. rida:
	</pre>		</pre>

	== Tulemused ~~aruande jaoks~~ ==		== Tulemused ==

	Katseta laiutiotsingut, A*-i ja ahnet otsingut kõikidel kaartidel alates 300x300 suurusest.		Katseta laiutiotsingut, A*-i ja ahnet otsingut kõikidel kaartidel alates 300x300 suurusest.

	~~Aruandesse pane~~:		Mõõda neid asju:
	* lahenduse leidmiseks kulunud aeg (piisab kui on iteratsioonide arv, aga võib lisada ka aja sekundites)		* lahenduse leidmiseks kulunud aeg (piisab kui on iteratsioonide arv, aga võib lisada ka aja sekundites)
	* lahenduse pikkus sammudes		* lahenduse pikkus sammudes

			Nendest katsetuste tulemustest võiks kaitsmisel rääkida. Pane lühike kokkuvõte ka README faili.

	== Optimaalsed tulemused ==		== Optimaalsed tulemused ==

PriitJ: /* Sissejuhatus */

2021-02-02T06:53:47Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 2. veebruar 2021, kell 08:53
8. rida:		8. rida:
	* otsing suuremal kaardil		* otsing suuremal kaardil
	* heuristiline otsing		* heuristiline otsing

			Kasutame mitut erinevat algoritmi. Uurime, kui efektiivselt nad lahenduse leiavad ja kas see on parim lahendus.

	== Esimene katsetus otsinguga ==		== Esimene katsetus otsinguga ==

PriitJ – 9. märts 2020, kell 18:47

2020-03-09T18:47:42Z

←Vanem redaktsioon		Redaktsioon: 9. märts 2020, kell 20:47
275. rida:		275. rida:

	Seejärel muuda otsingut nii, et lubataks ''diagonaalis'' liikumisi. Mis mõju on sellel heuristikute efektiivsusele, eriti A* puhul?		Seejärel muuda otsingut nii, et lubataks ''diagonaalis'' liikumisi. Mis mõju on sellel heuristikute efektiivsusele, eriti A* puhul?

			[[Category:Iti0210]]

PriitJ: /* Laiutiotsing */

2020-02-05T10:20:46Z

Laiutiotsing

←Vanem redaktsioon		Redaktsioon: 5. veebruar 2020, kell 12:20
90. rida:		90. rida:
	from queue import Queue		from queue import Queue

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

PriitJ – 1. veebruar 2020, kell 17:16

2020-02-01T17:16:38Z

Näita muudatusi

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...'

2020-02-01T17:00:29Z

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 "*"). Liikuda tohib ainult neljas suunas: üles, alla, vasakule ja paremale (mitte diagonaalis).

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

Kaart 2:
<pre>
lava_map2 = [
" ********************** ",
" ******* D ********** ",
" ******* ",
" **************** **********",
"*********** ******** ",
" *******************",
" ******** ******************",
"******** ****",
"***** ************ ",
"*** ********* ",
"* ****** ************",
"***************** *******",
"*** **** ***** ",
" ",
" s ",
]
start_row=14
start_col=16
</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''). 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 ==

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 ==

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):
# start (algolek) on 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 (ülal, all,
# paremal ja vasakul olev ruut)
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 ==

Mittekohustuslik, aga väga kasulik lisaülesanne:

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

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

Iti0210lab23 - Redigeerimiste ajalugu

PriitJ – 2. veebruar 2021, kell 06:56

PriitJ: /* Sissejuhatus */

PriitJ – 9. märts 2020, kell 18:47

PriitJ: /* Laiutiotsing */

PriitJ – 1. veebruar 2020, kell 17:16

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...'