Obchodný cestujúci - 2.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.

Zhrnutie užitočných vlastnosti

  1. B/E, Begin – End si je možné zvoliť ľubovoľne, pretože trajektória je uzavretá. Čo znamená, že v podstate jedno odkiaľ začíname.

  2. Veľkosť optimálnej dráhy, teda približnej dráhy pre kontrolu výsledku vypočítame, podľa Problém obchodný cestujúci – I. Diel.

  3. Každý uzol má minimálne dve spojnice, kde spája predchádzajúci uzol a nasledujúci uzol.

  4. Aby sme dosiahli čo najkratšiu dráhu musíme minimalizovať uzly, ktoré majú viac ako dve spojnice.

  5. Ak chceme mať, čo najkratšiu dráhu nesmieme trasy krížiť, iba výnimočné, ak to nie je možné urobiť inak, neexistuje iná alternatíva.

  6. Musíme maximalizovať taký druh spojníc uzlov, ktoré sú najkratšie pre každé okolie i-teho uzla. Teda musíme mať čo najkratšie spojnice medzi uzlami, aby sme minimalizovali celkovú trasu.

Systémové riešenie problému obchodného cestujúceho

Dostávame sa k jadru riešenia, to je schéma, ktorá bude obecne použiteľná pre riešenie symetricky rozmiestnených uzlov aj asymetricky rozmiestnených uzlov (vid. I. diel).

A, Obvodová technika

V prípade, že je uzlov malo, dostatočne od seba vzdialených je možné použiť obvodovú techniku. viď. obrázok, komentovať to netreba ide o jednoduchú vlastnosť. Dráha tvorí uzavretú krivku. Základ tejto metódy je ten, že hľadáme obvodovú krivku s čo najmenšou veľkosťou. Pri tejto metóde musíme využiť kombinačné schopnosti počítačov. Jednoduché použitie ukazuje obrázok č. 13 a obr. 14.

obchnodny_cestujci-13jpg

Obr. 13 Príklad jednoduchej obvodovej techniky, zdroj: vlastný obrázok

obchnodny_cestujci-14jpg

Obr. 14 Príklad jednoduchej obvodovej techniky, zdroj: vlastný obrázok

B) Metóda Zig - Zag, Cik - Cak

Autor tejto metódy je RoboPol. Táto technika kombinuje obvodovú techniku s technikou rolovania cik – cak. Rolovanie môžeme urobiť tromi spôsobmi a to:
  1. Rolovanie cik - cak -vodorovne
  2. Rolovanie cik - cak - zvislo
  3. Rolovanie cik- cak - kombinované

Na obrázkoch je technika ako postupovať systematicky v spájaní uzlov. Voľba cik - caku závisí hlavne od toho ako sú rozmiestnené uzly. Pokiaľ napríklad sú vodorovné vzdialenosti medzi susednými uzlami menšie ako zvislé, volíme vodorovný cik- cak. V prípade, že je to naopak volíme zvislý cik – cak. Pokiaľ sa to, ale mení miesto od miesta použijeme kombinovaný cik cak. Zelenou farbou je nakreslená obvodová technika s ktorou sa dostaneme: od Begin je najnižší uzol naľavo na najvrchnejší uzol napravo. Od tohto miesta volíme konkrétnu metódu cik – cak.

obchnodny_cestujci-15jpg
Obr. 15 Systémová metóda vodorovného cik - cak, zdroj: vlastný obrázok

obchnodny_cestujci-15jpg
Obr. 16 Systémová metóda zvislého cik - cak, zdroj: vlastný obrázok

obchnodny_cestujci-15jpg
Obr. 17 Systémová metóda kombinovaného Cik- cak, zdroj: vlastný obrázok

Príklady pre lepšie pochopenie

  1. Symetricky rozmiestnené uzly
  2. Asymetricky rozmiestené uzly
Príklad symetricky rozmiestnených uzlov:

obchnodny_cestujci-18jpg
Obr. 18 Vodorovný cik cak, zdroj: vlastný obrázok

