Saltzaile ibiltariaren problema

Pertsona bat A puntutik abiatuz, zein da puntu guztiak behin bakarrik zeharkatuz egin dezakeen ibilbide laburrena, A puntura itzuliz berriz ere?

Ikerkuntza operatiboan, saltzaile ibiltariaren ebazkizunak hiri multzo baterako hiri guztiak behin bakarrik, abiapuntura itzuliz, zeharkatzen dituen ibilbide laburrena bilatzen duen ebazkizuna da jatorrian. Planteamendu honetaz gainera, logistikako ebazkizunetarako erabil daitekeena, ebazkizunak beste aplikazio asko ditu, ekoizpen prozesuen antolakuntzan, zirkuituen diseinuan, eta genomaren azterketan esaterako. Ebazkizunaren aldaera ezberdinak daude, esaterako ibilbide luzeeneko ebazkizuna eta hirien arteko distantziak simetrikoak ez direneko ebazkizuna (adibidez, A-B eta B-A distantziak berdinak ez direnean).

Ebazkizunaren soluzioa hiri edo puntu multzo txiki baterako erraza den arren, nahikoa baita ibilbide posible guztiak aztertu eta guztira luzera txikiena duena aukeratzea, ebazkizuna oso konplexua da puntu kopurua handia denean. Adibidez, 80 punturako, permutazioen formula erabiliz, ibilbide posible guztien kopurua 80! (80 faktorial) da, unibertsoko atomo guztien kopurua baino handiagoa dena.

Konputagailu batek ibilbide baten luzera kalkulatzeko mikrosegundo bakar bat emango balu ere, 3 segundo baino gehixeago beharko luke 10 hirietarako ebazkizunaren soluzioa aurkitzeko, minutu erdia baino gehixeago 11 hirietarako soluzioa aurkitzeko eta 77 146 urte 20 hirietarako soluzioa aurkitzeko. Adibidez, 12 hirien arteko ibilbide posible guztiak 479 milioi baino gehiago dira.

Leherketa konbinatorioa deritzon fenomeno honek ekarritako konplexutasuna dela eta, ibilbide posible guztien guztirako distantziak erkatu ordez, ebazpen prozesu laburragoa eskatzen duten heuristika edo soluzio hurbilak edo gutxigorabeherakoak ematen dituzten prozedurak asmatzea.

Ebazkizunaren soluzio hurbilak ematen dituen prozedura sinple bat hurrengo gertuena algoritmoa da, non puntu bat bisitatu ondoren bisitatu beharreko hurrengo puntua bisitatu gabe geratzen den puntu gertuena den. Prozedura honek ordea puntuen arteko egiazko ibilbide laburrenetik urrun geratzen den soluzioak askotan ematen dituela egiaztatu da. Hurrengo gertuena algoritmoa algoritmo irenskorra da.

Ikus, gainera

• Postari txinatarraren ebazkizun

Kanpo estekak

• Datuak: Q322212
• Multimedia: Traveling salesman problem