Википедија

Problem najšireg puta — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
м Renamed template
Autobot (разговор | доприноси)
1.572.075 измена
м Разне исправке
Ред 14:
Za bilo koji graf, usmeren ili neusmeren, postoji jasan algoritam za traženje najšireg puta, čim je poznata težina ivice minimalne težine: jednostavno se obrišu sve manje grane i traži se bilo koji put između ostalih ivica koristeći [[pretraga u širinu|obilazak stabla u širinu]] (BFS) ili [[pretraga u dubinu|obilazak stabla u dubinu]] (DFS). Na osnovu ovog testa, takođe postoji algoritam linearnog vremena za nalaženje najšireg {{math|''s-t''}} puta u neusmerenom grafu, koji ne koristi maksimalno razapinjuće stablo. Osnovna ideja algoritma je da se algoritam pretrage linearne vremenske složenosti primeni na grani srednje težine, i onda ili da se obrišu sve manje grane ili da se sve veće grane skupe u zavisnosti od toga da li put postoji ili ne postoji, i da se zatim rekurzivno smeste u manji rezultujući graf.
 
{{harvtxtharvnb|Fernandez|Garfinkel|Arbiol|1998}} koriste usko grlo najkraćih puteva u cilju da sastave kompoziciju fotografija iz vazduha kombinovanjem više slika koje prikazuju preklapanje oblasti. U podproblemu gde se problem najšireg puta primenjuje, dve slike su već transformisane u običan koordinatni sistem; preostali zadatak je da se izabere šav, kriva koja prolazi kroz sve regije preklapanja i deli jednu sliku od druge. Pikseli na jednoj strani šava će biti kopirani sa jedne od slika, a pikseli na drugoj strani šava će biti kopirani sa druge slike; za razliku od ostalih metoda kompozicija koji seku piksele sa obe slike, ovaj metod proizvodi važeću fotografsku sliku svakog dela regije koji je uslikan. Oni mere težinu grana mrežastog grafa po numeričkoj proceni , koliko će šav kroz tu tačku da bude vidljiv; izbor najkraćeg puta kao šava, što je bolje nego konvencionalno traženje najkraćeg puta, primorava njihov sistem da nađe šav koga je teško razaznati, što je bolje nego dopustiti zamenu veće vidljivosti jednog dela slike za manju vidljivost bilo gde na slici.
 
Ako su težine svih grana neusmerenog grafa pozitivne, onda minimax udaljenost između parova tačaka (maksimalna težina ivica minimax puta) formira ultrametrički prostor (specijalna vrsta [[metrički prostor|metričkog prostora]]); obrnuto svaki konačan ultrametrički prostor dolazi od minimax udaljenosti. Struktura podataka formirana od minimalnog razapinjućeg stabla dozvoljava da minimax udaljenost između bilo kog para čvorova bude izračunata za konstantno vreme u zavisnosti od udaljenosti, koristeći najmanjeg zajedničkog pretka u [[Dekartovo stablo|Dekartovom stablu]] ([[binarno stablo]]). Koren Dekartovog stabla predstavlja najtežu granu minimalnog razapinjućeg stabla, i deca korena su Dekartova stabla koja su rekurzivno formirana od podstabla minimalnog razapinjućeg stabla formiranog uklanjanjem najtežih grana. Listovi Dekartovog stabla predstavljaju čvorove ulaznog grafa, a minimax rastojanje između dva čvora je jednako težini čvora koji je najmanji zajednički predak Dekartovog stabla. Jednom kad je minimalno razapinjuće stablo sortirano, Dekartovo stablo se može konstruisati za linearno vreme.
Ред 28:
 
