Introducere
În algoritmi, ca și în viață, negativitatea poate fi un obstacol.
Luați în considerare problema găsirii celei mai scurte căi între două puncte dintr-un grafic - o rețea de noduri conectate prin legături sau margini. Adesea, aceste margini nu sunt interschimbabile: un grafic ar putea reprezenta o hartă rutieră pe care unele drumuri sunt mai lente decât altele sau au taxe mai mari. Informaticii țin cont de aceste diferențe prin asocierea fiecărei margini cu o „greutate” care cuantifică costul deplasării pe acel segment – indiferent dacă acest cost reprezintă timp, bani sau altceva. Începând cu anii 1950, ei au știut cum să găsească cele mai scurte căi, în esență, cât mai repede posibil teoretic, presupunând că toate ponderile sunt numere pozitive.
Dar pe unele grafice ponderile pot fi negative - călătoria de-a lungul unui segment poate compensa costul traversării altuia. Luați în considerare, de exemplu, un șofer de livrare care trebuie să echilibreze costul gazului și al taxelor (reprezentate prin ponderi pozitive) cu veniturile din transportul coletelor (reprezentate prin ponderi negative). În astfel de cazuri, cel mai rapid algoritm cunoscut pe calea cea mai scurtă nu funcționează. Timp de zeci de ani, algoritmii rapidi pentru găsirea celor mai scurte căi pe grafice cu greutate negativă au rămas evazive.
Acum, un trio de informaticieni a rezolvat această problemă de lungă durată. Noul lor Algoritmul, care găsește cele mai scurte căi printr-un grafic de la un anumit nod „sursă” la fiecare alt nod, aproape se potrivește cu viteza pe care o obțineau algoritmii cu greutate pozitivă atât de mult timp în urmă.
În plus, noua abordare folosește tehnici matematice vechi de zeci de ani, evitând metode mai sofisticate care au dominat cercetarea modernă a teoriei grafurilor.
„Nu îmi venea să cred că există un algoritm atât de simplu”, a spus Maximilian Probst Gutenberg, un informatician la Institutul Federal Elvețian de Tehnologie din Zurich. „Totul este acolo de 40 de ani. A fost nevoie doar de cineva să fie cu adevărat inteligent și hotărât să facă totul să funcționeze.”
Limitele lăcomiei
Povestea începe în 1956, când informaticianul olandez Edsger Dijkstra a dezvoltat un algoritm rapid pentru a găsi cele mai scurte căi pe un grafic cu doar greutăți pozitive. Pentru a înțelege, imaginați-vă că începeți de la sursă și explorați graficul câte un nod, notând greutățile marginilor nou descoperite pe măsură ce mergeți. De fiecare dată când vizitați un nod, faceți estimări preliminare ale celor mai scurte căi de la sursă la fiecare dintre vecinii noului nod, actualizând orice estimări existente dacă ați găsit o nouă cale mai scurtă. Pentru a decide ce nod neexplorat să vizitați în continuare, utilizați ceea ce se numește o strategie lacomă: mergeți la oricare dintre cele mai apropiate de sursă, conform estimării dvs. actuale.
Cu ponderi pozitive, calea pe care o parcurge algoritmul lui Dijkstra pentru a vizita fiecare nod pentru prima dată este cu adevărat cea mai scurtă. Cel mai ușor este să vezi că acest lucru este valabil chiar pentru primul pas. Imaginează-ți două noduri A și B conectate printr-o muchie cu greutatea 2. Dacă A este nodul sursă și orice altă muchie care îl atinge are o greutate mai mare, atunci calea directă de la A la B trebuie să fie cea mai scurtă cale posibilă care conectează aceste două puncte. , deoarece primul segment al oricărei alte căi ar fi deja mai lung. Raționament similar funcționează la fiecare pas. Algoritmul nu trebuie să se uite niciodată în urmă, așa că este garantat să se termine după ce parcurge graficul o dată - asta este ceea ce îl face atât de rapid.
Dar greutățile negative înseamnă probleme pentru strategia lacomă a lui Dijkstra. Luați în considerare din nou șoferul nostru de livrare. O rută directă de la A la B care generează un profit mic poate câștiga mai puțini bani decât o cale ocolită care are undeva un mare profit. „Nu poți lua decizii doar pe baza informațiilor locale”, a spus Sanjeev Khanna, un informatician la Universitatea din Pennsylvania. „Este posibil să fii nevoit să faci câteva mișcări aparent suboptime pentru a obține în sfârșit o recompensă reală.”
Timp de zeci de ani, informaticienii care lucrează la grafice cu greutate negativă au încercat să potrivească viteza algoritmului lui Dijkstra cu algoritmi „combinatori” similari. Acestea implică operații discrete - cum ar fi posibilitățile de numărare, modificarea greutăților și ștergerea selectivă a marginilor - care reflectă structura discretă a graficului de bază. Progresul a încetinit însă în anii 1990. Mai recent, cercetătorii au folosit algoritmi de „optimizare continuă”, care împrumută trucuri din calcul. Din păcate, accelerațiile rezultate au fost limitate și au venit adesea cu prețul simplității.
Rupe ciclul
În vara lui 2021, doi informaticieni care au devenit colegi la Universitatea din Copenhaga - Danupon Nanongkai și Christian Wulff-Nilsen — căutau o temă pentru un proiect de cercetare comun. „Christian a spus: „Oh, apropo, eram în vacanță și, din cauza asta, încercam să mă gândesc la ceva foarte ambițios””, își amintește Nanongkai, care este acum la Institutul de Informatică Max Planck din Saarbrucken, Germania. S-au hotărât pe problema celor mai scurte căi cu greutate negativă și au invitat Aaron Bernstein de la Universitatea Rutgers să li se alăture.
Toți cei trei cercetători erau experți în algoritmi grafici combinatori pentru alte probleme și doreau să vadă cât de departe le puteau duce aceste abordări relativ vechi. „Există de fapt o anumită libertate în a lucra la o problemă care este ambițioasă și este deschisă de mult timp”, a spus Bernstein.
Trio-ul a început prin a ignora temporar un subset de grafice posibile: cele care conțin cicluri negative. Acestea sunt căi care se întorc înapoi la locul în care au început după ce au trecut printr-o serie de muchii ale căror greutăți se adună la un număr negativ. Într-un grafic cu cicluri negative atinse de la punctul de plecare, noțiunea de calea cea mai scurtă se strică, deoarece puteți face distanța până la orice nod la fel de negativă (sau la fel de profitabilă) după cum doriți, făcând tururi repetate în jurul ciclului negativ înainte plecând spre destinație.
Cercetătorii au bănuit că căile negative lungi au fost în principal responsabile pentru a îngreuna problema. Așa că au început să se concentreze pe grupuri strânse de noduri din apropiere, care nu pot conține căi lungi negative: asta pentru că dacă două puncte sunt conectate printr-o cale pozitivă scurtă, adăugarea unei căi lungi negative între ele ar crea un ciclu negativ. Într-un grup strâns, „faptul că toți sunt apropiați într-un sens pozitiv vă oferă de fapt informații utile și despre marginile negative”, a spus Bernstein. „Îți spune că lucrurile nu pot fi prea negative.”
Majoritatea graficelor conțin multe astfel de grupuri strânse care sunt doar slab conectate între ele. Dacă cercetătorii ar putea identifica toate clusterele, ei au bănuit că ar putea dezvolta o modalitate de a găsi cele mai scurte căi rapid în cadrul fiecăruia. De acolo, le-ar putea fi mai ușor să conecteze grupuri individuale și să găsească cele mai scurte căi pe graficul original. Dar asta ar necesita identificarea rapidă a regiunilor oricărui grafic în care nodurile sunt apropiate unul de altul - ceva ce nu știau cum să facă. Cheia s-a dovedit a fi o tehnică care își are originea într-o ramură complet diferită a teoriei grafurilor.
Decuparea graficelor
În anii 1980, oamenii de știință în domeniul informaticii au dezvoltat o tehnică numită descompunere cu diametru mic pentru a identifica clusterele strânse într-un grafic și pentru a identifica marginile de șters pentru a separa acele clustere. Această tehnică oferă o modalitate de a împărți graficele în secțiuni independente. A fost inventat pentru a facilita algoritmii „distribuiți”, în care calculele rulează în paralel pe diferite părți ale unui graf, așa că a fost mai puțin util pentru algoritmii cu cele mai scurte căi, care nu au această proprietate.
Bernstein, Nanongkai și Wulff-Nilsen și-au dat seama că descompunerea cu diametru mic i-ar putea ajuta să identifice clustere fără negativitate prea concentrată. Din păcate, algoritmii standard de descompunere cu diametru mic funcționează numai pe grafice nedirecționate - acelea în care fiecare muchie poate fi traversată în ambele direcții. Problema celor mai scurte căi cu greutate negativă, între timp, are sens doar pe graficele direcționate, în care fiecare muchie este o stradă cu sens unic. (În caz contrar, o singură margine negativă nedirecționată ar crea un ciclu negativ constând din hopuri repetate înainte și înapoi de-a lungul acelei margini.) Dacă cercetătorii ar dori să folosească descompunerea cu diametru mic, ar trebui să o adapteze.
Asta au făcut în noua lor ziare. Inspirat de munca trecută în care Bernstein și Wulff-Nilsen colaboraseră cu Probst Gutenberg, ei au dezvoltat o procedură de fracturare pentru graficele direcționate analogă cu descompunerea cu diametru mic. Procedura taie un grafic direcționat arbitrar într-o serie de grupuri strânse, folosind un proces aleatoriu pentru a șterge doar câteva margini. Ulterior, acele clustere sunt conectate printr-o rețea mai rară în care toate marginile sunt îndreptate în aceeași direcție. Acest tip de rețea se numește graf aciclic direcționat sau DAG.
Gândiți-vă la un DAG ca un pârâu în care apa poate curge pe căi diferite: unele căi curg din surse diferite, altele se răspândesc în direcții diferite, iar altele se pot separa și se pot îmbina. Dar nimic nu curge înapoi, deci nu există cicluri; acest lucru face DAG-urile mult mai ușor de lucrat.
Cercetătorii știu de mult cum să găsească rapid cele mai scurte căi pe DAG-uri chiar și cu ponderi negative. Așadar, tehnica de fracturare le-a permis celor trei cercetători să reducă orice grafic direcționat la o combinație de două cazuri speciale - DAG-uri și grupuri strânse - care au fost fiecare ușor de manevrat.
Noul algoritm cu cele mai scurte căi utilizează în mod repetat procedura de fracturare pentru a sparge un grafic în grupuri strânse conectate printr-un DAG. Apoi sparge acele grupuri din ce în ce mai mult. La sfârșitul procesului, clusterele de la nivelul cel mai interior sunt cât mai strâns legate posibil. O parte din motivul pentru care algoritmul este atât de rapid este că nu sunt necesare multe iterații pentru a descompune complet chiar și un grafic foarte mare, la fel cum nu durează mult pentru a reduce un număr mare la o dimensiune rezonabilă dacă împărțiți în mod repetat. e pe jumătate.
Cu graficul complet defalcat în acest mod, cercetătorii au putut găsi rapid cele mai scurte căi prin fiecare parte a graficului. Pentru grupurile strânse de la nivelul cel mai interior al structurii grafice imbricate, acest lucru a fost ușor - practic nu mai aveau nicio negativitate. Iar cercetătorii știau deja cum să găsească cele mai scurte căi pe secțiunile DAG care le unesc.
În cele din urmă, algoritmul adaugă înapoi muchiile eliminate de procesul de fracturare și calculează efectele acestora asupra celor mai scurte căi. Cercetătorii au demonstrat că procesul lor de ștergere aleatorie a marginilor ar necesita aproape întotdeauna doar câteva ștergeri pentru a elimina marginile „înapoi” – genul care ar transforma DAG-ul lor într-un grafic cu cicluri mari. Acest lucru a făcut extrem de puțin probabil ca orice cale mai scurtă să treacă prin prea multe astfel de segmente înapoi, așa că au putut rezolva acest pas final dificil prin combinarea a două metode manuale din anii 1950: algoritmul lui Dijkstra și primul algoritm dezvoltat pentru grafice cu greutate negativă.
„Este o compoziție extrem de inteligentă a acestor idei”, a spus Khanna. Algoritmul este primul pentru graficele cu greutate negativă care rulează în timp „aproape liniar” - ceea ce înseamnă că timpul de rulare este aproape proporțional cu timpul necesar doar pentru a număra toate muchiile, cel mai rapid posibil.
Și cum rămâne cu graficele cu cicluri negative, pe care cercetătorii au decis să le ignore la început? După ce au pus ultimele retușuri ale algoritmului lor cu cele mai scurte căi, ei au arătat că ar putea funcționa și ca un algoritm rapid pentru identificarea ciclurilor negative. Practic, niciun grafic nu era în afara accesului său.
Căi paralele
Bernstein a prezentat rezultatul echipei la conferința Foundations of Computer Science din 2022, unde manuscrisul lor care descrie noul algoritm a fost considerat unul dintre cele mai bune lucrări. The altă hârtie De asemenea, sa întâmplat să descrie un nou algoritm de timp aproape liniar pentru rezolvarea unei probleme de lungă durată în teoria grafurilor.
Acel algoritm, dezvoltat de Probst Gutenberg și alți cinci cercetători, a abordat o problemă mai generală numită flux de cost minim, în care scopul este de a optimiza transportul pe mai multe căi în paralel, iar fiecare margine are o capacitate maximă, precum și un cost asociat. . Problemele cu cele mai scurte căi sunt un caz special de flux cu costuri minime, astfel încât noul algoritm de flux cu costuri minime ar putea fi, de asemenea, utilizat pentru a rezolva problema celor mai scurte căi cu greutate negativă în timp aproape liniar, deși cu o abordare radical diferită.
Echipa care lucrează la fluxul cu costuri minime și-a dezvoltat algoritmul rapid de uz general folosind o sinteză complicată de tehnici combinatorii și de optimizare continuă, care îl face greu de utilizat în practică, cel puțin în prezent. Algoritmul combinatoriu de Bernstein și colegii săi, deși limitat la o problemă mai specifică, își realizează timpul de rulare aproape liniar fără a sacrifica simplitatea.
„Acesta este ceea ce este atât de uimitor la această lucrare”, a spus Probst Gutenberg. „Îl poți explica unui student de licență și îl poți implementa și pe computer.”
Ca rezultat, acest nou algoritm a reînviat interesul pentru abordările combinatorii ale altor probleme din teoria grafurilor. Rămâne de văzut care probleme pot fi rezolvate rapid folosind algoritmi pur combinatori și care necesită într-adevăr tehnicile continue dezvoltate în ultimii 20 de ani.
„Aceasta este o întrebare filozofică pe care încerc să o înțeleg”, a spus Nanongkai. „Această problemă pe calea cea mai scurtă dă puțină speranță.”
- Distribuție de conținut bazat pe SEO și PR. Amplifică-te astăzi.
- Platoblockchain. Web3 Metaverse Intelligence. Cunoștințe amplificate. Accesați Aici.
- Sursa: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/
- ani 20
- 2021
- 2022
- a
- Despre Noi
- Conform
- Cont
- realizat
- peste
- de fapt
- aciclic
- adapta
- Adaugă
- După
- împotriva
- Algoritmul
- algoritmi
- TOATE
- deja
- mereu
- ambițios
- Vechi
- și
- O alta
- separat
- abordare
- abordari
- în jurul
- asociate
- înapoi
- Sold
- bazat
- deoarece
- deveni
- înainte
- început
- Crede
- Bernstein
- CEL MAI BUN
- între
- Dincolo de
- Mare
- împrumuta
- Branch firma
- Pauză
- pauze
- Spart
- calculează
- denumit
- Capacitate
- caz
- cazuri
- sigur
- CSI
- Închide
- îndeaproape
- Grup
- a colaborat
- colegii
- combinaţie
- combinând
- cum
- calcule
- calculator
- Informatică
- Concentrat
- Conferință
- legat
- Conectarea
- Lua în considerare
- Constând
- continuu
- A costat
- ar putea
- crea
- Curent
- În prezent
- Tăiat
- cicluri
- DAG
- zeci de ani
- hotărât
- Deciziile
- livrare
- descrie
- destinație
- determinat
- dezvolta
- dezvoltat
- FĂCUT
- diferenţele
- diferit
- dificil
- direcționa
- direcţie
- a descoperit
- distanţă
- Nu
- Dont
- jos
- şofer
- Olandeză
- fiecare
- câștiga
- mai ușor
- Cel mai simplu
- Margine
- efecte
- elimina
- eliminat
- activat
- în întregime
- În esență,
- estima
- estimări
- Chiar
- EVER
- toată lumea
- existent
- există
- experți
- Explica
- Explorarea
- extrem
- facilita
- ventilator
- FAST
- cel mai rapid
- federal
- puțini
- final
- În cele din urmă
- Găsi
- descoperire
- descoperiri
- First
- prima dată
- debit
- fluxurilor
- Concentra
- găsit
- Fundații
- Libertate
- din
- complet
- mai mult
- GAS
- General
- scop general
- Germania
- obține
- dat
- oferă
- Go
- scop
- grafic
- grafice
- Lacom
- garantat
- Gutenberg
- Jumătate
- mână
- manipula
- sa întâmplat
- Rubrică
- ajutor
- superior
- speranţă
- Cum
- Cum Pentru a
- Totuși
- HTML
- HTTPS
- idei
- identifica
- punerea în aplicare a
- in
- Venituri
- independent
- individ
- informații
- inspirat
- instanță
- Institut
- interes
- Inventat
- implica
- IT
- iterații
- alătura
- aderarea
- Cheie
- Copil
- Cunoaște
- cunoscut
- mare
- mai mare
- Nivel
- Viaţă
- Limitat
- Limitele
- Link-uri
- local
- Lung
- perioadă lungă de timp
- de lungă durată
- mai lung
- Uite
- făcut
- face
- FACE
- Efectuarea
- manieră
- multe
- Hartă
- Meci
- matematic
- max
- maxim
- mijloace
- Între timp
- Îmbina
- Metode
- ar putea
- Modern
- bani
- mai mult
- mişcă
- în mişcare
- aproape
- negativ
- vecini
- Plase
- reţea
- Nou
- următor
- nod
- noduri
- noțiune
- număr
- numere
- compensa
- ONE
- deschide
- Operațiuni
- optimizare
- Optimizați
- original
- originea
- Altele
- Altele
- in caz contrar
- ofertele
- împerechere
- Hârtie
- lucrări
- Paralel
- parte
- piese
- Care trece
- trecut
- cale
- Pennsylvania
- alege
- Plato
- Informații despre date Platon
- PlatoData
- Punct
- puncte
- pozitiv
- posibilităţile de
- posibil
- practic
- practică
- prezentat
- Problemă
- probleme
- proces
- Profit
- profitabil
- Progres
- proiect
- proprietate
- s-au dovedit
- furnizează
- pur
- Punând
- Quantamagazina
- întrebare
- repede
- radical
- aleator
- repede
- ajunge
- real
- realizat
- motiv
- rezonabil
- recent
- reduce
- reflecta
- regiuni
- relativ
- a ramas
- rămășițe
- repetat
- REPETAT
- reprezenta
- reprezentate
- reprezintă
- necesita
- necesar
- cercetare
- cercetători
- responsabil
- limitat
- rezultat
- rezultând
- Răsplăti
- drum
- Traseul
- Alerga
- funcţionare
- Universitatea Rutgers
- sacrificare
- Said
- acelaşi
- Ştiinţă
- Om de stiinta
- oamenii de stiinta
- căutare
- secțiuni
- segment
- segmente
- sens
- serie
- Stabilit
- câteva
- Pantaloni scurți
- asemănător
- simplu
- simplitate
- întrucât
- singur
- Mărimea
- mic
- So
- REZOLVAREA
- Rezolvarea
- unele
- Cineva
- ceva
- undeva
- sofisticat
- Sursă
- Surse
- special
- specific
- viteză
- VRAJA
- împărţi
- standard
- Începe
- început
- Pornire
- Pas
- Încă
- Poveste
- Strategie
- curent
- stradă
- structura
- student
- astfel de
- de vară
- Elvețian
- Lua
- ia
- luare
- echipă
- tehnici de
- Tehnologia
- spune
- manual
- Graficul
- Sursa
- lor
- lucruri
- trei
- Prin
- timp
- la
- împreună
- de asemenea
- subiect
- emoționant
- de transport
- Traveling
- necaz
- adevărat
- ÎNTORCĂ
- transformat
- care stau la baza
- înţelege
- universitate
- actualizarea
- utilizare
- vacanţă
- practic
- dorit
- Apă
- WebP
- greutate
- Ce
- dacă
- care
- OMS
- în
- fără
- Apartamente
- de lucru
- fabrică
- ar
- ani
- Tu
- Ta
- zephyrnet
- Zurich