Problem najšireg puta — разлика између измена
Садржај обрисан Садржај додат
Поправљене везе: čvor → Čvor (informatika) користећи Dab solver |
м Разне исправке; козметичке измене |
||
Ред 2:
[[Датотека:TezinskiGraf.jpg|мини|U ovom grafu, najširi put od cvora D do cvora F je opsega 29, i prolazi kroz čvorove C, E, B i G]]
U [[algoritmima za rad sa grafovima]] , '''problem najšireg puta''', takođe poznat kao '''problem usko grlo najkraćeg puta''' ili '''problem maksimalnog kapaciteta puta''', je problem nalaženja puta između dva određena [[Čvor (informatika)|
Na primer, ako graf predstavlja veze između [[ruter]]a na [[Интернет|Internetu]], i težina grane predstavlja protok konekcije između dva rutera, problem najšireg puta je problem nalaženja puta između dva Internet čvora koja imaju maksimalni mogući protok. Težina grane minimalne težine je poznata kao kapacitet protoka puta. Pored primene u mreži rutera, problem najšireg puta je vrlo važna komponenta [[Šulcova metoda|Šulcove metode]] (sistem za glasanje), prilikom odlučivanja pobednika izbora. Takođe problem se primenjuje u tzv. digitalnom sastavljanju (proces digitalne montaže više slika u jednu završnu sliku) , u metaboličkoj analizi, i u računanju maksimalnog toka. Moguće je prilagoditi algoritme najkraćeg puta kako bi se izračunao najširi put, menjajući ih tako da koriste udaljenost uskog grla umesto dužine puta. Dobro je znati da, u mnogim slučajevima čak i brži algoritmi su mogući.
Ред 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
|
|
| contribution = Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths
|pages=384–391
Ред 35:
| 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
|
|
|
| contribution = All-pairs bottleneck paths for general graphs in truly sub-cubic time
| doi = 10.1145/1250790.1250876
Ред 55:
{{harvtxt|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. {{harvtxt|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. |
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
|
|
| 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}}
== 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
|
|
|
|
|
| doi = 10.1016/j.comgeo.2004.04.003
| mr = 2095376
| |||