Da bi se izračunala najšira širina puta za sve parove čvorova u zbijenom usmerenom grafu, kao graf koji se javlja u primeni u glasanju, asimptotski najbrži mogući pristup ima vremensku složenost {{math|''O''(''n''<sup>(3+ω)/2</sup>)}} gde je ω eksponent za brzo množenje matrica. Koristeći najbolje poznate algoritme za množenje matrica, vremenska složenost postaje {{math|''O''(''n''<sup>2.688</sup>)}}.<ref>{{citation
|last1=Duan| first1 = Ran
|last2=Pettie| first2 = Seth
| contribution = Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths
|pages=384–391
| title = Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09)
| url = http://portal.acm.org/citation.cfm?id=1496813
|year=2009}}. For an earlier algorithm that also used fast matrix multiplication to speed up all pairs widest paths, see {{citation
|last1=Vassilevska| first1 = Virginia
|last2=Williams| first2 = Ryan | author2-link = Ryan Williams (computer scientist)
|last3=Yuster| first3 = Raphael
| contribution = All-pairs bottleneck paths for general graphs in truly sub-cubic time
| doi = 10.1145/1250790.1250876
| mr = 2402484
| location = New York
|pages=585–589
| publisher = ACM
| title = [[Symposium on Theory of Computing|Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC '07)]]
|year=2007}} and Chapter 5 of {{citation|title=Efficient Algorithms for Path Problems in Weighted Graphs|last=Vassilevska|first=Virginia|series=Ph.D. thesis, Report CMU-CS-08-147|year=2008|url=http://www.cs.cmu.edu/afs/cs/Web/People/virgi/thesis.pdf|publisher=Carnegie Mellon University School of Computer Science}}</ref> Nasuprot tome, implementacija Šulcove metode koristi izmenjenu verziju jednostavnijeg [[Flojd-Voršalov algoritam|Flojd-Varšalovog algoritma]], i ima vremensku složenost {{math|''O''(''n''<sup>3</sup>)}}. Za grafove koji su proređeni, bilo bi efikasnije da se više puta primeni algoritam najšireg puta sa pojedinačnim izvorom.
 
=== Jedan izvor ===
 
Ako su grane sortirane na osnovu svojih težina, onda izmenjena verzija [[Dijkstrin algoritam|Dijkstrinog algoritma]] može da računa uska grla između određenog početnog i svakog drugog čvora u grafu, za linearno vreme. Ključna ideja iza ubrzane konvencionalne verzije Dijkstrinog algoritma je da sekvenca rastojanja do svakog čvora, sa ciljem da se čvorovi uzimaju u obzir ovim algoritmom, je monotona podsekvenca svih sortiranih težinskih grana; stoga red sa prioritetom Dijkstrinog algoritma može biti zamenjen nizom brojeva od 1 do m (broj grana u grafu), gde član niza i sadrži čvorove čije rastojanje je težina grane na poziciji i u sortiranom redosledu. Ova metoda dozvoljava da se problem najšireg puta reši brzo koliko i [[algoritmi sortiranja|sortiranje]]; na primer, ako je težina grane predstavljena kao ceo broj, onda bi se vreme koje je potrebno za sortiranje liste od m celih brojeva moglo primeniti na ovaj problem.
 
=== Jedan izvor i jedno odredište ===
 
{{harvtxtharvnb|Berman|Handler|1987}} predlažu da bi servis vozila i vozila hitne pomoći trebalo da koriste minimax puteve kada se vraćaju u svoju bazu nakon poziva servisa. U ovoj primeni , vreme povratka nije toliko važno, za razliku od vremena reagovanja na mogući poziv servisa dok je vozilo servisa u povratku. Koristeći minimax putanju, gde je težina grane maksimalno vreme putovanja od jedne tačke grane do najudaljenijeg mogućeg poziva servisa, može se isplanirati ruta koja minimizuje maksimalno moguće vreme čekanja od trenutka kada servis primi poziv do trenutka kada vozilo servisa dođe na pozvano mesto. {{harvtxtharvnb|Ullah|Lee|Hassoun|2009}} koriste maksimalne putanje kako bi napravili dominantnu lančanu reakciju u metaboličkim mrežama; u njihovom modelu, težina grane je slobodna energija metaboličke reakcije koja je predstavljena granom.
 
Još jedna primena najširih putanja se javlja u [[Ford–Fulkerson algorithm|Ford-Fulkersonovom algoritmu]] za problem maksimalnog protoka. Više puta povećavajući protok duž maksimalnog kapaciteta puta u mreži protoka dovodi do male granice, {{math|''O''(''m'' log ''U'')}}, brojeva povećanja koji su potrebni da bi se našao maksimalni protok; ovde, grane kapaciteta su podrazumevano celi brojevi, koji su u većini slučajeva U. Ipak, ova analiza nije pozdana za nalaženje puta koji ima maksimalni kapacitet; bilo koji put čiji kapacitet ima konstantan faktor maksimuma je dovoljan. Kombinujući ovu približnu ideju sa metodom povećanja najkraćeg puta [[Edmonds–Karp algorithm|Edmonds-Karpovog algoritma]], dovodi do algoritma maksimalnog protoka koji je složenosti {{math|''O''(''mn'' log ''U'')}}.<ref name="amo">{{citation | first1=Ravindra K. |last1=Ahuja| author1-link = Ravindra K. Ahuja | first2 = Thomas L. |last2=Magnanti| author2-link = Thomas L. Magnanti | first3 = James B. |last3=Orlin| author3-link = James B. Orlin | title= Network Flows: Theory, Algorithms and Applications | publisher=Prentice Hall |year=1993|id=ISBN 0-13-617549-X|contribution=7.3 Capacity Scaling Algorithm|pages=210–212}}</ref>
 
Moguće je vrlo efikasno naći putanje maksimalnog kapaciteta i minimax putanje sa pojedinačnim izvorom i pojedinačnim odredištem čak i u modelima računanja kod kojih ne smemo da vršimo bilo kakvu matematičku operaciju, možemo samo da upoređujemo grane ulaznog grafa. Algoritam sadrži set od {{math|''S''}} grana za koje se zna da predstavljaju usko grlo optimalnog puta; inicijalno, {{math|''S''}} je samo set svih {{math|''m''}} grana grafa. U svakoj iteraciji algoritma, {{math|''S''}} se deli na određene podsetove {{math|''S''<sub>1</sub>, ''S''<sub>2</sub>, ...}} koje su približno istih veličina; broj podsetova u ovoj podeli nije slučajan, izabran je tako da se sve razdvojene tačke između podsetova mogu naći ponavljanjem srednjeg-traženja za vreme {{math|''O''(''m'')}}. Algoritam zatim ponovo postavlja težinu svakoj grani grafa u zavisnosti od indeksa podseta kojoj grana pripada, i zatim se na tako izmenjenom grafu primeni izmenjeni Dijkstrin algoritam; i u zavisnosti od rezultata računanja, algoritam može za linearno vreme da odredi koji od podseta sadrži granu koja ima težinu uskog grla. Nakon toga se {{math|''S''}} zameni podsetom {{math|''S''<sub>''i''</sub>}}, za koji se prethodno ustanovilo da sadrži granu uskog grla, i počinje sledeću iteraciju sa sada novim setom {{math|''S''}}. Broj podsetova na kojih se {{math|''S''}} može podeliti se eksponencijalno povećava svakim korakom, pa je broj iteracija proporcionalan logaritamskoj funkciji, {{math|''O''(''log*n'')}}, dok je vremenska složenost ovog algoritma {{math|''O''(''mlog*n'')}}.<ref>{{citation
|last1=Han| first1 = Yijie
|last2=Thorup| first2 = M. | author2-link = Mikkel Thorup
| contribution = Integer sorting in {{math|O(''n''{{sqrt|log log ''n''}})}} expected time and linear space
| doi = 10.1109/SFCS.2002.1181890
|pages=135–144
| title = [[Symposium on Foundations of Computer Science|Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002)]]
|year=2002}}</ref>
 
== Euklidov set tačaka ==
 
Varijanta problema minimax putanje se takođe uzela u obzir za set tačaka u [[Euklidova geometrija|Euklidovoj geometriji]]. Za razliku od neusmerenih grafova, ovaj problem može da se reši vrlo efikasno tako što se nađe Euklidovo minimalno razapinjajuće stablo. Ipak, postaje komplikovanije kada je put takav da ne minimizuje samo kratka rastojanja nego, među putanjama koje imaju ista kratka rastojanja, minimizuje ili približno minimizuje ukupnu dužinu puta. Približno rešenje se može dobiti korišćenjem tzv. geometrijskih izvijača.<ref>{{citation
|last1=Bose| first1 = Prosenjit
|last2=Maheshwari| first2 = Anil
|last3=Narasimhan| first3 = Giri
|last4=Smid| first4 = Michiel
|last5=Zeh| first5 = Norbert
| doi = 10.1016/j.comgeo.2004.04.003
| mr = 2095376
| issue = 3
| journal = Computational Geometry. Theory and Applications
|pages=233–249
| title = Approximating geometric bottleneck shortest paths
| volume = 29
|year=2004}}</ref>
 
 
Преузето из „https://sr.wikipedia.org/wiki/Problem_najšireg_puta”