Iti0210lab42 - Redigeerimiste ajalugu

PriitJ – 18. märts 2021, kell 10:10

2021-03-18T10:10:04Z

←Vanem redaktsioon		Redaktsioon: 18. märts 2021, kell 12:10
84. rida:		84. rida:
	Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')		Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')

	=== Some high performance results from spring semester 2021 ==		=== Some high performance results from spring semester 2021 ===

	[[Image:Iti0210lab42res.png\|320px\|right\|nqueens performance]]		[[Image:Iti0210lab42res.png\|320px\|right\|nqueens performance]]

PriitJ: /* Kuidas lahendada suuremaid ülesandeid */

2021-03-18T10:09:12Z

Kuidas lahendada suuremaid ülesandeid

←Vanem redaktsioon		Redaktsioon: 18. märts 2021, kell 12:09
83. rida:		83. rida:

	Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')		Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')

			=== Some high performance results from spring semester 2021 ==

			[[Image:Iti0210lab42res.png\|320px\|right\|nqueens performance]]

			{\| class="wikitable"
			! N
			! time, approx
			! algorithm
			! moves
			! language
			\|-
			\| 100000
			\| 2 minutes
			\| FCHC
			\| row shift
			\| Python (PyPy)
			\|-
			\| 50000
			\| 18 min
			\| SA
			\| col swap
			\| Java
			\|-
			\| 50000
			\| 2 hours
			\| FCHC
			\| col swap
			\| Java
			\|}

			Algorithm details:
			* SA - simulated annealing
			* FCHC - first choice hill climbing, with some form of random restart
			* row shift - move is moving a queen to a different row
			* col swap - move is swapping two columns (queens stay at their row)


	[[Category:Iti0210]]		[[Category:Iti0210]]

PriitJ: /* Sissejuhatus */

2021-02-18T16:14:37Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 18. veebruar 2021, kell 18:14
5. rida:		5. rida:
	[[Image:Iti0210lab42.png\|369px\|right\|lipud]]		[[Image:Iti0210lab42.png\|369px\|right\|lipud]]

	Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:~~chapter04b-abbrev2~~.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.		Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:ITI0210_w4.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.

	== Oleku kodeerimine ==		== Oleku kodeerimine ==

PriitJ: /* Oleku kodeerimine */

2021-02-15T15:59:33Z

Oleku kodeerimine

←Vanem redaktsioon		Redaktsioon: 15. veebruar 2021, kell 17:59
13. rida:		13. rida:
	Mõned ideed:		Mõned ideed:
	# Laua suurune, NxN tabel, kus igas ruudus kirjas, mis seal paikneb (lipp või mitte midagi). Kuna see on ruumilise keerukusega O(''n<sup>2</sup>''), siis sobib see ainult väikestele ülesannetele.		# Laua suurune, NxN tabel, kus igas ruudus kirjas, mis seal paikneb (lipp või mitte midagi). Kuna see on ruumilise keerukusega O(''n<sup>2</sup>''), siis sobib see ainult väikestele ülesannetele.
	# Kuna meil on N lippu~~, siis võime lihtsalt teha tabeli, kus igale lipule on antud tema koordinaadid~~		# Kuna meil on N lippu ja iga lipp peab lõpuks olema eraldi veerus, siis fikseerime iga lipu veeru ja muudame ainult rida. Teeme N pikkusega massiivi, nii et positsioonil ''i'' väärtus ''j'' näitab, et lipu koordinaadid on ''(i, j)''.
	~~# Edasiarendus eelmisest: kuna~~ iga lipp peab ~~niikuinii~~ lõpuks olema eraldi veerus, siis ~~teeme~~ N pikkusega massiivi, nii et positsioonil ''i'' väärtus ''j'' näitab, et lipu koordinaadid on ''(i, j)''.		# Iga lipp peab olema eraldi veerus JA real. Seega me võime ka fikseerida mõlemad. Vaatame lauda kui ribasid, mis tuleb õigesse järjekorda panna. Esitus mälus oleks sama kui eelmine.

	~~Otsingukäiguks, ehk tegevuseks~~, mis annab praegusest olekust ühe naaberoleku, ~~võiks olla ühe~~ lipu ringi tõstmine. ~~Ka siin hoiab aega kokku, kui fikseerime iga lipu kindlasse veergu ja liigutame seda alati ainult~~ ridu mööda. ~~See piirab otsingu hargnemistegurit~~.		Otsingukäik on tegevus, mis annab praegusest olekust ühe naaberoleku. Käik sõltub sellest, kuidas olekut esitame.
			# Ühe lipu ringi tõstmine suvalisse kohta.
			# Liigutame ühte lippu ridu mööda üles-alla.
			# Vahetame veerge omavahel või muudame nende järjekorda.

	Oleku väärtuseks on õpikus pakutud selliste lippude paaride arv, mis asuvad samas reas, veerus või diagonaalis. Lahendatud oleku väärtus on 0 ja seega alati väiksem, kui ükskõik millise muu oleku oma. Seega peame seda väärtusfunktsiooni minimeerima.		Oleku väärtuseks on õpikus pakutud selliste lippude paaride arv, mis asuvad samas reas, veerus või diagonaalis. Lahendatud oleku väärtus on 0 ja seega alati väiksem, kui ükskõik millise muu oleku oma. Seega peame seda väärtusfunktsiooni minimeerima.

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

