Keliaujančio pirklio uždavinys.
Tai grafų teorijoje sprendžiamas uždavinys, kurio formuluotė yra tokia: turint tam tikrą kiekį miestų ir kelionės iš vieno miesto į kitą kainas, reikia rasti pigiausią maršrutą, kad aplankius kiekvieną miestą tik po vieną kartą, maršrutas baigtųsi pradiniame mieste. Teorijoje šis uždavinys formuluojamas ir kitaip – kaip grafe su svoriais rasti mažiausio svorio Hamiltono ciklą. Hamiltono ciklas - tai toks bekrypčio grafo apėjimo kelias, kuris visas viršūnes apeina tik po vieną kartą ir baigiasi pradinėje viršūnėje. Šis uždavinys turi ir kitus pavadinimus – tai keliaujančio pirklio, pardavėjo ar komivojažieriaus problema, pigiausio, greičiausio arba bendrai formuluojant – mažiausių sanaudų maršruto paieška. Uždavinys priskiriamas kombinatorinio optimizavimo problemai. Tai problemų sritis, kuri sprendžiama pasitelkus matematiką ir kompiuterių mokslą, naudoja algoritmų bei algoritmų sudėtingumų teorijas. Šios optimizavimo problemos apima kelias sritis, tokias kaip dirbtinis intelektas, matematika ir programinė įranga. Paprastai sprendžiami uždaviniai, kurie turi labai didelę galimų sprendimų aibę, kaip pavyzdžiui nagrinėjamas keliaujančio pirklio uždavinys, kur maršrutų variantų skaičius didėjant miestų skaičiui, auga greičiau, nei bet kokia laipsninė funkcija.

Apie programą: Programa skirta keliaujančio pirklio uždaviniui spręsti. Uždavinio sąlyga yra atsitiktinai arba pagal tinklelį sugeneruotas miestų žemėlapis. Naudojami trys algoritmai - artimiausio kaimyno, porų sukeitimo ir genetinis. Genetinis algoritmas turi dvi realizacijas - 'Genetic' ir 'Genetic-M', kurios skiriasi populiacijos mutavimo metodais. Yra galimybė pasirinkti miestų ir iteracijų skaičių, genetinio algoritmo tris svarbiausius parametrus - populiaciją, kryžminimo ir mutavimo faktorius.

Privalumai:
- galimybė sugeneruoti iki 2048 taškų(žymiai daugiau nei panašios programos);
- rodomas sprendimo laikas ir gauto maršruto ilgis;
- galimybė naudoti genetinį algoritmą, kuris, parinkus populiaciją ir faktorius, randa optimalų maršrutą per sąlyginai mažą laiką;
- galimybė generuoti taškus, išdėstytus tinkleliu;
- galima pasirinkti iteracijų skaičių;
- galimybė stebėti maršruto paieškos eigą ir bet kuriuo momentu ją nutraukti.

Reiktų padaryti:
- galimybę importuoti taškus;
- galimybę pačiam sudėti taškus;
- galimybę atvaizduoti atstumo konvergavimą grafike;

Parametrai ir mygtukai:
- # of cities - taškų(miestų) skaičius;
- # of iterations - vykdomų iteracijų skaičius(artimiausio kaimyno algoritmo atžvilgiu nedaugiau nei taškų kiekis);
- Population(GA) - populiacijos dydis genetiniams algoritmams;
- Cross Factor(GA) - kryžminamos populiacijos dalis;
- Mute Factor(GA) - mutuojančios populiacijos dalis;
- Distance - pasirinktu algoritmu gautas atstumas per visus taškus;
- Random - išdėstyti taškus atsitiktine tvarka;
- Grid - išdėstyti taškus tinkleliu;
- Nearest Neighbour - naudoti artimiausio kaimyno algortimą;
- 2-optimal - naudoti dviejų porų sukeitimo algoritmą;
- Genetic - naudoti genetinį algoritmą;
- Genetic-M - naudoti genetinį algortimą su modifikuotu populiacijos mutavimo metodu;
- Stop - stabdyti vykdyma.

Algoritmai:
Artimiausio kaimyno(NN).Tai pats seniausias ir pats paprasčiausias euristinis algoritmas maršrutui tarp duotų miestų rasti, priskiriamas prie „godžių“ algoritmų grupės, t.y. tokių algoritmų grupės, kur sprendimo ieškoma išskaidant problemą į mažesnes ir sprendžiant jas pavieniui. Šiuo metodu rastas kelias yra geros kokybės, greitai randamas, bet nėra optimalus. Didžiausias algoritmo minusas yra tai, kad tam tikrais atvejais praleidžiama „plika akim“ matomus trumpesnius maršrutus. Teigiamos savybės yra tai, kad jis gana lengvai realizuojamas, greitai pasiekiamas rezultatas, reikalauja sąlyginai mažai atminties. Uždavinio sprendimas grindžiamas tokiu samprotavimu – ieškomas trumpiausias kelias turi būti sudarytas iš punktų, kurie yra artimiausi prieš tai buvusiems ir kurie dar nė karto nebuvo aplankyti, tuomet rastas kelias bus maksimaliai trumpas. Taigi algoritmą galima suskaidyti į kelis žingsnius: 1. pasirenkamas bet kuris pradinis miestas; 2. randamas arčiausias dar neaplankytas miestas; 3. rastas miestas įtraukiamas į sprendimą ir pažymimas kaip aplankytas; 4. jei visi miestai aplankyti ir grįžtama į pradinį – sprendimas baigiamas; 5. kitu atveju ciklas kartojamas nuo 2 žingsnio. Rasta miestų seka ir yra sprendimas.
Porų sukeitimo(2-opt exchange). Šio algoritmo veikimo principas yra dviejų briaunų panaikinimas, sujungiant viršūnes kitokiu būdu, tikintis gauti trumpesnį maršrutą. Visada yra tik vienas būdas perjungti lankus, kurie įeina į maršrutą, kad išliktų ciklas. Jei pasiūlytas naujasis kelias yra trumpesnis (jei panaikintų briaunų svorių suma didesnė už sujungtų kitokiu būdu), tuomet juo pakeičiame pradinį. Tokia procedūra vykdoma tol kol panaikinamos visos grafo briaunų kilpos. Gaunamas rezultatas vadinamas 2-jų pasirinktųjų rezultatu. Keletas atsitiktinai sugeneruotų algoritmų variantai: Optimizuotas Markov grandinės algoritmas, kuris panaudoja paieškos euristinius subalgoritmus, gali rasti labai artimą kelią optimaliam. Jis naudojamas paieškai iki 700 – 800 miestų. Atsitiktinio kelio pakeitimo algoritmas, yra šiuo metu pagrindinis algoritmas ir naudojamas uždaviniams kurie turi iki 100 000 miestų. Principas yra gana paprastas: iš pradžių pasirenkamas atsitiktinį kelias, tada imami keturis artimiausi taškai, tada sukeičiami jų keliai, taip kad sugeneruotume naują atsitiktinį kelią, tai daroma iki tol, kol pasirinktasis kelias bus trumpesnis už senąjį. Visa tai vykdoma kol tikrasis skaičius bandomas atsitiktiniu keliu nepakeičia viršutinės ribos, ir randamas tas vienas lokalus minimumas su didele tikimybe, ir be abejo, globalųjį minimumą su taip pat didele tikimybe ( didelė tikimybė reiškia, kad likusi tikimybė mažėja rodykliškai/eksponentiškai, priklausomai nuo sprendimo dydžio). Iki 10 000 ir daugiau mazgu, nesėkmės šansas labai nežymus.
Genetinis. Sprendžiant šį uždavinį, genetinis algoritmas sprendimą randa per žymiai mažesnį laiką. Šis sprendimas neduoda šimtaprocentinės garantijos, kad rastasis maršrutas bus geriausias, bet kaip taisyklė, rastieji maršrutai visuomet būna labai artimi geriausiam. Kita gera savybė yra jo greitis. 100 miestų maršrutui rasti užtrunkama mažiau nei viena sekundę. Pats sprendimas vykdomas taip: 1) sudaroma grupė atsitiktinių maršrutų, kurie yra vadinami populiacija, o visa ši populiacija sprendžiama naudojat kitą algoritmą - dažniausiai porų sukeitimo, po įvykdymo gaunama pirmoji karta; 2) pasirenkami keli geriausi maršrutai ir pažymimi kaip tėviniai, juos sukryžminus gaunami antros kartos maršrutai-vaikai, kurie, kaip tikimasi, yra geresni už tėvinius; 3) maršrutai-vaikai mutuoja, taip užtikrinama, kad jie nebus vienodi ir bus didesnė tikimybė rasti geriausią; 4) maršrutai-vaikai pakeičia populiacijoje kelis prasčiausius narius, populiacijos dydis išlieka tas pats, o bendras 'gerumas' neblogesnis, susikuria nauja karta; 5) šie veiksmai kartojami tol, kol pasiekiamas tikslas(pakankamas maršrutas) arba įvykdomas iteracijų(kartų) skaičius.