Obchodný cestujúci - 1.diel

Ú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ť a 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 teda š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ť.

obchnodny_cestujci-1jpg
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é.

obchnodny_cestujci-2jpg

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.

obchnodny_cestujci-3jpg

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.
obchnodny_cestujci-4jpg

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.
obchnodny_cestujci-5jpg

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.

Máme teda prvé tvrdenie:

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

obchnodny_cestujci-6jpg

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ť aj 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

obchnodny_cestujci-7jpg
Obr. 7 Príklad pre štvorec, zdroj: vlastný obrázok
obchnodny_cestujci-8jpg
Obr. 8 Príklad kosoštvorec, zdroj: vlastný obrázok
obchnodny_cestujci-9jpg
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.
obchnodny_cestujci-10jpg

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:

1.  Zvoľ rádius/ polomer kružnice v okolí (i) – teho uzlu 
2. Prejdi všetky uzly od i=1 po N v nasledujúcom postupe
  • 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)
3. Spočítaj optimálnu dráhu ako sumu od i=1 po i=N všetkých priemerných vzdialenosti PRIEMER(i)

obchnodny_cestujci-11JPG
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.
obchnodny_cestujci-12jpg

Obr. 12 Zóny rôzneho polomeru, zdroj: vlastný obrázok.