2020-03-09T18:44:14Z

←Vanem redaktsioon		Redaktsioon: 9. märts 2020, kell 20:44
80. rida:		80. rida:

	Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')		Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')

			[[Category:Iti0210]]

PriitJ: /* Sissejuhatus */

2020-03-07T10:03:04Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 7. märts 2020, kell 12:03
6. rida:		6. rida:

	Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:chapter04b-abbrev2.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.		Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:chapter04b-abbrev2.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.

	~~([[Iti0210lab42ex\|Lokaalse otsingu harjutus]])~~

	== Oleku kodeerimine ==		== Oleku kodeerimine ==

PriitJ: /* Sissejuhatus */

2020-02-22T09:28:50Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 22. veebruar 2020, kell 11:28
6. rida:		6. rida:

	Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:chapter04b-abbrev2.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.		Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:chapter04b-abbrev2.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.

			([[Iti0210lab42ex\|Lokaalse otsingu harjutus]])

	== Oleku kodeerimine ==		== Oleku kodeerimine ==

PriitJ: /* Kuidas lahendada suuremaid ülesandeid */

2020-02-19T10:27:32Z

Kuidas lahendada suuremaid ülesandeid

←Vanem redaktsioon		Redaktsioon: 19. veebruar 2020, kell 12:27
75. rida:		75. rida:

	Aga kui kaugele on võimalik minna? Õpiku peatükist 4.1.1 leiame ideid, mida edasi teha:		Aga kui kaugele on võimalik minna? Õpiku peatükist 4.1.1 leiame ideid, mida edasi teha:
	# Oletame, et otsinguruumis esineb piirkondi, kus väärtusfunktsioon on platoo. Tavaline mäeronimine annab selles kohas alla, kui lubame ka võrdset naaberolekut järglaseks võtta, saame edasi liikuda. Otsingu iteratsioonide arv tuleb piirata, muidu võib lõputu tsükkel tekkida.		<!--# Oletame, et otsinguruumis esineb piirkondi, kus väärtusfunktsioon on platoo. Tavaline mäeronimine annab selles kohas alla, kui lubame ka võrdset naaberolekut järglaseks võtta, saame edasi liikuda. Otsingu iteratsioonide arv tuleb piirata, muidu võib lõputu tsükkel tekkida.-->
	# Stohhastilisus: algolek ja käikude järjestus otsingus on juhuslikud. See aitab lokaalsetest miinimumidest "välja raputada", eriti kui kasutad ka järgmist ideed.		# Stohhastilisus: algolek ja käikude järjestus otsingus on juhuslikud. See aitab lokaalsetest miinimumidest "välja raputada", eriti kui kasutad ka järgmist ideed.
	# ''Random restart''. Tee otsingut korduvalt, alustades iga kord juhuslikust algolekust. Kui lahendust ei leita, katkesta otsing üsna ruttu. Jäta meelde, milline nähtud olekutest oli parim.		# ''Random restart''. Tee otsingut korduvalt, alustades iga kord juhuslikust algolekust. Kui lahendust ei leita, katkesta otsing üsna ruttu. Jäta meelde, milline nähtud olekutest oli parim.

	Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')		Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus ''first choice hill climbing'')

PriitJ: /* Mäeronimisotsing */

2019-02-19T11:41:56Z

Mäeronimisotsing

←Vanem redaktsioon		Redaktsioon: 19. veebruar 2019, kell 13:41
62. rida:		62. rida:
	<pre>		<pre>
	pos = NQPosition(4) # test with the tiny 4x4 board first		pos = NQPosition(4) # test with the tiny 4x4 board first
			print("Initial position value", pos.value())
	best_pos, best_value = hill_climbing(pos)		best_pos, best_value = hill_climbing(pos)
	~~print("Initial position value", pos.value())~~
	print("Final value", best_value)		print("Final value", best_value)
	# if best_value is 0, we solved the problem		# if best_value is 0, we solved the problem

PriitJ: /* Sissejuhatus */

2019-02-19T11:39:13Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 19. veebruar 2019, kell 13:39
2. rida:		2. rida:

	Lahendame õpiku mänguülesande, kus tuleb malelauale paigutada lipud nii, et ükski teist ei saaks "ära lüüa" - see tähendab, et üheski reas, veerus ega diagonaalil ei tohi olla üle ühe lipu. Seda ülesannet on võimalik lahendada ka mängulaual, mis on tavalisest malelauast erineva suurusega - alates 4x4 ruudust, kuhu tuleks paigutada 4 lippu. Tähistame seda küljepikkust N. Alati on ka lippude arv sama N.		Lahendame õpiku mänguülesande, kus tuleb malelauale paigutada lipud nii, et ükski teist ei saaks "ära lüüa" - see tähendab, et üheski reas, veerus ega diagonaalil ei tohi olla üle ühe lipu. Seda ülesannet on võimalik lahendada ka mängulaual, mis on tavalisest malelauast erineva suurusega - alates 4x4 ruudust, kuhu tuleks paigutada 4 lippu. Tähistame seda küljepikkust N. Alati on ka lippude arv sama N.

			[[Image:Iti0210lab42.png\|369px\|right\|lipud]]

	Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:chapter04b-abbrev2.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.		Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks [[Media:chapter04b-abbrev2.pdf\|loenguslaididelt]]. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.