Iti0210lab5 - Redigeerimiste ajalugu

PriitJ: /* init() */

2018-03-01T12:59:42Z

__init__()

←Vanem redaktsioon		Redaktsioon: 1. märts 2018, kell 14:59
67. rida:		67. rida:
	* linnad juhuslikus järjekorras		* linnad juhuslikus järjekorras
	* ''nearest neighbour'' ahne otsing		* ''nearest neighbour'' ahne otsing

			Omista algolek atribuudile <code>self.initial</code>

	Millised parameetrid sellel meetodil on, otsusta ise. Oluline on, et otsingu käigus, s.t. <code>TSP</code> klassi sees oleks teada konkreetse instantsi linnade arv ja omavaheliste kauguste maatriks. Võimalikud variandid oleks ette anda instantsi failinimi		Millised parameetrid sellel meetodil on, otsusta ise. Oluline on, et otsingu käigus, s.t. <code>TSP</code> klassi sees oleks teada konkreetse instantsi linnade arv ja omavaheliste kauguste maatriks. Võimalikud variandid oleks ette anda instantsi failinimi

PriitJ – 28. veebruar 2018, kell 13:07

2018-02-28T13:07:52Z

@@ 7. rida: / 7. rida: @@
 TSP puhul on antud linnad. Tuleb leida lühim võimalik marsruut, mis läbib kõik linnad täpselt ühe korra. Marsruut peab olema suletud, ehk lõpp-punkt on sama mis alguspunkt.
