Iti0210lab4 - Redigeerimiste ajalugu

PriitJ: /* 8-Puzzle kodeerimine */

2018-09-25T12:06:58Z

8-Puzzle kodeerimine

←Vanem redaktsioon		Redaktsioon: 25. september 2018, kell 14:06
42. rida:		42. rida:
	<pre>		<pre>
	problem = EightPuzzle(inistate, goal)		problem = EightPuzzle(inistate, goal)
	goalnode = search.~~breadth_first_search~~(problem)		goalnode = search.breadth_first_graph_search(problem)
	# sammud (tegevused, käigud) algolekust lõppolekuni		# sammud (tegevused, käigud) algolekust lõppolekuni
	print(goalnode.solution())		print(goalnode.solution())

PriitJ: /* Otsingustrateegiate võrdlus */

2018-09-25T12:04:00Z

Otsingustrateegiate võrdlus

←Vanem redaktsioon		Redaktsioon: 25. september 2018, kell 14:04
94. rida:		94. rida:
	<pre>		<pre>
	search.compare_searchers([problem], ["Strateegia", "algolek1"],		search.compare_searchers([problem], ["Strateegia", "algolek1"],
	searchers=[search.~~breadth_first_search~~])		searchers=[search.breadth_first_graph_search])
	</pre>		</pre>