Na obrázku č.18 je použitý vodorovný cik - cak. Zelená čiara predstavuje obvodovú techniku, kde sme sa od začiatku B (begin) dostali na najvrchnejší uzol. Všimneme si, že to nie je priama čiara, ale tvorí kľukatú čiaru, pretože vzdialenosti sú po tejto kľukatej dráhe menšie medzi uzlami. Samozrejme v tomto prípade sme mohli zvoliť aj zvislý cik - cak, či kombinovaný.

Príklad asymetricky rozmiestených uzlov:

obchnodny_cestujci-19jpg

Obr. 19 Obvodová technika, asymetrické uzly, zdroj: Vlastný obrázok

Na obrázku č. 19 je použitá len obvodová technika (obvodový cik - cak), pre nedostatok uzlov vnútorný cik - cak nebol použitý. Na obrázku je vidno, že máme ostrov uzlov pospájaných zelenou a prepojených červenou s modrou obvodovou technikou.

obchnodny_cestujci-20jpg

Obr. 20 Kombinovaný cik- cak, zdroj: vlastný obrázok

Na obrázku č.20  sú rozmiestnené uzly s rôznou dĺžkou medzi sebou, použili sme obvodovú techniku nakreslené zelenou, hrubou čiarou a kombinovaný cik - cak. V tomto prípade, už bolo nutné použiť kombinovaný cik - cak, pretože vzdialenosti medzi uzlami sa menili. Je tu nakreslené len jedno riešenie, ale riešení je viac. Všimnime si 4 ostrovčeky uzlov v rohoch. , noPokiaľ by napríklad boli vzdialené od stredu ostrova uzlov viac, potom riešime každý ostrov uzlov samostatne. Pre dopravu, kde je napríklad diaľnica medzi mestami sa potom môže stať, že sa vraciame po tej istej dráhe späť. V tomto prípade však lepšie riešenie, kratšie bolo ako je pospájané na obrázku. Samozrejme pri počítači sa bude dať nájsť aj kratšie riešenie (vďaka kombináciám, ktoré môže preveriť).

obchnodny_cestujci-21jpg

Obr. 21 Kombinovaný cik - cak, zdroj: vlastný obrázok

Príklad - asymetrické uzly - metóda kombinovaný cik - cak. Z B=E v ľavom dolnom rohu sme sa cez obvodovú techniku (obvodový cik - cak) dostali do pravého, horného rohu odkiaľ je použitý vnútorný, kombinovaný cik - cak.

obchodny cestujucipng

Obr. 22 Kombinovaný cik- cak, zdroj: vlastný obrázok

Príklad - asymetrické uzly - metóda kombinovaný cik - cak. Z B=E v ľavom dolnom rohu sme sa cez obvodovú techniku (obvodový cik - cak) dostali do pravého, horného rohu odkiaľ je použitý vnútorný, kombinovaný cik - cak, nosné rolovanie je vodorovný cik - cak. Toto je rýchly nástrel riešenia človekom, pričom ide už o zložitý problém.

Príklady Mapy - vzdušná čiara, obvodová technika + obvodový cik- cak, malá množina na vnútorné cik- caky.

afrikajpg

Obr. 23 Obvodový cik- cak Afrika, zdroj: vlastný obrázok

Toto je ukážka obvodovej techniky vytvorená človekom. Pričom nie je použitý vnútorný cik - cak, pretože obsahuje málo bodov, body sa koncentrujú po obvode.

map002gpng
Obr.24 Obvodový cik - cak, zdroj: internet

Dôkaz správnosti systémového riešenia

Ten dôkaz je prostý a jednoduchý. V každom tu uvedenom riešení príkladu sú dodržané metódy z kapitoly Užitočné vlastnosti (viď. vyššie). Trasy sú blízke optimu, pretože sme dodržali a splnili všetky dôležité zistenia. Pre počítač ak má systémové riešenie je maličkosť optimalizovať tie dráhy do čo najkratšej.

