Ceļojošā pārdevēja problēma
Ceļojošā pārdevēja problēma (bieži saukta par TSP) ir klasiska algoritmiska problēma datorzinātnes un operāciju izpētes jomā. Tā ir vērsta uz optimizāciju. Šajā kontekstā labāks risinājums bieži nozīmē risinājumu, kas ir lētāks, īsāks vai ātrāks. TSP ir matemātiska problēma. To visvieglāk izteikt kā grafiku, kas apraksta mezglu kopas atrašanās vietas.
Ceļojošā pārdevēja problēmu 19. gadsimta 19. gadsimtā definēja īru matemātiķis V. R. Hamiltons un britu matemātiķis Tomass Kirkmans. Hamiltona Ikosa spēle bija izklaides uzdevums, kura pamatā bija Hamiltona cikla atrašana. Šķiet, ka TSP vispārējo formu pirmo reizi pētīja matemātiķi 20. gadsimta 30. gados Vīnē un Hārvardā, īpaši Karls Mengers. Mengers definēja problēmu, apsvēra acīmredzamo brutālās spēka algoritmu un novēroja, ka tuvākā kaimiņa eiritika nav optimāla:
Ar kurjera problēmu (jo praksē šis jautājums būtu jārisina katram pastniekam, katrā ziņā arī daudziem ceļotājiem) apzīmējam uzdevumu atrast īsāko maršrutu, kas savieno punktus, fintificēti daudziem punktiem, kuru pāru attālumi ir zināmi. Protams, šis uzdevums ir atrisināms ar galīgi daudziem mēģinājumiem. Nav zināmi noteikumi, kas mēģinājumu skaitu samazinātu zem doto punktu permutāciju skaita. Noteikums, ka vispirms no sākuma punkta jāiet uz tuvāko punktu, tad uz tam tuvāko punktu utt., kopumā nedod īsāko maršrutu.
Haslers Vitnijs Prinstonas universitātē drīz pēc tam ieviesa nosaukumu ceļojošā pārdevēja problēma.
Pārdevējs vēlas apmeklēt visas pilsētas A, B, C un D. Kāds ir labākais veids, kā to izdarīt (lētākās aviobiļetes un minimāls ceļojuma laiks)?
Pārdevēja optimālais maršruts, apmeklējot 15 lielākās Vācijas pilsētas. Parādītais maršruts ir īsākais no 43 589 145 600 iespējamiem maršrutiem.
Viljams Rovans Hamiltons
Problēmas formulēšana
Ceļojošā pārdevēja problēma apraksta pārdevēju, kuram jāceļo starp N pilsētām. Viņam ir vienalga, kādā secībā viņš to darīs, ja vien viņš ceļojuma laikā apmeklē katru no tām vienu reizi un pabeidz ceļojumu tur, kur viņš bija sākumā. Katra pilsēta ir savienota ar citām tuvējām pilsētām jeb mezgliem, izmantojot lidmašīnas, autoceļus vai dzelzceļu. Katram no šiem savienojumiem starp pilsētām ir viens vai vairāki svari (vai izmaksas). Izmaksas raksturo, cik "grūti" ir šķērsot šo grafika šķautni, un tās var norādīt, piemēram, lidmašīnas vai vilciena biļetes cena vai, iespējams, šķautnes garums, vai laiks, kas nepieciešams, lai veiktu šķautni. Pārdevējs vēlas, lai gan ceļošanas izmaksas, gan nobrauktais attālums būtu pēc iespējas mazāks.
Ceļojošā pārdevēja problēma ir raksturīga lielai "smagu" optimizācijas problēmu klasei, kas jau gadiem ilgi intriģē matemātiķus un datorzinātniekus. Vissvarīgākais ir tas, ka tā ir pielietojama zinātnē un inženierzinātnēs. Piemēram, shēmas plates izgatavošanā ir svarīgi noteikt labāko secību, kādā lāzers izurbj tūkstošiem caurumu. Efektīvs šīs problēmas risinājums samazina ražošanas izmaksas ražotājam.
Grūtības
Kopumā ceļojošā pārdevēja problēma ir grūti atrisināma. Ja ir veids, kā šo problēmu sadalīt mazākās sastāvdaļās, tad tās būs vismaz tikpat sarežģītas kā sākotnējā problēma. Datorzinātnieki to sauc par NP-grūtām problēmām.
Daudzi cilvēki ir pētījuši šo problēmu. Visvienkāršākais (un visdārgākais) risinājums ir vienkārši izmēģināt visas iespējas. Problēma ir tāda, ka N pilsētām ir (N-1) faktoriāla iespēja. Tas nozīmē, ka tikai 10 pilsētām var izmēģināt vairāk nekā 180 tūkstošus kombināciju (tā kā sākuma pilsēta ir definēta, pārējām deviņām pilsētām var būt permutācijas). Mēs skaitām tikai pusi, jo katram maršrutam ir vienāds maršruts pretējā virzienā ar tādu pašu garumu vai izmaksām. 9! / 2 = 181 440
- Problēmas precīzus risinājumus var atrast, izmantojot zaru un robežu algoritmus. Pašlaik tas ir iespējams līdz 85 900 pilsētām.
- Eiristiskās pieejas izmanto vadlīniju kopumu nākamā mezgla izvēlei. Taču, tā kā heiristikas rezultātā tiek iegūtas aproksimācijas, tās ne vienmēr sniedz optimālo risinājumu, lai gan augstas kvalitātes pieļaujamās heiristikas var atrast noderīgu risinājumu daļā laika, kas nepieciešams pilnīgai problēmas risināšanai ar brutālu spēku. Eiristikas piemērs mezglam varētu būt summēšana par to, cik daudz neapmeklētu mezglu atrodas "tuvu" savienotajam mezglam. Tas varētu mudināt pārdevēju apmeklēt tuvumā esošo mezglu grupu, kas sagrupēti kopā, pirms pāriet uz citu dabisku grafa kopu. Skatīt Monte Karlo algoritmus un Lasvegasas algoritmus.
Jautājumi un atbildes
J: Kas ir ceļojošā pārdevēja problēma?
A: Ceļojošā pārdevēja problēma (TSP) ir klasiska algoritmiska problēma datorzinātnes un operāciju izpētes jomā. Tā ir vērsta uz optimizāciju, un labāki risinājumi bieži nozīmē lētākus, īsākus vai ātrākus risinājumus.
J: Kā tiek izteikta TSP?
A: TSP visvieglāk izteikt kā grafiku, kas apraksta mezglu kopas atrašanās vietas.
J: Kas pirmais definēja TSP?
A: Ceļojošā pārdevēja problēmu 19. gadsimta 19. gadsimtā definēja īru matemātiķis V. R. Hamiltons un britu matemātiķis Tomass Kirkmans.
J: Kurš to tālāk pētīja 20. gadsimta 30. gados?
A: 20. gadsimta 30. gados matemātiķi Karls Mengers Vīnē un Hārvardā turpināja pētīt šo problēmu.
J: Ko drīz pēc tam ieviesa Haslers Vitnijs?
A.: Haslers Vitnijs Prinstonas universitātē drīz pēc tās definēšanas ieviesa nosaukumu "ceļojošā pārdevēja problēma".
J: Ko šajā kontekstā nozīmē "labāks risinājums"?
A: Šajā kontekstā labāks risinājums bieži nozīmē lētāku, īsāku vai ātrāku risinājumu.
J: Kādu algoritmu Mengers, pētot TSP, uzskatīja par acīmredzamu?
A: Mengers, pētot TSP, uzskatīja par acīmredzamu brutālā spēka algoritmu un novēroja, ka, izmantojot tuvākā kaimiņa heiristiku, ne vienmēr iegūst optimālus rezultātus.
