English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGrafice și rețeleProblema vânzătorului călător
Să ne gândim, încă o dată, la rețele și hărți. Imaginați-vă că trebuie să vizitați un serviciu de livrare
Camionul de livrare trebuie să viziteze toate orașele, în orice comandă. În problema podurilor din Königsberg am vrut să găsim căi care să călătorească de-a lungul oricărei margini exact una. Acum vrem să găsim căi care vizită fiecare vertex exact o dată. Aceste căi se numesc cicluri hamiltoniene .
Există nenumărate posibilități diferite pentru ciclurile hamiltoniene în grafice complete. De fapt, putem alege orice vertex ca vertex de pornire și apoi să alegem oricare dintre orașele rămase în orice ordine:
Diagram coming soon…
Diagram Coming Soon…
Într-un grafic cu
Aceasta înseamnă că, în total, există ${tsnPaths(tsn1)} căi posibile. O scurtătură pentru acest produs este ${tsn1} ! sau ${tsn1} Factorial .
Vă puteți imagina că este posibil să nu puteți călători direct între două orașe - fără a trece printr-un alt oraș. În acest caz, nu mai avem un grafic complet, iar găsirea numărului de cicluri hamiltoniene, dacă există deloc, devine mult mai dificilă.
Până acum am ignorat faptul că unele orașe ar putea fi mai departe de altele. În viața reală, însă, aceasta este o considerație foarte importantă: nu dorim doar să găsim vreo cale, ci vrem să o găsim pe cea mai scurtă. Aceasta se numește Travelling Travelling Problem . Trebuie rezolvat nu numai în transport și logistică, ci și atunci când poziționați tranzistoarele pe microcipuri, pentru a face computere mai rapide sau când analizați structura
O metodă simplă ar fi să încercați toate căile posibile, găsind lungimea fiecăreia, apoi selectând cea mai scurtă. Cu toate acestea, tocmai am arătat asta, chiar și cu doar
Din păcate, nu există un algoritm mai eficient pentru a rezolva problema vânzătorului în călătorie. În schimb, matematicienii și informaticienii au dezvoltat diferiți algoritmi care găsesc soluții bune , chiar dacă este posibil să nu fie cei mai buni. Acești algoritmi, care dau doar soluții aproximative, se numesc Heuristic .
Încercați să rearanjați orașele de pe această hartă și urmăriți cum se schimbă calea cea mai scurtă dintre ele. Puteți elimina orașele atingând-le și puteți adăuga orașe făcând clic oriunde pe hartă (până la 8):
Greedy Algorithm (sau Algoritmul cel mai apropiat) este foarte simplu: începeți într-un oraș aleatoriu și vă mutați consecutiv în cel mai apropiat oraș pe care nu l-ați vizitat până acum. După ce ați vizitat toate orașele, vă opriți.
Animația va veni în curând ...
Puteți arăta că, în medie, căile găsite folosind algoritmul lacom sunt cu 25% mai lungi decât cea mai scurtă cale posibilă.
Algoritmul 2-Opt începe cu o cale posibilă aleatorie. Apoi, alegeți în mod repetat două muchii și le schimbați în jurul valorii dacă acest lucru ar reduce lungimea căii. Vă opriți atunci când nu puteți reduce lungimea mai departe schimbând orice pereche de margini.
Animația va veni în curând ...
Se dovedește că, cu mult înainte ca computerele să existe chiar, Natura a găsit o modalitate inteligentă de a găsi căi optime între diferite locații: în coloniile de furnici.
Furnicile vor să găsească cele mai scurte rute posibile între cuibul lor și sursele de hrană posibile. Ele pot comunica între ele prin intermediul substanțelor chimice pe care le lasă de-a lungul urmelor lor și pe care alte furnici le pot urma.
- Colonia de furnici trimite numeroase cercete care călătoresc inițial în direcții aleatorii. Odată ce găsesc mâncare, se întorc, lăsând în urmă o urmă de feromoni. * Alte furnici tind să urmeze o potecă atunci când găsesc una, ceea ce îi duce la mâncare. În călătoria lor de întoarcere depun mai multe feromoni, întărind astfel calea. * În timp, feromona se evaporă. Cu cât este mai lungă calea, cu atât mai mult timp este nevoie ca furnicile să călătorească de-a lungul ei și astfel feromona are mai mult timp să se evapore. Căile scurte, pe de altă parte, se pot întări mai repede, astfel încât rezistența lor crește mai repede.
Diagrama care va veni în curând ...
Algoritmii Sistemului de colonii antice (ACS) încearcă să reproducă acest comportament pe computere, folosind multe furnici „virtuale”. Ei pot găsi rapid soluții foarte bune pentru problema vânzătorului în călătorie.
O proprietate deosebit de utilă a algoritmilor ACS este că aceștia pot rula continuu și se pot adapta în timp real la modificările grafice. Aceste modificări ar putea fi cauzate de accidente auto și închideri rutiere în rețelele stradale sau de vârfurile de trafic către serverele web din rețelele de calculatoare.
Problema Traveling Salesman este
Găsirea unui algoritm rapid și exact ar avea implicații grave în domeniul informaticii: ar însemna că există algoritmi rapizi pentru toate problemele dificile NP. De asemenea, aceasta ar face inutilă securitatea Internetului, ceea ce se bazează pe faptul că anumite probleme sunt considerate a fi foarte dificile pentru calculatoare.
Găsirea unui algoritm rapid pentru rezolvarea problemei de vânzător de călători ar rezolva, de asemenea, una dintre cele mai faimoase probleme deschise în matematică și informatică, problema P vs NP . Este una dintre cele șapte