Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м ispravke
м Разне исправке
Ред 1:
[[Датотека:TezinskiGraf.jpg|thumbмини|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]]a u težinskom usmerenom grafu, povećavajući težinu minimalno-težinskih grana puta.
Ред 30:
| 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)
Ред 41:
| 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|last=Vassilevska|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 ===
Ред 56:
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 ==
Ред 77:
| 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”