Lankide:Anderberru/Proba orria

Problemaren ebazpena

Kasu bereziak

Problema metrikoa

Bidaiariaren problema metrikoan (ingelesez, delta-TSP edo Δ-TSP), hirien arteko distantziek desberdintza triangeluarra betetzen dute. Egia esan, hirien arteko distantziek desberdintasun triangeluarra betetzen duen metrika bat osatzea oso murrizketa naturala da bidaiariaren probleman. Saltzaile ibiltariaren problemaren instantzia askotan betetzen da desberdintza triangeluarra. Horrek esan nahi du, $H_{i}$ eta $H_{j}$ hiriak ertz batez konektaturik badaude, $H_{i}$-tik $H_{j}$-ra dagoen distantzia $H_{k}$ hiritik pasata dagoena baino txikiagoa dela:

$d(H_{i},H_{j})\leq d(H_{i},H_{k})+d(H_{k},H_{j})$.

Tarteko $H_{k}$ hiri batetik pasatzean, ertzak zabaldu egiten dira eta ondorioz metrika bat osatzen dute erpin multzoaren gainean. Bidaiaren problemako hiriak planoko puntu direla kontsideratzen bada, hainbat espazio metriko agertzen dira. Hona hemen hainbat adibide, puntuen arteko distantzia metrika desberdinak erabiliz neurtuta:

• Euklidestarra: puntuen arteko distantzia euklidesen distantzia da.

• Lerrozuzena (Manhattanen distantzia): puntuen arteko distantzia puntuen $x$ eta $y$ koordenatuen arteko diferentzien balio absolutuen batura da.

• Maximoaren metrika (Chebyshev distantzia): puntuen arteko distantzia puntuen $x$ eta $y$ koordenatuen arteko diferentzien balio absolutuen maximoa da.

Azken bi metrikak, adibidez, bidaiariaren problemaren aplikazio klasiko batean erabiltzen dira: zirkuitu inprimatuen fabrikazioan (ingelesez, Printed Circuit Board, PCB). Aplikazio horretan, plaka zulatu egin behar da osagaiak plakan kokatzeko eta zulagailuaren ibilbidea planifikatu behar da. “Hiriak” egin beharreko zuloak dira, beraz. Makina zulagailua Manhattanen metrika erabiliz lan egiteko diseinatzen bada, lehenengo koordenatu batean (horizontalean, adibidez) doituko ditu bere mugimenduak eta gero beste koordenatuan (bertikalean). Horrela, puntu batetik bestera mugitzeko denbora bi koordenatuetan egindako mugimenduen batura izango da. Makina zulagailua Chebyshev distantzia (maximoaren metrika) erabiliz lan egiteko diseinatzen bada, aldiz, mugimendua bi koordenatuetan aldiberean doituko da; horrela, puntu batetik bestera mugitzeko denbora bi mugimenduen (horizontalaren eta bertikalaren) arteko maximoa da (motelena).

Berez, saltzaile ibiltariaren probleman hiriak ezin dira bi aldiz bisitatu. Hala ere, hainbat aplikaziotan ez da beharrezkoa murrizketa hori ezartzea. Kasu horietan, metrikoa ez den instantzia simetriko bat instantzia metriko bihur daiteke, horrela: jatorrizko grafoa grafo oso bihurtzen da, eta jatorrizko grafoan $A$tik $B$ra joateko bide motzenaren luzera izango da $A$ eta $B$ hirien arteko ertzaren $d_{AB}$ distantzia grafo osotuan.

Bestalde, desberdintza triangeluarra betetzen duten bidaiariaren problemetan, posiblea da grafoaren zuhaitz estaltzaile minimoetan oinarritutako algoritmoak diseinatzea problema ebazteko (grafoan ziklo hamiltondarra aurkitzeko). Izan ere, zuhaitz horien hedapeneko ertzen distantzien batura bidaiariaren problemarako soluzioaren luzeraren behe-borne bat da. Kontuan izan behar da bidaiariaren ibilbide optimoan ertz bat kenduz bide Hamiltondar bat lortzen dela, hau da, zuhaitz estaltzaile minimo bat grafoan. Horrela, zuhaitz estaltzaile minimoen goi-borneak kontuan hartuz, ibilbidearen hedapenak aztertzen dituen algoritmoa diseina daiteke. Ideia horretan oinarrituz argitaratu den algoritmo bat honakoa da:

1. Grafoan zuhaitz estaltzaile minimo bat aurkitu.
2. Zuhaitzaren ertz guztiak bikoiztu, hau da zuhaitzean $u$ erpinetik $v$ erpinera ertza dagoen guztietan, $v$-tik $u$-ra doan beste ertz bat gehitu. Eragiketa horren ondorioz grafo eulertarra lortzen da.
3. Grafo eulertar horretan zirkuitu eulertar bat aurkitu. Hedapen hori zuhaitzaren hedapenaren bikoitza da.
4. Zirkuitu eulertar horretatik hasierako grafoaren ziklo hamiltondar bat lortu behar da, prozedura honi jarraituz: zirkuitu eulertarra zeharkatu, eta jada bisitatu den erpin batera iristen den bakoitzean, jauzi egin eta hurrengora joaten saiatu zirkuitu eulertarra zeharkatuz.

Froga daiteke azken urratsak funtzionatzen duela. Gainera, desberdintza triangeluarrari esker, 4. urratseko jauzi bakoitza bide laburra da, hau da, zikloaren luzera ez da handitzen. Beraz, bidaiariaren problemaren ibilbide baterako, ibilbide optimoaren bikoitza baino motzagoa da.