Optimalizácia trasy pre program

Systémové riešenie tú uvedené je možné vylepšiť, optimalizovať tak, aby sme dostali, čo najlepšiu dráhu.

Začiatok trasy B=E

Začiatok B=E je daný výberom. Začiatok je potrebné voliť tak, že po otočíme obrazec o celých 90 stupňov. Celkové pootočenie bude 360 stupňov. Máme teda štyri možné začiatky. Z každého pootočenia volíme jednu najlepšiu variantu, ktorá má najhustejšie zastúpenie bodov/uzlov : z najnižšieho miesta vľavo po najvyššie miesto vpravo hore. Pre túto časť trasy je použitá obvodová technika, preto je najlepšie voliť také natočenie, ktoré ma najlepšie kontinuálne zastúpenie uzlov, tak aj vzdialenosti medzi nimi.

Dve zrkadlové varianty systémového riešenia

Pre každú variantu (celkom 4) zvolíme dve systémové riešenia, ktoré sú si zrkadlovo otočené.  Dostaneme celkovo 8 systémových riešení, najlepšie je samozrejme to najkratšie riešenie. Týmto spôsobom sme pôvodnú techniku obohatili o kombinačné možnosti odkiaľ začať a ako postupovať, v ktorom smere. K obrázku č. 17 urobíme zrkadlový obraz viď. obrázok č.25

11-otocjpg

Obr. 25 Zrkadlové riešenie kombinovaný cik - cak

Hľadanie najkratšej trasy

Samozrejme samotné systémové riešenie vyžaduje vylaďovať trasy, optimalizovať na určité vlastnosti a to hlavne (použiť najkratšie spojnice, nekrížiť cesty, použiť dve spojnice pre každý uzol). V prípade zložitejších rozmiestnených uzlov je potrebné pre lepšiu optimalizáciu spájať vo vnútri obrazca uzlov preferované trasy. To sú také trasy kde sú uzly blízko seba a okolie uzlov je ďalej. Týmto si predom určíme postup trasy a cik - cak tomu budeme musieť prispôsobiť. Pozrime si rovno obrázok, čo sa pod tým rozumie. Na obrázku č.26 sú zakreslené niektoré časti trasy v zmysle preferovaných najkratších dĺžok.

obchnodny_cestujci-27jpg

Obr. 26 Rekonštrukcia hľadania najkratšej trasy, zdroj: vlastný obrázok

Pekne túto vlastnosť vidno na mape Afriky (zvýraznené oblasti modrou farbou). Modré oblasti ukazujú preferované kúsky trasy, ktoré je potrebné využiť pretože majú najkratšie dráhy, musíme ich použiť, aby sme sa priblížili k celkovému optimu trasy.

afrika2jpg

Obr. 27 Hľadanie optimálnej trasy Afrika, zdroj: vlastný obrázok

Záver

S popísaným systémovými metódami cik-caku si každý môže vyskúšať efektívnosť tejto metódy pre rôzne rozmiestnené uzly. Som presvedčený, že táto metóda je najefektívnejšia v kombinácii s uvedenými pravidlami  hľadania riešenia blížiace sa k optimu. Pokiaľ budeme mať ostrovy uzlov vzdialené medzi sebou dostatočne, aby sme ho nezahrnuli do miestnej kopy/ostrova uzlov, každý jeden ostrov uzlov riešime samostatne a medzi nimi je priama spojnica, ktorá môže byť použitá aj pre návrat do Begin. Pre vytvorenie účinného algoritmu na riešenie problému obchodného cestujúceho sa budú dať využiť spomenuté vlastnosti, no algoritmus bude využívať aj iné vlastnosti pri hľadaní minima funkcie (známe metódy). Kombináciou by sme získali ten najúčinnejší.

Pri obrovskom počte uzlov, kde výpočtová náročnosť je už obtiažna aj pre počítač postavený algoritmus na uvedených metódach a vlastnostiach nájde dobrú cestu aj v obrovskom počte bodov.