-Lokaalse optimumi leidmiseks kasutame ''2-opt'' käiku; vt. [https://en.wikipedia.org/wiki/2-opt wikipedia artikkel]
+Lokaalse optimumi leidmiseks kasutame ''2-opt'' käiku; vt. [https://en.wikipedia.org/wiki/2-opt wikipedia artikkel].
-Lahendame neid ülesannete instantse: [[Media:iti0210lab5.zip]]. Need on võetud suuremast logistikaülesannete benchmarkide paketist [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ TSPLIB].
+Lahendame neid ülesannete instantse: [[File:iti0210lab5.zip]]. Need on võetud suuremast logistikaülesannete benchmarkide paketist [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ TSPLIB].
 == Ettevalmistus ==
@@ 58. rida: / 60. rida: @@
 Soovi korral võib kasutada ka muud esitust.
 === Actions ja result ===
@@ 76. rida: / 87. rida: @@
 Leia siin kõik naabrid. Milline neist valitakse, otsustab otsingualgoritm.
 === value() ===
@@ 109. rida: / 111. rida: @@
 == Lisaülesanne ==
-(Mittekohustuslik; tulekul)
+(Mittekohustuslik)

PriitJ: Uus lehekülg: '= Lokaalne otsing = == Sissejuhatus == Lahendame rändkaupmehe (''travelling salesperson problem'' ehk TSP) lokaalse otsinguga. Kasutame [http://github.com/aimacode/aima-python...'

2018-02-25T17:11:29Z

Uus lehekülg: '= Lokaalne otsing = == Sissejuhatus == Lahendame rändkaupmehe (''travelling salesperson problem'' ehk TSP) lokaalse otsinguga. Kasutame [http://github.com/aimacode/aima-python...'

Uus lehekülg

= Lokaalne otsing =

== Sissejuhatus ==

Lahendame rändkaupmehe (''travelling salesperson problem'' ehk TSP) lokaalse otsinguga. Kasutame [http://github.com/aimacode/aima-python aima-python] paketti, kus on vajalikud lokaalse otsingu algoritmid juba olemas. Meie ülesanne on TSP nendele algoritmidele arusaadavalt kirjeldada.

TSP puhul on antud linnad. Tuleb leida lühim võimalik marsruut, mis läbib kõik linnad täpselt ühe korra. Marsruut peab olema suletud, ehk lõpp-punkt on sama mis alguspunkt.

Lokaalse optimumi leidmiseks kasutame ''2-opt'' käiku; vt. [https://en.wikipedia.org/wiki/2-opt wikipedia artikkel]

Lahendame neid ülesannete instantse: [[Media:iti0210lab5.zip]]. Need on võetud suuremast logistikaülesannete benchmarkide paketist [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ TSPLIB].

== Ettevalmistus ==

Hangi endale [http://github.com/aimacode/aima-python aima-python] või analoogne teek mingis teises keeles ([[Iti0210lab4|Eelmise nädala juhend]]).

Kirjuta kood mis loeb ülesande instantsi tekstifailist sisse. Instantsid on sellises formaadis:

N
0 d_12 ... d_1N
d_21 0 ... d_2N
...
d_N1 d_N2 ... 0

Kus <code>N</code> on linnade arv ja <code>d_ij</code> on kaugus linnade <code>i</code> ja <code>j</code> vahel. Sealjuures kui <code>i == j</code>, siis kaugus on alati 0.

Lihtsustamise eesmärgil pole linnade koordinaate vm atribuute antud, mistõttu nende visualiseerimine pole võimalik. See pole aga optimaalse marsruudi leidmiseks ka vajalik. Linnu tähistame numbritega (Pythonis kõige lihtsam võtta vahemik 0..N-1).

== TSP kodeerimine ==

Rändkaupmehe ülesanne tuleb kirjeldada <code>search.Problem</code> klassi kasutades.

Klassi skelett (kui see jääb segaseks, vt uuesti [[Iti0210lab4|eelmise nädala juhendit]]):

<pre>
import search

class TSP(search.Problem):
def __init__(self, ülejäänud parameetrid):
# tekitab otsingu algseisu

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

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

def value(self, state):
# returnib olekule vastava marsruudi pikkuse

</pre>

Pane tähele, et <code>path_cost()</code> pole selles ülesandes oluline, kuna me otsime optimaalset olekut, aga selle leidmise käik pole oluline. Samuti ei saa defineerida <code>goal_test()</code> meetodit, kuna me EI TEA, milline lõppolek on.

=== Oleku esitus ===

Kuna lahendus peab läbima kõiki linnu, siis on oluline ainult nende järjekord. Seega oleks loomulik esitusviis kasutada Pythoni listi, kus esimene element on esimesena läbitav linn, teine element järgmine linn jne. Eeldame, et iga olek kujutab endast suletud marsruuti, s.t. listi viimane element ja esimene element on ka ühendatud.

Soovi korral võib kasutada ka muud esitust.

=== Actions ja result ===

Lokaalse otsingu korral annavad <code>actions()</code> ja <code>result()</code> meetodid naaberolekuid. Naaberolekute leidmiseks kasutame ''2-opt'' käiku (vt [https://en.wikipedia.org/wiki/2-opt wikipedia selgitus]).
Laename ka oleku tegemise pseudokoodi wikipediast:

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

Kuna see teeb vanast olekust uue oleku, siis sobib ta <code>result()</code> meetodisse, seega <code>actions()</code> meetodi ülesandeks võiks jääda sobivate ''i, k'' paaride leidmine.

Leia siin kõik naabrid. Milline neist valitakse, otsustab otsingualgoritm.

=== __init__() ===

See meetod peab tekitama mingi algoleku. Võimalikud variandid, kuidas algolekut konstrueerida:
* linnad numbrite järjekorras
* linnad juhuslikus järjekorras
* ''nearest neighbour'' ahne otsing

Millised parameetrid sellel meetodil on, otsusta ise. Oluline on, et otsingu käigus, s.t. <code>TSP</code> klassi sees oleks teada konkreetse instantsi linnade arv ja omavaheliste kauguste maatriks.

=== value() ===

Siin tuleb kokku arvutada mingile olekule vastava marsruudi pikkus. Selleks kasuta omavaheliste kauguste maatriksit. Ära unusta, et marsruut on suletud, ehk siis kaugust viimasest punktist algpunkti tuleb ka arvestada.

OLULINE <code>search</code> mooduli otsingufunktsioonid on mõeldud maksimeerimisülesannete jaoks, TSP on aga minimeerimisülesanne. Seetõttu peab <code>value()</code> tagastama teepikkuse vähenemisel SUUREMA numbri. Kuna meid huvitavad ka reaalsed teepikkused, siis võiks teepikkuse arvutamise osa eraldi meetodina hoida.

Sõltuvalt linnade arvust ülesande instantsis võib olla kasulik laiendada olekut nii, et seal sees hoitakse ka hetke summaarset teepikkust. ''2-opt'' käigu tegemisel lahutatakse sealt siis eemaldatud lõikude pikkus ja liidetakse lisatud lõikude pikkus. 17 linna puhul see veel erilist efekti ei anna.

== Lokaalse otsingu katsetamine ==

Kasuta <code>search</code> mooduli funktsioone, et lahendusi otsida. Optimaalsed (või teadaolevad parimd) lahendused on toodud [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html siin].

<pre>
problem = TSP(sinu parameetrid)
g = search.hill_climbing(problem)
#g = search.simulated_annealing(problem)
# muudame SA parameetreid
#g = search.simulated_annealing(problem, search.exp_schedule(limit=10000))
print(g)
</pre>

== Lisaülesanne ==

(Mittekohustuslik; tulekul)

Iti0210lab5 - Redigeerimiste ajalugu

PriitJ: /* __init__() */

PriitJ – 28. veebruar 2018, kell 13:07

PriitJ: Uus lehekülg: '= Lokaalne otsing = == Sissejuhatus == Lahendame rändkaupmehe (''travelling salesperson problem'' ehk TSP) lokaalse otsinguga. Kasutame [http://github.com/aimacode/aima-python...'

PriitJ: /* init() */