Strokovni-; razpravi?
Algoritmi za reševanje splošnega
problema trgovskega potnika
Vladimir Batsgelj Oddelek za Matematiko, Univerza v Ljubljani
Povzetek
Problem trgovskega potnika (PTP) spada med osnovne probleme kombinatoriCne optimizacije. V Članku je podanih nekaj osnovnih dejstev o PTP in pregled pomembnejšh algontmiCnih pristopov k njegovemu reševanju.
Abstract
The Traveling Salesman Problem (TSP) is one among the basic problems of combinatorial optimization. In the paper some basic facts about TSP are given, followed by an overview of the main algorithmic approaches for solving TSP.
Članek je nastal na osnovi gradiva za 2. seminar Izbrana poglavja iz računalništva na FNT, Oddelek za matematiko in mehaniko. Ljubljana v decembru 1992. Glavni cilj sestavka je bralca seznaniti s problemom trgovskega potnika (PTP) in s pomembnejšimi pristopi k njegovemu reševanju. Pri tem se ne spuščamo v podrobnosti, temveč bralca, ki bi želel izvedeti veC, napotimo na ustrezne vire. Prav tako so iz pregleda izpuščeni algoritmi za posamezne posebne vrste PTP (na primer Evkiidski) [10].
1. OSNOVE
1.1 Optimizacijske naloge
Naj bo na množici d> dana funkcija P : 1R*
min(^P)=Jinf*-PiX> L«
kjer je Hi" = IR u i +<*>,-«]. Množici <i> bomo rekli množica dopustnih rešitev, funkciji P pa namenska ali kriterijs-ka funkcija.
Pogosto pri določitvi množico dopustnih rešitev <I> izhajamo iz širše množice rešitev ii, ki jo je enostavneje opisati. Množico dopustnih rešitev <t> tedaj sestavljajo tiste rešitve X e ii, ki zadoščajo predikatu dopustnosti ali omejitvam </>(X)
tf>-(Q.<l>) = {X<eil :<i>(X)}
Postavimo
Min(<t>,P) = {Xeii : VYe4>:P{Y)>r{X)}
Vsi elementi množice Min|4>,P), če je ta neprazna, imajo isto vrednost kriterijske funkcije P Označimo jo z min{<t>,P) in jo razširimo na primer, ko je množica Min(<t,P) prazna, s predpisom:
Tedaj lahko zapišemo tudi
Min(<I>,P)= {X e<t>: P(X) = min(4>,P)}
Na podoben način lahko vpeljemo tudi Max (O,P) in max(d>,P); ali pa i uporabo zvez:
Ext.I Max(d>,P) = Min(®,-P) fcxt.2 m ax (O, P) = -min(^.-P)
Ti dve zvezi nam omogočata, da se omejimo samo ria Min in min.
Ophmuadjsko liniogo ali nalogo (matematičnega) programiranja dobimo, če dodamo dvojici (<t>,P), glede na značilnosti naloge, vsaj eno od naslednjih, ali njim podobnih, zahtev:
Pl. določi Min{<J>,P) P2. določi X € Min(^,P) P3. določi min(0,P)
upombiui NFOfi M ATI KA
Strokovni-; razpravi?
P4. določi zaporedje (Xj : X( i e IN), tako
da velja lim P(X,) = min(<I\P)
¡■-j«
P5, določi X tako da bo (z dano verjetnostjo) razlika P(X) - min(<J>,P) zadosti majhna. P6. določi X ed>.
Tako zastavljene naloge bi pravzaprav morali označiti (0,Pmin), kajti /a vsako obstaja tudi naloga (<l>,I'max), ki se od nje razlikuje le po tem, da so v pogojih minimumi zamenjani z maksimumi.
Optimizacijski nalogi (<&,Pmin) in (^,Q,min) sta enakovredni, če iz rešitev ene dobimo rešitve druge in obratno. Relacijo enakovrednosti označimo z s. Zaradi zvez Extl in Ext.2 je naloga (3>,Pmax) enakovredna nalogi (<t\ -IJmin). Zato se lahko v nadaljnem omejimo samo na naloge minimizacije.
Množica optimizacijskih nalog sestavlja optimizacijski problem. Običajno združimo v optimizacijski problem med seboj podobne naloge, ki imajo enako obliko in se razlikujejo le po podatkih. Nalogi, ki pripada optimizaci-jskemu problemu, pravimo tudi primerek problema.
1.1.1. Naloga o prirejanju
n ljudi mora opraviti n opravil. Stroški, ki jih imamo, če človek i opravi opravilo j naj bodo air Ljudem moramo prirediti vsakemu po eno opravilo, tako da bodo skupni stroški najmanjši, prt čemer pa morajo biti opravljena vsa opravila. Zastavljeni problem lahko prevedemo na oplimizaeijsko nalogo (Sn, P, min), kjer je S(1 množica vseh permutacij števil od 1 do n in
n
pM auti)
1=1
V linearni algebri ponavadi permutacijo ir podamo z dvojiško matriko X, določeno s predpisom
xij =Jl i = * (D
(_0 sicer
nalogo o prirejanju pa oblečemo takole: (O, P, min), kjer je I = l..n ,
{X € {0,1 r!: Vi e 1 £ Xjj =l,Vj€I:- 1}
jet	iel
in
P(X) =X a'ix'i
(M)
Pogoji v opisu množice <t> zagotavljajo, da je X matrika neke permutacije. Iz tega zapisa naloge o prirejanju vidimo, da sodi med naloge (ccloštevilskega) linearnega programiranja.
1.1.2. Naloga o trgovskem potniku
Trgovec se je namenil, da bo obšel n mest tako, da se bo v vsakem mudil samo enkrat. Znane so razdalje d|j med posameznimi mesti. Kako naj trgovec potuje, da bo opravil Čim krajšo pot?
Pri formalizaciji problema nadomestimo zemljevid z grafom povezanosti mest G = (V,E). Točke tega grafa so mesta, povezave pa predstavljajo prometne zveze med mesti. Vsaki povezavi je pripisana še pripadajoča razdalja.
Vsakemu trgovčevemu potovanju ustreza Hamiltonov cikel po grafu G. lega lahko popišemo i urejeno n-ter-ko točk n, sestavljeno po pravilu
j = it(i) - ločka j je v ciklu naslednik točke i
Če naj ji popisuje Hamiltonov cikel, mora biti ciklična permu taci ja. Tako dobimo nalogo (T,,, fi min), kjer je F,, množica cikličnih permutacij števil od 1 do n in
jsm-2 id
Najbrž ni potrebno posebej opozarjati na podobnost problema o trgovskem potniku s problemom o prirejanju. Žal je podobnost le površinska - za problem o prirejanju obstajajo učinkoviti algoritmi; problem trgovskega potnika pa je NP-težek, kar med drugim pomeni, da imajo vsi znani (točni) algoritmi zanj eksponentno zahtevnost. Je pa ta podobnost s pridom izkoriščena v nekaterih algoritmih za reševanje problema trgovskega potnika.
1.2. Grafi in problem trgovskega potnika
Naj bo G = (V,A) končen enostaven usmerjen graf z množico točk V in množico povezav A £ V x V
Končno zaporedje točk y = (v(l, v,, v2,...vd), ki zadošča pogoju
Vi € l.,d : (vM, Vj) e A
imenujemo sprehod po G; d je dolžina sprehoda y. Če je V||-Vt(, je sprehod sklenjen ali obhod. Sprehod je osnoven ali ¡x>t, če gre skozi posamezno točko grafa največ enkrat. Osnovnemu obhodu rečemo krajše cikel. Sprehod je poln, če gre skozi vse točke grafa. Polnemu ciklu pravimo tudi Hamiltonov cikel.
Če je A = V x V ¡e graf G poln. V polnem grafu ustrezajo Hamiltonovim ciklom natanko vse ciklične permutacije (z začetno točko).
Urejeno trojico G = {V A, c), kjer je (V, A) graf in C : A IR cena povezav, imenujemo graf z vrednostmi na povezavah. V nadaljnjem bomo predpostavljali, da je cena nenegativna c : A -> 11V-
Cena c zadošča trikotniški neenakosti, če zanjo velja
Vx, y, z e V : c{x,z) + c(/,,y) > c(x,y)
npcmibt mi NFORM ATIKA
Strokovni-; razpravi?
Če ima poleg tega še lastnost Vv e V : c{v,v) = 0, ji bomo rekli oddaljenost. Pozor, oddaljenost ni nujno simetrična Vx,y 6 V: c(x,y) = c(y,x). V primeru, ko lahko točke grafa predstavimo kot točke v IRk in je cena povezave enaka kar Hvklidski razdalji med njenima kiajiščema, govorimo o Evklidski nalogi TP Pogosto se pri predstavitvi omejimo na ravnino 1R2.
Ceno lahko razširimo s povezav na sprehode s predpisom
c(Y) = £ c(\Vi,v¿)
i=i
Morda pa bi lahko trgovski potnik opravil svoje potovanje ceneje, če bi kakšno od mest obiskal večkrat. To je res v primeru na sliki 1, za katerega velja:
c((x,z,y,z,x)) = 4 m c({x,y,z,x)) = 5.
Torej minimalne rešitve naloge TP niso vselej Ha mil tono vi cikli, temveč jih moramo iskati med polnimi obhodi.
z
Slika 1: Minimalne rešitve naloge TP niso vselej Hamiltonovi cikli
Naj bo F(A) množica vseh polnih obhodov grafa G, Tedaj lahko míúgo trgovskega potnika zapišemo kol opti-mizacijsko nalogo
TP - (r(A), c, min)
Množica vseh nalog trgovskega potnika sestavlja problem trgovskega potnika.
Dano ceno č razširimo na množico V x V s predpi-
" c(u,v) (u,v) e A sicer
č{U,V) =
Tedaj velja
Izrek 1. Naloga TP (F(A), c, min) je enakovredna nalogi (F(V x V), Č, min).
Množico Hamillonovih ciklov grafa G označimo s H{A). Nalogo (H{A), C, min) imenujemo naloga o najcenejšem Ham-iltonovem ciklu.
Čeprav v splošnem rešitev NTP ni vedno Hamiltonov cikel, pa velja:
Izrek 2. Če v grafit z vrednostmi na fmvzavah (YV x V c) velja za ceno c trikotniŠka neenakost, obstaja Hamiltonov obhod y g Min(F(V x V),c).
Grafu G = {V,A,c) lahko vselej priredimo nov graf H = (V,V x V,d) takole: Naj bo za u, v e V <u,v> najcenejši sprehod {ali eden izmed njih, čc jih je več) iz u v v po C. Iedaj postavimo:
d(u,v) = £ Cjj
(i,j)e <u,v>
Nova cena d zadošča trikotniški neenakosti.
Izrek 3. Nalaga TP = {T(A), c, min) po C je enakovredna nalogi (H(V x V), d, min) najcenejšega Hamil-tonovega cikla v H.
Torej je vsaka naloga TP prevedljiva na enakovredno nalogo iskanja najcenejšega Hamiltonovega cikla v grafu s ceno, k t zadošča trikotniški neenakosti.
2. ALGORITMI
Problem trgovskega potnika (potujočega trgovca, kramarja) ima svoje začetke v zabavnih (matematičnih) nalogah ¡1] kot sta naloga o požrešnem šahovskem konjičku {Euler, 1759; Vandermonde, 1771) in dvajset tika igra (Sir William Rowan Hamilton, 1856), Prvi je obravnaval splošni problem obstoja Hamiltonovih ciklov Kirkman 1855,
Pravi problem trgovskega potnika je obravnavan v knjigi nasvetov za trgovske potnike, ki je izšla v Nemčiji leta 1832,
V	matematične kroge je PTP zašel v tridesetih letih tega stoletja (Menger, Whitney H., Tucker A.W, Flood M.). Okrog leta 1948 je RAN D corporation, kjer je bilo takrat središče operacijskih raziskav, razpisal nagrado za pomemben izrek o PTP
Leta 1954 so Dantzig, Fulkerson in Johnson objavili prvo rešitev obsežne NTP - 49 mest ZDA; 48 velikih mest v zveznih ameriških državah in Washington DC. Rešitev so določili z nitko na modelu. Optimalnost pa so dokazali z uporabo linernega programiranja, pri katerem so z metodo odsekov (dodatne omejitve) zagotovili cikličnost in celoštevilskost rešitve. Zadostovalo je 25 dodatnih omejitev. Pri pripravi rešitve so uporabili tudi osnovne zamisli metode razveji in omeji. Uporabo odsekov pri reševanju nalog celoštevilskega linearnega programiranja je naprej razvijal Gomory.
V	tistih časih, začetek petdesetih, so se pojavili prvi pomembnejši rezultati v kombinatorični optimizaciji (linearno programiranje, prirejanja, pretoki, razporejanje poslov, ..,). Zato je trdovratnost PTP privlačila posebno pozornost.
,,,W-7WINFORMATIKA
29
Strokovni-; razpravi?
Leta 1963 so Little, Murty, Sweeney in Karel objavili postopek razveji in omeji za reševanje PTP in prvi uporabili termin branch & bound. Postopka razveji in omeji sta za reševanje PTP predlagala že leta 1958 tudi Eastman in Croes. Leta 1970 sta Held in Karp predložila za ocenjevanje mej uporabo Lagrangeovske relaksacije.
Mesto FTP so v svojih Člankih o zahtevnosti problemov razjasnili Cook (1971), Karp (1972) in Levin (1973). PTP je NP-težek; prav tako tudi večina pod problemov (npr. fcvklidski). Ti rezultati nas vodijo v dve smeri:
■	za točno reševanje iT P se najbolje obnesejo izpeljanke metode razveji in omeji. Pri tem je prava umetnost razvoj Čim boljših ocen mej. Leta 1980 sta Crovv-der in Padberg rešila NTP na 318 točkah, ki je bila do 1987, najobsežnejša naloga z dokazano optimalno rešitvijo. Leta 1987 sta I'adberg in Kinaldi objavila optimalne rešitve nalog velikosti 532, 1002 in 2392; leta 1988 pa Grótschel in Holland 666 in 1000 113,
n
■	če je naloga preobsežna ali imamo omejene vire, se moramo zadovoljiti s približnimi rešitvami. Do teh lahko pridemo z raznimi hevristikami, kakršna je na primer najbližji sosed (Menger, 1930), ali pa s postopki lokalne optimizacije.
Poglejmo si posamezne pristope:
2.1 Prebor vseh možnosti
Najpreprostejši točen postopek je prebor vseh možnosti - vseh (n-1)! cikličnih permutacij.
CONST »max - 20;
TYPE vector - ARRAY [l..nmax] OF integer;
matrix - ARRAY 11..nmax, 1..nmax) OF integer;
VAR q, route : vector; v ; matrix;
PROCEDURE perm{)c:ititeger);
VAR i, t; integer; BEGIN
IF THEN BEGIN
C efl; ts vlqlfll iqilj]; write[1st,c:B,' > '); FOR i 1 TO n DO write(Ut ,q[i ] ;3J; FOR i:-l TO n-1 DO ts : - ts + w [q (i ], ql i+1 J ]; writeln(lst,ts;8);
IF ts < bis THEN BEGIN btS : - tSi route : - q END; END ELSE BEGIN per¡n(K*l);
PGR 2 TO k-1 DO BEGIN
t :*q[l); qli| :-qlk];qtM t; perm fit-1);
t Í- q|i); qli) q(k); q[k] ;- t END; END; end (perm!;
BF.GIN
FOR 1 :- 1 TO n DO q|i] i; 0 0; btS maxint; petn(ti);
END.
Žal je ta postopek uporaben le za zelo majhne naloge. Pri polnem preboru rešitev moramo pregledati (n-1)! permutacij.
n_(n-1)! n_(n-1)!
10	362880	16	1307674368000
11	3626800	17	20922789888000
12	39916800	18	355687428096000
13	479001600	20	121645100408832000
14	6227020800	25	620448401733239439360000
15	87178291200	30	8841761993739701954543616000000
Recimo, da program pri polnem preboru (na super-računalniku) pregleda milijon rešitev na sekundo. Tedaj bi pri n= 15 tekel 24.2 ur; pri n = 18 pa že 11.3 let in pri n=30 kar 2,8 I0!7 let.
2.2.	Razveji in omeji
Postopek polnega prebora lahko izboljšamo tako, da s kleščenjem slabih vej, omejimo pregledovanje na obetavne veje. To je osnova postopkov razveji in omeji. Glej Kozak [9L str. 316-324 in 112, 8, 18)].
2.3.	Dinamično programiranje
Dinamično programiranje je eden izmed standardnih pristopov k težkim problemom kombinatorične optimizacije; vendar pri PTP nima večje teže. Glej Kozak [9j, str. 269-271.
2.4.	Monte Carlo - naključne permutacije
Pri zelo obsežnih problemih bi lahko dani obhod naključno določili in izračunali njegovo vrednost
FOR i n DOKNTO 2 DO BEGtN j 1 t trunc[i*randooi);
t :« rOUte|il; routefi] :-route!jl; raute(il t; END;
ts :» w|route[n),route[l]];
FOR i:-l TO n*l DO ts ts + w[route[i],route[i+ll ];
To bi velikokrat ponovili in obdržali najboljšo dobljeno rešitev.
Ta zamisel ne vodi do zadovoljivih rezultatov. Uporabili pa jo bomo za določanje naključnih začetnih rešitev pri postopkih lokalne optimizacije.
2.5.	Lokalna optimizacija
2.5.1. Globalni in lokalni minimumi
Pogosto lahko v dani množici ii definiramo relacijo so-sednosti rešitev S c SI sil, za katero zahtevamo le refle-ksivnost.
Pri diskretnih optimizacij s ki h problemih običajno definiramo sosednost z lokalnimi transformacijami, ki prevedejo eno rešitev v drugo.
2Q opombiw)INFORMATIKA
Strokovni-; razpravi?
Element xei je lokalni minumum glede na S natanko takrat, ko je x e Min(<t>nS(x),P); ali drugače povedano, ko
Ve<t>nS(x) : P(x) £ P(y)
Množico vseh lokalnih minimumov naloge (<]>, P, min) glede na sosednost 5 označimo LocMin(<b, P, S).
Zato, da bi poudarili razliko, pravimo elementom množice Mm(0, P) tudi ghMni minimumi. Očitno je vsak globalni minimum tudi lokalni. Poleg tega velja Se:
Izrek 4. 7m vsako sosednost S je
LocMin(4>, IJOx <I>) = Min(4>, l')c LocMin(<I>, P S) in, čcje 0cQcS,tudi LocMin(d>,IiS)c LocMin{0,pQ).
Relacija sosednosti nam ponuja za reševanje optimiza-cijskih nalog naslednji postopek lokalne optimizacije:
izberi x e O ;
while 3y 6 S{x) n <t> : P(y) < P(x) do x := y ;
Če se postopek izteče v končno korakih, konča v lokalnem minimumu.
QO
Stiha 3. Lokalne transformacije 3-OPT
Pri problemu trgovskega potnika se najpogosteje uporabljajo sosednosti r-OPT pri katerih so sosednje rešitve določene tako, da i/, tekočega cikla odstranimo r povezav in jih nadomestimo z novimi, ki zopet sestavljajo cikel. Na slikah 2 in 3 sta prikazani sosednosti 2-OPT in 3-OPT. Lin je s poskusi pokazal, da je sosednost 3-OPT veliko boljša kot sosednost 2-OPT, učinek sosednosti višjih redov pa ne upravičuje povečane porabe časa [14, 18).
2.5.2.	Ohlajanje
Ohlajanje (simuiated annealing) je izpeljanka postopka lokalne optimizacije, ki se poskuša s posnemanjem gibanja delcev plina izogniti lokalnim minimumom. Prvi ga je okrog leta 1953 predlagal Metropolis s sodelavci; zelo priljubljen pa je postal v zadnjem desetletju. Postopek lokalne optimizacije z ohlajanjem za PTP najdemo v [15] str. 328-334.
Podrobneje je uporaba ohlajanja pri PTP obdelana v [19].
2.5.3.	Prepovedane smeri
Zadnjih nekaj let se uveljavlja druga izboljšava postopkov lokalne optimizacije - uporaba prejJovcdanih smeri {Tabu search) [6]. Pri teh postopkih se vselej premaknemo v sosednjo dovoljeno rešitev z najmanjšo vrednostjo, pri čemer lahko nekatere premike prepovemo. To nam omogoča, da se skobacamo iz lokalnih minimumov in da upoštevamo nabrano informaciji) o prostoru rešitev.
Po poročilih v člankih se pri PTP ti postopki izjemno dobro obnesejo.
2.5.4.	Genetski algoritmi
Eden izmed obetajočih pristopov k (približnemu) reševanju kombinatoričnih optimizacijskih problemov so tudi genetski algoritmi, pri katerih poskušamo s posnemanjem razvoja (reprodukcija, križanje, mutacije) množice rešitev vzgojiti čim boljše rešitve [4J.
2.6. APROKSIMACIJSKI ALGORITMI
o
o
Slika 4. Širjenje delnega cikla
Hevristični algoritmi pogosto temeljijo na načelu požre-sitosti. Pri PTP lahko zgradimo take postopke tako, da zaporedoma dodajamo točke delnemu ciklu. Postopki se med seboj ločijo po odločitvah: katero točko dodati in kam.
i/pombuM NFORM ATIKA
Strokovni-; razpravi?
Pri zelo velikih nalogah lahko poskušamo priti do dobrih rešitev tudi tako, da v postopkih razveji in omeji obdržimo le najbolj obetavne veje.
Označimo c* = min(H(V x V), c) in s c{A) ceno rešitve, ki jo vrne dani aproksimacijski algoritem A. Zanima nas, ali obstaja taka konstanta a, da velja
1 <
c(A) c*
<a
Za algoritem najbližji sosed je mogoče pokazati, da velja
a = ^ {Tin nI + 1)
Sahni in Gonzales sta leta 1976 pokazala, da je tudi problem aproksimacije za splošni PTP NP-teŽek.
Dobro aproksimacijo, a <\ , lahko zagotovimo v primeru, ko je cena c razdalja. Kako to storimo je opisano v |11|.
3. ZAKLJUČEK
Po vzemimo: čeprav je PTP NP-težek problem, ni treba takoj vreči puške v koruzo. Ce narava naše naloge ne zahteva točne rešitve, lahko pridemo razmeroma hitro do precej dobrih rešitev, tudi za naloge z več tisoč točkami, z uporabo postopkov lokalne optimizacije ali njihovih izboljšav. Te postopke je razmeroma enostavno s programirati Za naloge Tp pri katerih je zahtevana točna rešitev, je doseg najboljših postopkov okrog 2000 točk. Ti postopki zahtevajo za svoj razvoj veliko znanja in časa, V našem prostoru (vsaj kolikor je avtorju sestavka znano) še niso dostopni.
LITERATURA
1.	Batagclj V,: I larnlltonova nalogj za grafe. ii. seminar i/. matematike: Zanimiva matematika, DMFA SUS, Ljubljana, 19H0, 1325; Presek 11(1983-84)1,4-16.
2.	Batagclj V.: Oprimizacijskc metode. Zapiski predavanj na F F. H, skripta v pripravi.
.i. t ;hrist<tft(les N,: Graph Thcury; An a I gori th mtc approach, Académie l'tcss, New Yofk, 1975. (ruski prevod: Mir, Moskva, 1978)
4.	Filipič B.: Primerjava genetskih algoritmov na problemu trgovskega potnika. Zbornik XXXV ETAN, Olirid 1991, 257264.
5.	Gibbons A.: Algorithmic Graph Theory. (lam bridge University Press, Cambridge. 1985.
6.	f! lover F.: Tabu search. O RS A Journal on Computing. Fart I: 1(1989)3;; 1*10-2%; Part II: 2(1990)1.4-32.
7.	fir fit sehe! M., [Holland O.: Solution of large-scale symmetric traveling salesman problems. Mathematical Programming 51(1991), 141-202.
K. [ Inrowit/ F.., Sahni S.: Fundamentals of Computet Algorithms. Computer Science Press, Kocki ille, 1978,
9, Ko/.ak J.: Podatkovne strukture in algoritmi. DM FA SKS, Ljubljana. 1986,
111. Lawler F.F., Lenstra J.K., Rinnooy Kan A.Il.fi.. Shmuys D.B.: The Traveling Salesman Problem; A guided tour of.combinatorial optimization. John Wiley, New York, IWi,
1!. Mohar B.: Aproksimacijski postopki /a problem trgovskega potnika. Gradivo za 2. seminar: Izbrana poglavja računalništva, Oddelek /a matematiko, Ljubljana, 1992i
12.	Mu rtv K.: Linear and (lombinaturial Priigra m m ing .John Wiley. New York, 1976.
13.	Padberg M., H i na Id i G.; A Braneh-and-Cut Algorithm fori lie Resolution of Large-scale Symmetric Traveling Salesman Problems. SIAM Review 33(1991)1. fi(>-1tHt.
14.	Papailimitriou G.H., Stieglitz K.; Combinatorial Optimisation; Algorithms and Complexity. Prenrice-HaJj, Engfewood Cliffs, NJ, IW.
15.	Press W.Il„ Flannery B.P., Teukolsky S.A., Vettčrling W.T.: Numerical Kccipcs; The art of scientific computing, Cambridge University Press. Cambridge. 1986.
16.	Reingold E.M., Nievergek J., Deo N.: Combinatorial Algorithms; Theory and practice. Prcniicc-i lall, Englewood CtitTs, NJ. 1977. (ruski prevod: Mir, Moskva. 19K0)
17.	SakoviO V.A.: Isslcdovanic operacij, Višejšaja škola, Minsk, 1985.
18.	Syslo M.M., Deo N., Kowalik J.S.: Discrete Optimization Algorithms; with pascal programs. Prentice-1 ¡all, Eriglewond Cliffs. NJ. 1983,
19.	Zerovnik).-. Algoritem Ohlajanje. Gradivo /a 1. seminar [/brana poglavja i/, računalništva. Oddelek z a matematiko. Ljubljana. 1992.
J2 i$wi4wdNFORMATIKA