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 š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

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 č.13, č.14, 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.

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

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

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

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.

Príklady pre lepšie pochopenie

1. Symetricky rozmiestnené uzly.
2. Asymetricky rozmiestené uzly.

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:

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ý.

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. Pokiaľ 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 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ť).

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.

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.

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.

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 implementované je maličkosť optimalizovať tie dráhy do, čo najkratšej. Zároveň táto metóda ukazuje silu pri veľmi veľkom počte uzlov.

Optimalizácia trasy pre program

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.

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, pokiaľ to je možné). 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.

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.

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, pre veľký počet uzlov. 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 veľmi dobrú cestu, aj v obrovskom počte bodov.

Publikácia venovaná optimalizácii metódy najbližšieho suseda nájdete :

odkaz: https://robopol.sk/blog/vylep%C5%A1enie-metody-najblizsieho-suseda-tsp-problem