Christofidesen algoritmoaren diseinua antzekoa da, baina zuhaitz estaltzaile minimoa beste problema baten soluzioarekin konbinatzen da, parekatze perfektuarenarekin. Algoritmoak gehienez soluzio optimoa baino 1.5 aldiz luzeagoa den ibilaldia itzultzen du. Christofidesen algoritmoa hurbilketa-algoritmoen artean sortu zen lehenetarikoa izan zen. Gertakaria garrantzitsua izan zen, ebazten zailak ziren problemetarako ikuspuntu desberdin bat proposatzen zelako: soluzio optimoa bermatu ordez, hurbilketa on bat lortzea zen helburua. Hasiera batean, Christofidesen algoritmoari Christofidesen heuristikoa esaten zitzaion, "algoritmo" terminoa ez zelako hurbilketa algoritmoetarako erabiltzen.

Problema Euklidestarra

Bidaiariaren problema Euklidestarra edo laua Euklidesen distantzian oinarritzen da. Bidaiariaren problema metrikoaren kasu partikular bat da, distantziak planoan desberdintza triangeluarra betetzen baitu.

Problema orokorra bezala, hau ere NP-gogorra da. Metrika diskretura bihurtutako problema (distantzia zenbaki oso bihurtzea gora biribilduz) NP-osoa da. Hala ere, problema metriko orokorra baino errazagoa da. Adibidez, bidaiariaren problema euklidestarraren instantzia bati dagokion zuhaitz estaltzaile minimoa euklidestarra da eta O (n log n) ordenakoko denboran kalkula daiteke, n izanik hiri kopurua.

Problema asimetrikoa

Kasu gehienetan, hirien arteko distantzia ez da aldatzen noranzkoaren arabera, baina batzuetan $A$-tik $B$-rako distantzia eta $B$-tik $A$-rako distantzia ez da berdina. Problema horiek asimetrikoak direla esaten da. Halako problemen aplikazio praktiko bat "Ibilgailuak Bideratzearen Problema" da (Vehicle Routing Problem, VRP), noranzko bakarrean zeharka daitezkeen kaleak daudenean. Problema asimetrikoak ebaztea zaila izan daitekeenez, aukera bat simetriko bihurtzea da, n tamainako matrize asimetriko batetik 2n tamainako matrize simetriko bat lortuz.

Izan bedi $A$, $B$ eta $C$ puntuen arteko distantziak jasotzen dituen honako 3 × 3 tamainako matrizea. Matrizeak adierazten duen grafo zuzenduan bi ziklo hamiltondar daude (bi ibilbide posible bidaiariarentzat): $\mathrm {A\to B\to C\to A}$ (9ko distantzia) eta $\mathrm {A\to C\to B\to A}$ (12ko distantzia).

Matrize asimetrikoa

	A	B	C
A		1	2
B	6		3
C	5	4

Matrizearen errenkada eta zutabe kopurua bikoizten da, puntu bakoitzarentzat beste puntu "mamu" bat sortuz, $A$ puntuarentzat $A'$ puntu mamua, adibidez. Puntuen eta puntu mamuen arteko distantziari oso balio baxua esleitzen zaie (adibidean −∞), puntu mamu guztiak soluzio optimoan ager daitezen. Jatorrizko matrize asimetrikoa matrize bikoiztuaren behealdeko ezkerreko zatian ikusten da (diagonalean −∞ balioekin), eta matrizea bera baina diagonal nagusiarekiko iraulita goialdeko eskuineko zatian (hau ere bere diagonalean −∞ duelarik). Matrize berrian jatorrizko $A$, $B$ eta $C$ puntuen artean ez dago ertz bidezko konexio zuzenik, ezta $A'$, $B'$ eta $C'$ puntu mamuen artean ere. Erraz ikus daiteke matrize berria simetrikoa dela diagonal nagusiarekiko.

Matrize simetrikoa

	A	B	C	A′	B′	C′
A				−∞	6	5
B				1	−∞	4
C				2	3	−∞
A′	−∞	1	2
B′	6	−∞	3
C′	5	4	−∞

6 × 6 tamainako matrizeak adierazten duen grafo zuzenduan honako ziklo hamiltondarra existitzen da: $\mathrm {A\to A'\to B\to B'\to C\to C'\to A}$. Ikusten den bezala, ibilbidean puntu batetik dagokion puntu mamura joaten da, hau da, $A$, $B$, $C$ puntuak eta horien puntu mamu diren $A'$, $B'$, $C'$ puntuak txandakatzen dira. $\mathrm {A\to A'}$ moduko bikoteetan "jauzi" egiten da, distantzia zero dela interpreta daitekeelako. Horrela, $\mathrm {A\to A'\to B\to B'\to C\to C'\to A}$ zikloa $\mathrm {A\to B\to C\to A}$ bihurtuko da (9ko distantziakoa).

Ebaluazioa

Bidaiariaren problema ebazteko algoritmoak ebaluatzeko, badira liburutegi estandarrak. TSPLIB liburutegian hainbat adibideren instantziak eta erlazionatutako problemak aurki daitezke (ikus TSPLIB kanpo erreferentzien atalean). Instantzia horietako asko egungo hirien zerrendak eta gaur egungo zirkuitu inprimatuen diseinuak dira.