Priit: /* Kasuta järgmiselt */

2018-10-02T12:13:50Z

Kasuta järgmiselt

Priit: /* Kasuta järgmiselt */

2018-10-02T10:41:00Z

Kasuta järgmiselt

Priit: Uus lehekülg: '= Lokaalne otsing = Lahendame rändkaupleja (TSP) ülesannet lokaalse otsinguga. Ülesanded pärinevad logistikaülesannete teegist [https://www.iwr.uni-heidelberg.de/groups/com...'

2018-10-02T10:35:35Z

Uus lehekülg: '= Lokaalne otsing = Lahendame rändkaupleja (TSP) ülesannet lokaalse otsinguga. Ülesanded pärinevad logistikaülesannete teegist [https://www.iwr.uni-heidelberg.de/groups/com...'

Uus lehekülg

= Lokaalne otsing =

Lahendame rändkaupleja (TSP) ülesannet lokaalse otsinguga. Ülesanded pärinevad logistikaülesannete teegist [https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ TSPLIB]

Rakendame mäeronimis- ja ''simulated annealing'' (SA) algoritme. Neid pole <code>aima-python</code> teegi kasutamisel vaja ise implementeerida.

== Ettevalmistus ==

Laadi alla fail lihtsustatud formaadis väikeste ülesannetega [[Media:Iti0120lab5.zip]]. Ülesanded on kõik tekstifaili kujul, kus esimesel real on linnade arv N ning järgmised NxN rida ja veergu annavad paarikaupa kaugused linnade vahel. Kirjuta kood, mis failist linnade kauguste maatsiksi suudab sisse lugeda. Linnad ise on nimetud, tähistame neid kokkuleppeliselt numbritega 0..N-1 või 1-N. Linnade koordinaadid ei ole antud. Edaspidises tekstis ülesande "instants" viitab konkreetsele linnade ja kauguste kombinatsioonile, millel on teegis ka oma nimi, näiteks <code>gr48</code>.

== 2-Opt heuristik ==

Kasutame [https://en.wikipedia.org/wiki/2-opt Wikipediast] laenatud 2-Opt käigu tegemise algoritmi.

<pre>
2optSwap(route, i, k) {
1. take route[0] to route[i-1] and add them in order to new_route
2. take route[i] to route[k] and add them in reverse order to new_route
3. take route[k+1] to end and add them in order to new_route
return new_route;
}
</pre>

Siin <code>route</code> on hetkeolek, mis on antud linnade listina samas järjekorras, milles neid läbitakse. <code>i, k</code> on kahe linna indeksid, millest järgmised kaared lahti ühendatakse. See tähendab, et võetakse lahti kaared <code>i, i+1</code> ja <code>j, j+1</code>. Pane tähele, et listis viimase linna ja kohal 0 asuva linna vahel on ka kaar.

== TSP klass ==

Kui kasutada <code>search.py</code> moodulit, siis tuleb ülesande klass ehitada umbes nii:

<pre>
class TSP(search.Problem):
def __init__(self, instance):
# laadi sisse ülesanne sobival kujul
# genereeri algolek (võib olla list linnade indeksitest)

def actions(self, state):
# siin genereerime võimalikud lahti ühendatavate graafi kaarte paarid 2-Opt jaoks

def result(self, state, action):
# siin tekitame uue oleku, kus mingid kaared lahti ühendatakse ja teistpidi kokku ühendatakse, kasutades ülalolevat pseudokoodi.
# action on üks i, j paar.

def cost(self, state):
# arvuta (või leia muul viisil) praeguse marsruudi kogupikkus. Ära unusta, et marsruut on suletud.

def value(self, state)
# kuna valmis otsingufunktsioonid arvavad, et mida suurem väärtus, seda parem, siis meie minimeerimisülesande TSP
# lahendamiseks tuleb teepikkusest pöördväärtus võtta.
return 1/(self.cost(state)+1)

</pre>

== Kasuta järgmiselt ==

<pre>
p = search.InstrumentedProblem(TSP("gr48"))
g = search.hill_climbing(p)
print(g.state)
print(p.cost(g.state))
</pre>

Parameeter <code>"gr48"</code> on lihtsalt näide, see eeldaks, et TSP klass oskab avada "gr48.txt" faili ja sealt andmed sisse laadida. Selle töö võib ka enne ära teha ja TSP klassile juba valmis kauguste maatriksi anda.

SA kasutamine vaikimisi parameetritega ja natuke pikendatud otsinguga:

<pre>
g = search.simulated_annealing(p)
#g = search.simulated_annealing(p, search.exp_schedule(limit=10000))
</pre>

== Lisaülesanne ==

Antud kirjelduse järgi lahendades on käikude genereerimine <i>O(N**2)</i> keerukusega linnade arvu N suhtes. Eeldades, et lõpplahenduses on linnad üksteise lähedal, võiks vaadata otsingukäikude genereerimisel ainult linnade paare, kus linn <code>j</code> on linna <code>i</code> <code>k</code> lähima naabri hulgas. Käikude genereerimine oleks siis lineaarse keerukusega <i>O(kN)</i>.

@@ 58. rida: / 58. rida: @@
 p = search.InstrumentedProblem(TSP("gr48"))
 g = search.hill_climbing(p)
-print(g.state)
+print(g)
-print(p.cost(g.state))
+print(p.cost(g))
 </pre>

@@ 70. rida: / 70. rida: @@
 #g = search.simulated_annealing(p, search.exp_schedule(limit=10000))
 </pre>
 == Lisaülesanne ==
 Antud kirjelduse järgi lahendades on käikude genereerimine <i>O(N**2)</i> keerukusega linnade arvu N suhtes. Eeldades, et lõpplahenduses on linnad üksteise lähedal, võiks vaadata otsingukäikude genereerimisel ainult linnade paare, kus linn <code>j</code> on linna <code>i</code> <code>k</code> lähima naabri hulgas. Käikude genereerimine oleks siis lineaarse keerukusega <i>O(kN)</i>.

ITI0120lab5 - Redigeerimiste ajalugu

Priit: /* Kasuta järgmiselt */

Priit: /* Kasuta järgmiselt */

Priit: Uus lehekülg: '= Lokaalne otsing = Lahendame rändkaupleja (TSP) ülesannet lokaalse otsinguga. Ülesanded pärinevad logistikaülesannete teegist [https://www.iwr.uni-heidelberg.de/groups/com...'