Ceļojošā tirgotāja problēma

Ceļojošā tirgotāja problēmai jau vairākus gadus ir pievērsta matemātiķu un datoru zinātnieku uzmanība, jo to ir viegli formulēt, bet grūti atrisināt. Problēmu vienkārši var noteikt: ja ceļojošais tirgotājs vēlas apmeklēt tieši vienu no m sarakstā esošajām pilsētām (kur ceļošanas izmaksas no pilsētas i uz pilsētu j ir cij) un pēc tam atgriezties savā mājas pilsētā, tad kāds ir vislētākais ceļš, pa kuru ceļotājs var doties.
Ceļojošā tirgotāja problēma pieder pie kombinatorikas optimizācijas problēmu apakšklases NP-pilna. Ja ceļojošā tirgotāja problēmai tiks atrasts efektīvs risināšanas algoritms (t.i., algoritms kas garantē atrast optimālu risinājumu ar polinomu izteiktu soļu skaitu), tad efektīvi algoritmus varētu atrast visai NP-pilns klasei. Pašreiz šāds risinājums ceļojošā tirgotāja problēmai nav atrasts. Vai tas nozīmē ka nav iespējams atrisināt šo problēmu lielu instanci? Daudzas lielas mēroga praktiskas optimizācijas problēmas ir atrisinātas balstoties uz iegūtajām zināšanām. 1994. gadā tika atrisināta ceļojošā tirgotāja problēma, kas modelē iespiedplates caurumu urbšanu iespiedplatei ar 7397 caurumiem (pilsētām). 1998. gadā tika atrisināta problēma ar ASV 13509 lielāko pilsētu apceļošanu.…