101. rida:		101. rida:
	<pre>		<pre>
	Strateegia algolek1		Strateegia algolek1
	~~breadth_first_search~~ < 45/ 84/ 128/(1, >		breadth_first_graph_search < 45/ 84/ 128/(1, >
	</pre>		</pre>

113. rida:		113. rida:

	<pre>		<pre>
	search.~~breadth_first_search~~		search.breadth_first_graph_search
	search.depth_first_graph_search		search.depth_first_graph_search
	search.iterative_deepening_search		search.iterative_deepening_search

PriitJ: /* Sissejuhatus */

2018-09-25T09:11:31Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 25. september 2018, kell 11:11
5. rida:		5. rida:
	Vaatame, kuidas ülesannet formaliseerida kui olekute ruumi, olekute üleminekuid ja soovitud oleku otsingut. Selleks kasutame [http://github.com/aimacode/aima-python aima-python] paketti.		Vaatame, kuidas ülesannet formaliseerida kui olekute ruumi, olekute üleminekuid ja soovitud oleku otsingut. Selleks kasutame [http://github.com/aimacode/aima-python aima-python] paketti.

	''8-Puzzle'' on vähendatud, 3x3 versioon [https://en.wikipedia.org/wiki/15_puzzle viieteistkümnemängust]. Vaatame, kuidas seda ülesannet samm-sammult formaliseerida ja testime <code>aima-python</code> abil erinevate otsingustrateegiate efektiivsust.		''8-Puzzle'' on vähendatud, 3x3 versioon [https://en.wikipedia.org/wiki/15_puzzle viieteistkümnemängust]. Vaatame, kuidas seda ülesannet samm-sammult formaliseerida ja testime <code>aima-python</code> abil erinevate otsingustrateegiate efektiivsust. Otsingualgoritme ennast pole vaja implementeerida, need on juba olemas ning meil tuleb ülesanne lihtsalt sobival kujul ära kirjeldada.

	== Ettevalmistus ==		== Ettevalmistus ==

PriitJ – 17. veebruar 2018, kell 21:09

2018-02-17T21:09:16Z

←Vanem redaktsioon		Redaktsioon: 17. veebruar 2018, kell 23:09
123. rida:		123. rida:
	4 3 6 1 8 2 5 4		4 3 6 1 8 2 5 4
	7 6 5 7 3 2 3 1		7 6 5 7 3 2 3 1

			== Lisaülesanne ==

			(Mittekohustuslik)

			Leia 8-Puzzle jaoks sobivaid heuristikuid. Ideede saamiseks vt. õpikust 3.6.

			Implementeeri heuristik(ud) oma <code>EightPuzzle</code> klassi meetodina, see võimaldab ligipääsu näit. otsitavale lõppolekule.

			Korda ülalolevat testi nende algoritmidega:

			<pre>
			search.greedy_best_first_graph_search
			search.astar_search
			search.recursive_best_first_search
			</pre>

			Kuna <code>compare_searchers()</code> ei oska nendele heuristiku parameetrit ette anda, siis tee ise vajalik wrapper näiteks nii:

			<pre>
			def astar_h1(p):
			return search.astar_search(p, p.h1)
			</pre>

PriitJ: /* Otsingustrateegiate võrdlus */

2018-02-17T21:00:53Z

Otsingustrateegiate võrdlus

←Vanem redaktsioon		Redaktsioon: 17. veebruar 2018, kell 23:00
109. rida:		109. rida:
	* prindi leitud lahenduse pikkus sammudes		* prindi leitud lahenduse pikkus sammudes
	* lõpeta otsing näit. 10000 või 100000 tsükli järel		* lõpeta otsing näit. 10000 või 100000 tsükli järel

			Vaja on testida selliseid strateegiaid (puuotsingu strateegiaid me ei vaata)

			<pre>
			search.breadth_first_search
			search.depth_first_graph_search
			search.iterative_deepening_search
			</pre>

	Veel algolekuid testimiseks		Veel algolekuid testimiseks

PriitJ: /* Testimine */

2018-02-17T20:57:11Z

Testimine

←Vanem redaktsioon		Redaktsioon: 17. veebruar 2018, kell 22:57
88. rida:		88. rida:
	Seda meetodit pole vaja defineerida, kuna vaikimisi on <code>Problem</code> klassis ühe sammu maksumus 1. 8-Puzzle puhul see sobib, kuna klotside nihutamisega ei ole seotud mingit teepikkust, kulu vms.		Seda meetodit pole vaja defineerida, kuna vaikimisi on <code>Problem</code> klassis ühe sammu maksumus 1. 8-Puzzle puhul see sobib, kuna klotside nihutamisega ei ole seotud mingit teepikkust, kulu vms.

	== ~~Testimine~~ ==		== Otsingustrateegiate võrdlus ==

			Võrdluse tegemiseks uuri <code>search.py</code> lõppu. Seal on funktsioon <code>compare_searchers</code>

	~~Veel olekuid testimiseks~~		<pre>
			search.compare_searchers([problem], ["Strateegia", "algolek1"],
			searchers=[search.breadth_first_search])
			</pre>

	~~1 8 2~~		Tekib umbes selline väljund:
	~~4 3~~
	~~7 6 5~~

	~~5 4~~		<pre>
	6 1 8		Strateegia algolek1
	~~7 3 2~~		breadth_first_search < 45/ 84/ 128/(1, >
			</pre>

	8 6 7		Numbrid tulevad klassist <code>search.InstrumentedProblem</code>. Uuri seda, et aru saada, mida need tähendavad. Põhimõtteliselt huvitab meid läbitud tsüklite arv, ehkki ka genereeritud järglaste arv võib olla oluline mälukasutuse seisukohast.
	2 5 4
	3 1		Testimise lihtsustamiseks võib nii seda klassi kui ka <code>search.py</code> sees olevaid otsingualgoritme modifitseerida:
			* prindi leitud lahenduse pikkus sammudes
			* lõpeta otsing näit. 10000 või 100000 tsükli järel

			Veel algolekuid testimiseks

			1 8 2 5 4 8 6 7
			4 3 6 1 8 2 5 4
			7 6 5 7 3 2 3 1

PriitJ: /* 8-Puzzle kodeerimine */

2018-02-17T20:31:14Z

8-Puzzle kodeerimine

←Vanem redaktsioon		Redaktsioon: 17. veebruar 2018, kell 22:31
61. rida:		61. rida:
	8 4 6 7 8		8 4 6 7 8

			Märkus: kui oled valinud oleku esituse, proovi Pythoni konsoolist, kas <code>hash(olek)</code> toimib. Osad otsingualgoritmid eeldavad seda.

			=== Actions ===

			def actions(self, state):
			# returnib actionite listi

			Tee meetod, mis leiab kõik võimalikud käigud suvalisest etteantud olekust. Seda meetodit rakendatakse iga kord, kui suvalise oleku naaberolekuid otsitakse.

			=== Result ===

			def result(self, state, action):
			# returnib UUE oleku

			Tee meetod, mis returnib oleku, mis tekib kui olekus <code>state</code> tehakse tegevus <code>action</code>. Pane tähele, et <code>state</code> ei tohi modifitseerida. Pead konstrueerima uue oleku.

			=== Goal test ===

			def goal_test(self, state):
			# returnib True kui state on lõppolek

			Kontrolli, kas <code>state</code> on lõppolek. <code>search.Problem</code> lähtekoodi uurides võid veenduda, et selle klassi instantsi initsialiseerimisel pannaks <code>self.goal</code> väärtuseks etteantud lõppolek. Sellega tulebki võrrelda.

			=== Path cost ===

			Seda meetodit pole vaja defineerida, kuna vaikimisi on <code>Problem</code> klassis ühe sammu maksumus 1. 8-Puzzle puhul see sobib, kuna klotside nihutamisega ei ole seotud mingit teepikkust, kulu vms.

	== Testimine ==		== Testimine ==

PriitJ: /* Testimine */

2018-02-17T20:08:16Z

Testimine

←Vanem redaktsioon		Redaktsioon: 17. veebruar 2018, kell 22:08
81. rida:		81. rida:
	4 3		4 3
	7 6 5		7 6 5

			5 4
			6 1 8
			7 3 2

	8 6 7		8 6 7
	2 5 4		2 5 4
	3 1		3 1

PriitJ – 17. veebruar 2018, kell 19:36

2018-02-17T19:36:20Z

←Vanem redaktsioon		Redaktsioon: 17. veebruar 2018, kell 21:36
39. rida:		39. rida:

	Ja seda kasutatakse järgmiselt:		Ja seda kasutatakse järgmiselt:

			<pre>
			problem = EightPuzzle(inistate, goal)
			goalnode = search.breadth_first_search(problem)
			# sammud (tegevused, käigud) algolekust lõppolekuni
			print(goalnode.solution())
			# olekud algolekust lõppolekuni
			print(goalnode.path())
			</pre>

			=== Oleku esitus ===

			Alustada tuleks sellest, et otsustada, kuidas esitada programmis:
			* üks mänguseis, ehk olek
			* üks tegevus (''action''), mis selles mängus on klotsi liigutamine

			eeldame, et algolek ja lõppolek on sellised:

			1 2 3 1 2 3
			7 5 4 5 6
			8 4 6 7 8













			== Testimine ==


			Veel olekuid testimiseks

			1 8 2
			4 3
			7 6 5

			8 6 7
			2 5 4
			3 1

PriitJ – 17. veebruar 2018, kell 19:06

2018-02-17T19:06:34Z

←Vanem redaktsioon		Redaktsioon: 17. veebruar 2018, kell 21:06
6. rida:		6. rida:

	''8-Puzzle'' on vähendatud, 3x3 versioon [https://en.wikipedia.org/wiki/15_puzzle viieteistkümnemängust]. Vaatame, kuidas seda ülesannet samm-sammult formaliseerida ja testime <code>aima-python</code> abil erinevate otsingustrateegiate efektiivsust.		''8-Puzzle'' on vähendatud, 3x3 versioon [https://en.wikipedia.org/wiki/15_puzzle viieteistkümnemängust]. Vaatame, kuidas seda ülesannet samm-sammult formaliseerida ja testime <code>aima-python</code> abil erinevate otsingustrateegiate efektiivsust.

			== Ettevalmistus ==

			Hangi endale AIMA õpiku algoritme implementeeriv teek [http://github.com/aimacode/aima-python siit] (klooni või võta kokkupakitult master branch). <code>aima-python</code> on pigem kogum faile, kui installitav pakett, seetõttu võib selle lihtsalt kusagile lahti pakkida. Kõige lihtsam on edaspidi oma programmifailid ka samasse kataloogi teha.

			Java jaoks on olemas sarnane teek, <code>aima-java</code>. Selle kasutamist tuleb iseseisvalt uurida.

			== 8-Puzzle kodeerimine ==

			Kasutame <code>search</code> moodulit, mis toimib järgmiselt:
			* Ülesanne kirjeldatakse <code>search.Problem</code> klassi kasutades
			* Otsing pannakse käima ülesande instantsi peal (konkreetne algolek ja lõppolek)

			Klassi skelett peaks olema umbes selline (detailsemaks selgituseks vt. [''AIMA''] õpik 3.1.1):

			<pre>
			import search

			class EightPuzzle(search.Problem):
			def actions(self, state):
			# returnib actionite listi

			def result(self, state, action):
			# returnib UUE oleku

			def goal_test(self, state):
			# returnib True kui state on lõppolek

			def path_cost(self, c, state1, action, state2):
			return c + 1 # uus cost peale ühe sammu tegemist
			</pre>

			Ja seda kasutatakse järgmiselt: