Úvod
Tento článok je venovaný súhrnu, výskumu problému obchodného cestujúceho. V článku nájdete originálne riešenie tohto problému. Metódu popísanú v článku nie je možné kopírovať , vydávať za svoj vlastný nápad, bez odkazu na originálny článok. Túto metódu je možné naprogramovať pre efektívne hľadanie optimálnej cesty. Problém obchodného cestujúceho má široké uplatnenie v doprave a v priemysle (napr. CNC stroje). Riešenie ponúka široké uplatnenie v rôznych oblastiach. Výsledkom je úspora času a financií. V dnešnej dobe existujú rôzne algoritmy na riešenie obchodného cestujúceho, ale vždy ich efektivita výrazne klesá s pribúdajúcim počtom bodov/uzlov.Definície, základné charakteristiky
Majme
štvorcovú sieť na obr. 1, ktorá bude zároveň predstavovať súradnicový systém
x, y. Do tejto siete, keďže bude natoľko jemná zaznačíme všetky uzly, ktoré ma
obchodný cestujúci navštíviť.
Obr.1 Štvorcová sieť, zdroj: vlastný obrázok.
Sieť je definovaná veľkosťou najmenšieho štvorca o veľkosti a x a. Na obrázku č.2 je zaznačený Begin(začiatok) a END(koniec) cesty obchodného cestujúceho. Na obrázku sú najtriviálnejšie možnosti o počte uzlov: 3,4. Modrou farbou sú zaznačené najoptimálnejšie trasy, cez jednotlivé uzly. Smer trasy ponúka, pre každý prípad iba dve možnosti, ktoré sú si symetrické.
Obr. 2 Základné charakteristiky, zdroj: vlastný obrázok.
Každý uzol na obr. 3 spája predchádzajúci a nasledujúci uzol, spojnica môže byť v rôznych kombináciách tvaru, ako je neznačné na obrázku. Uzol(i)- je i-ty uzol z celkového množstva uzlov N.
Obr.3 Definície uzlov obchodný cestujúci, zdroj: vlastný obrázok.
Dráhu S definujeme ako súčet všetkých prejdených dráh cez všetky uzly. Na obrázku č.4 je dráha rovná:
S(B,E)=S(1,2)+S(2,3)+S(3,4)+S(4,1)
Obecne ju môžeme definovať:
S(B,E)= ∑<i=1,n>(S(i),(i+1))
Je to suma cez i=1 po n uzlov všetkých dráh, ktoré obchodný cestujúci prešiel.
Obr. 4 definícia dráhy obchodný cestujúci, zdroj: vlastný obrázok.
Rovnomerné rozmiestnenie uzlov
A, Počet uzlov je párna číslo.
Na obr.5 sú nakreslené optimálne dráhy pre párny počet uzlov (horná polovica obrázka). Optimálnych dráh je viac (rovnakej dĺžky). Optimálna dráha je rovná S=N x a.
- N - počet všetkých uzlov.
- a - Je rovnaká vzdialenosť medzi uzlami o veľkosti "a".
Analógiou dostaneme, že najkratšia dráha pre ľubovoľne N je rovná uvedenému vzťahu. Je to najkratšia možná dráha, zo všetkých možných kombinácii dráh, po týchto rovnako vzdialených uzloch.
Obr. 5 Rovnomerné rozmiestnenie uzlov, zdroj: vlastný zdroj.
B, Počet uzlov je nepárne číslo.
Na obr.5 sú nakreslené tri prípady ,takýchto dráh pre 9,15,25 uzlov. Optimálna dráha je rovná:
S(B,E)=(N-1)*a+sqrt(2)*a,
To znamená, že pri nepárnom počte uzlov dráha nemôže byť menšia, ako počet uzlov násobené vzdialenosťou „a“, no máme tam jednu dráhu, ktorá je po prepone trojuholníka o veľkosti (a * sqrt(2)).
Zovšeobecnením pre ľubovoľný počet uzlov máme najkratšiu možnú dráhu o veľkosti S(B,E)= (N-1)*a+sqrt(2)*a,
Dôkaz nejdem písať, pretože nejde o kľúčové tvrdenie, no je potrebné, aby sme vedeli akú veľkosť má najoptimálnejšia možná dráha, pre takto pravidelne rozmiestnené uzly.
Optimálna dráha v takto symetricky, rozmiestnených uzloch má optimálnu dráhu rovnú veľkosti S (vzťahy viď. vyššie) a každý i- ty uzol má len dve spojnice.
Príklady symetrického a asymetrického rozmiestenia uzlov
Prípady kedy máme najmenšiu vzdialenosť medzi uzlami „a“, no uzly už netvoria plochu štvorca, obdĺžnika sú na obr.6.
Obr. 6 Príklady symetrických a asymetrických uzlov, zdroj: vlastný obrázok.
A, symetrické rozloženie bodov.
Symetricky rozložených obrazcov je na obr. 6 :päť. Prvý ma symetriu voči osi x, y, druhý ma symetriu voči x osi, tretí má symetriu na os x, y, štvrtý ma symetriu pootočenú (os x o 45 stupňov), piaty má symetriu voči osi x. Optimálne dráhy sa líšia v rôznych rozložených obrazcoch. Pre prvý máme S(1)=3*√2*a+7a, Druhý: S(2)=14a, Tretí: S(3)12a, štvrtý: S(4)=√2*a+16a, piaty: S(5)= 2*√2*a+8a.
Pre párny počet uzlov, štvorcovej alebo obdĺžnikovej plochy je optimálna dráha rovná S(B,E)=N*a. Toto splňuje obrazec 2,3. Zvyšné tri obrazce nevyskladáme zo štvorcov (a x a). Z tohto dôvodu je vzdialenosť medzi dvoma uzlami uhlopriečka o vzdialenosti √2*a.
B, nesymetrické rozloženie bodov.
Nesymetricky rozložený obrazec je na obr.6 jeden. Nemá symetriu voči žiadnej osi, ani po-otočenej. Optimálna dráha je S(6)=5*√2*a+10a.Ďalšie príklady symetrických uzlov
Obr. 7 Príklad pre štvorec, zdroj: vlastný obrázok.
Obr. 8 Príklad kosoštvorec, zdroj: vlastný obrázok.
Obr. 9 Príklad kruh, zdroj: vlastný obrázok.
Zhrnutie
Je zrejme, že optimálnu dráhu nie je možné jednoduchým spôsobom spočítať, líši sa rozložením uzlov, symetriou voči osiam atď. Potrebujeme mať, ale spôsob akým efektívne budeme vedieť určiť približnú veľkosť optimálnej dráhy s malou chybou. Dôležité je to z dôvodu porovnania nájdenej, optimálnej dráhy algoritmom s tým, akú dĺžku by mala mať tá optimálna dráha určite.
Všeobecný systém s rôzne rozloženými uzlami
Na obr. 10 je všeobecný systém s rôzne rozmiestnenými uzlami, kde vzdialenosť medzi uzlami sa líši (je rozdielna). V zmysle predchádzajúcej kapitoly potrebujeme vyriešiť, akú vzdialenosť by mala optimálna dráha, cez všetky uzly. Nie je nutné, aby táto vzdialenosť bola o presnej veľkosti, ale aby jej hodnota bola blízko tej optimálnej hodnoty. Potrebujeme tento problém vyriešiť bez toho, aby sme uzlami prekladali konkrétne dráhy.
Obr. 10 Všeobecný systém s rôzne rozmiestnenými uzlami, zdroj: vlastný obrázok.
Riešenie priemerných vzdialenosti medzi uzlami
Toto riešenie vychádza z predstavy, že spočítame všetky vzdialenosti, medzi jednotlivými uzlami (i) až (N) v zadefinovanom rádiuse, o zadanej veľkosti. Na obr. 10 sú nakreslené 4 farebné varianty v i- tom uzle, pre rozdielne veľkosti rádiusu oblasti, ktoré budeme pre výpočet potrebovať. Takže principiálny postup je nesledujúci:
- Nájdi všetky okolité uzly vo vnútri kružnice (i) – teho uzlu, zahrň aj uzly nachádzajúce sa na kružnici.
- Vypočítaj vzdialenosti medzi všetkými uzlami z okolia (i) – teho uzla cez Pytagorovu vetu.
- Urob priemernú vzdialenosť okolitých uzlov od (i) – teho uzla, PRIEMER(i.
Obr. 11 Vývojový diagram výpočtu priemerných vzdialenosti, zdroj: vlastný obrázok.
Zóny rôzneho polomeru:
Pre získanie presnejšej hodnoty optimálnej vzdialenosti SOPTIMUM ,by bolo možné urobiť to, aby sme zadefinovali oblasti, kde by sa menil polomer, ako je znázornení na obr. 12.
Obr. 12 Zóny rôzneho polomeru, zdroj: vlastný obrázok.