Topološko uređenje — разлика између измена
Садржај обрисан Садржај додат
м knjige+sfn; козметичке измене |
м Разне исправке |
||
Ред 1:
{{Spajanje|
U [http://en.wikipedia.org/wiki/Computer_science informatici], '''topološko sortiranje'''(skraćeno '''topsort''' ili '''toposort''') ili '''topološko uređenje''' [http://en.wikipedia.org/wiki/Directed_graph usmerenog grafa] je linearno uređenje njegovih [http://en.wikipedia.org/wiki/Vertex_(graph_theory) čvorova] tako da svaka usmerena grana ''UV'' od čvora ''U'' ka čvoru ''V, U'' dolazi pre ''V'' u uređenju.Na primer, čvorovi grafa predstavljaju zadatke koje treba izvršiti , a grane predstavljaju ograničenja da neki zadataka mora biti izvršen pre nekog drugog; u ovoj aplikaciji, topološko uređenje je samo validan raspored izvršavanja zadataka.Topološko uređenje je moguće ako i samo ako graf nema [http://en.wikipedia.org/wiki/Directed_cycle usmerene cikluse], odnosno da je [http://en.wikipedia.org/wiki/Directed_acyclic_graph usmereni acikličan graf](UAG).Svaki UAG ima najmanje jedno topološko uređenje , i poznat je [http://en.wikipedia.org/wiki/Algorithm algoritam] za konstruisanje topološkog uređenja bilo kog UAG u [http://en.wikipedia.org/wiki/Linear_time#Linear_time linearnom vremenu].
== Primeri ==
Kanonska aplikacija topološkog sortiranja(topološkog uređenja) je u [http://en.wikipedia.org/wiki/Job_shop_scheduling planiranju] rasporeda poslova ili zadata na osnovu njihove zavisnosti; algoritmi topološkog sortiranja su prvi put proučavani ranih 1960-ih godina u kontekstu [http://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique PERT] tehnike planiranja [http://en.wikipedia.org/wiki/Project_management upravljanja projektima] ({{harv|Jarnagin|1960}}).Poslovi su predstavljeni čvorovima i postoji grana od ''A'' ka ''B'' ako posao ''A'' mora biti izvršen pre nego što se posao ''B'' može zapoceti(primer: kod pranja veš mašine, mašina mora da završi sa pranjem veša da bi ga mi satvili na sušenje).Dakle, topološko sortiranje nam daje redosled kojim treba da izvršavamo poslove.
U informatici, aplikacije ovog tipa prerastaju u [http://en.wikipedia.org/wiki/Instruction_scheduling instrukcije organizacije], uređenju formula ćelija evaluacije pri reizračunavanju formula valuacije u [http://en.wikipedia.org/wiki/Spreadsheet tabelama], [http://en.wikipedia.org/wiki/Logic_synthesis logičke sinteze], određivanje rasporeda zadataka kompilacije koji se izvršavaju u [http://en.wikipedia.org/wiki/Makefile mejkfajlovima], [http://en.wikipedia.org/wiki/Serialization serijalizaciji] podataka i određivanju zavisnosti simbola u [http://en.wikipedia.org/wiki/Linker_(computing) linkerima].
{|
|[[Датотека:Directed acyclic graph.png|
| The graph shown to the left has many valid topological sorts, including:
* 7, 5, 3, 11, 8, 2, 9, 10 (vuzuelno sa leva na desno,
* 3, 5, 7, 8, 11, 2, 9, 10 (prvo čvorovi sa najmanjom vrednošću)
* 3, 7, 8, 5, 11, 10,
* 5, 7, 3, 8, 11, 10, 9, 2 (najkrace grane prvo)
* 7, 5, 11, 3, 10, 8, 9, 2 (prvo čvorovi sa največom vrednošću)
* 7, 5, 11, 2, 3, 8, 9, 10
|}
==
Uobičajeni algoritmi sa topološkim sortiranjem imaju linearnu složenost po broju grana plus broju čvorova (<math>O(\left|{V}\right| + \left|{E}\right|)</math>).
Jedan od ovih algoritama, koji je opisao {{harvtxt|Kahn|1962}}, radi tako što odabira čvorove u istom redosledu kao i eventualno topološko sortiranje.Prvo nade listu "početnih čvorova" koji nemaju ulazne grane i ubacuje ih u S;barem jedan takav čvor mora postojati u acikličnom grafu.Zatim:
L ← Prazna lista koja će sadržati sortirane elemente
S ← Skup svih čvorova bez ulaznih grana
'''while''' S is non-empty '''do'''
remove a node n from S
insert n into L
'''for each''' node m with an edge ''e'' from n to m '''do'''
remove edge e from the graph
'''if''' m has no other incoming edges '''then'''
insert m into S
'''if''' graph has edges '''then'''
return error (Graf ima bar jedan ciklus)
'''else'''
return L (Topološki sortirani)
Ako je graf UAG, rešenje ce se nalaziti u listi L(rešenja ne moraju biti jedinstvena).U suprotnom, graf ima bar jedan ciklus i topološko sortiranje se ne može uraditi.
Napomenimo da, zbog ne-jedinstvenosti rezultata sortiranja, struktura S može biti jednostavno skup, red ili stek.U zavisnosti od redosleda kojim se čvorovi ''n'' izbacuju iz skupa S, dobijamo različita rešenja.Varijacije Kahn-ovog algoritma koji razbije veze [http://en.wikipedia.org/wiki/Lexicographic_order leksikografskih] oblika, ključna je komponenta [http://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm Caffman-Graham-ovog] algoritma za paralelno planiranje i [http://en.wikipedia.org/wiki/Layered_graph_drawing slojevito crtanje grafa].
Alternativni algoritam za topološko sortiranje je zasnovan na [http://en.wikipedia.org/wiki/Depth-first_search pretraživanju u dubinu].Kod ovog algoritma, grane su usmerene u suprotnom smeru od prethnog algoritma(a u suprotnom smeru nego sto su prikazane na dijagramu uznad).Postoji grana od ''A'' ka ''B'' ako posao ''A'' zavisi od posla ''B''(ako posao ''B'' mora biri izvršen pre nego sto posao ''A'' može da se započne).Algoritam se kreće kroz svaki čvor grafa, u proizvoljnom redosledu, započinjući pretragu u dubinu koja se zaustavlja kada se dođe do čvora koji je već posećen.
L ← Prazna lista koja će sadržati sortirane čvorove
'''while''' there are unmarked nodes '''do'''
select an unmarked node n
visit(n)
'''function''' visit(čvor n)
'''if''' n has a temporary mark '''then''' stop (nije UAG)
'''if''' n is not marked (nije posećen) '''then'''
mark n temporarily
'''for each''' node m with an edge from n to m '''do'''
visit(m)
mark n permanently
add n to head of L
Primetimo da se svaki čvor ''n'' dodaje u izlaznu listu L tek nakon što se razmotre svi čvorovi od kojih ''n'' zavisi(svi potomci čvora ''n'' u grafu).Posebno, kada algoritam doda čvor ''n'', zagarantovano je da su svi čvorovi od kojih zavisi ''n'' već dodati u izlaznu listu L:dadati su u L ili prethodnim rekurzivnim pozivom visit() ili ranijim pozicom visit().Kako su svi čvorovi i svaka grana posećeni jednom, algoritam se izvršava u lineatnom vremenu.Ovaj algoritam, zasnovan je na pretrazi u širinu, opisao ga je {{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}} ali ga je pre njega opisao {{harvtxt|Tarjan|1976}} u stampi.
== Složenost ==
* [http://en.wikipedia.org/wiki/Computational_complexity Računarska kompleksnost] izračunavanja topološkog uređenja u usmerenom grafu je [http://en.wikipedia.org/wiki/NC_(complexity) '''NC''']<sup>2</sup>; što znači da se može izračunati za ''O''(log<sup>2</sup> ''n'') vremena na [http://en.wikipedia.org/wiki/Parallel_computer paralelnom računaru] pomoću polinomijalnog broja od ''O''(''n<sup>k</sup>'')procesora, za istu konstantu ''k''{{harv|Cook|1985}}.
== Jedinstvenost ==
Kada bi topološko sortiranje imalo osobinu da sve parove uzastopnih čvorova u sortiranom poretku poveže granama, dobili bismo usmeren [http://en.wikipedia.org/wiki/Hamiltonian_path Hamiltonov put] u [http://en.wikipedia.org/wiki/Directed_acyclic_graph UAG].Ako Hamiltonov put postoji, topološki poredak je jedinstven;nijedan drugi poredak ne zadovoljava ivice puta.Obrnuto, ako topološko sortiranje ne formira Hamiltonov put, UAG će imati dva ili više validna topološka poretka, jer je u ovom slučaju uvek moguće formirati drugi ispravan poredak zamenom dva uzastopna čvora koji nisu povezani granom.Dakle, moguće je proveriti u linearnom vremenu da li postoji jedinstveni poredak, i da li postoji Hamiltonov put, uprkos [http://en.wikipedia.org/wiki/NP-hard NP-težini] problema Hamiltonovog puta za neke opštije usmerene grafove{{harv|Vernet|Markenzon|1997}}.
== Odnos prema relaciji poretka ==
Topološka sortiranja su usko povezana sa konceptom [http://en.wikipedia.org/wiki/Linear_extension lineanog istezanja] [http://en.wikipedia.org/wiki/Partial_order#Formal_definition relacije poretka] u matematici.
Parcijalno uredjen skup je skup objekata sa definicijom relacije manje ili jednako "≤", zadovoljavajući aksiome refleksivnosti(''x'' ≤ ''x''), antisimetričnosti(ako je ''x'' ≤ ''y'' i ''y'' ≤''x'' onda je ''x'' = ''y''), i [http://en.wikipedia.org/wiki/Transitive_relation tranzitivnosti] (ako je ''x'' ≤ ''y'' i ''y'' ≤ ''z'', onda je ''x'' ≤ ''z'').[http://en.wikipedia.org/wiki/Total_order Relacija totalnog poretka] je relacija poretka u kojoj su svaka dva objekta ''x'' i ''y'' iz skupa uporedivi, ili je ''x'' ≤ ''y'' ili je ''y'' ≤ ''x''.Totalna uređenja se koriste u informatici kako bi operatori poređenja mogli da izedu upoređivanje kod [http://en.wikipedia.org/wiki/Comparison_sort algoritama za sortiranje].Za konačne skupove, totalna uređenja se mogu identifikovati kao linearan niz objekata gde je "≤" relacija tačna kad god prvi objekat prethodi drugom u redu;algoritmi za sortiranje upoređivanjem se mogu iskoristiti za pretvaranje totalnog uređenja u niz na ovaj način. Linearno istezanje relacije poretka je totalni poredak koji je usaglašen sa njim, u smislu ako je ''x'' ≤ ''y'' u relaciji poretka onda je i ''x'' ≤ ''y'' u totalnom poretku takođe.
Može se definisati relacija poretka iz bilo kog DAL-a tako što ćemo postaviti da skup objekata budu čvorovi DAL-a i definišemo da je ''x'' ≤ ''y'' tačno za bilo koja dva čvora ''x'' i ''y', kad god postoji [http://en.wikipedia.org/wiki/Directed_path usmeren put] od ''x'' ka ''y'',tj. kad god iz ''x'' [http://en.wikipedia.org/wiki/Reachability možemo da stignemo do] ''y''. Ovako definisano, topološko uređenje DAL-a je isto što i linearno istezanje ove relacije poretka.Obrnuto, svaka relacija poretka može biti definisana kao relacija domašaja u DAL-u.Jedan način da se ovo izvede je da se definiše DAL koje ima čvor za svaki objekat iz skupa relacije poretka i granu ''xy'' za svaki par objekata za koje važi ''x'' ≤ ''y''.Alternativan način da se uradi ovo je da se koristi [http://sr.wikipedia.org/wiki/Tranzitivni_zavr%C5%A1eci tranzitivno zatvorenje] relacije poretka;u celini, ovako dobijamo DAL-ove sa manje grana ali je relacija domašaja i dalje
ista relacija poretka.Ovako se algoritmi za topološko sortiranje mogu koristiti za nalaženje linearnih istezanja relacije poretka.
== Pogledati takođe ==
* [http://en.wikipedia.org/wiki/Tsort_(Unix) tsort], a Unix program for topological sorting
* [http://sourceforge.net/projects/dep-trace/ dep-trace] Orders basic dependencies and unfolds nested ones. (basic: without 2D graphical presumption)
* [http://en.wikipedia.org/wiki/Feedback_arc_set Feedback arc set], a (possibly empty) set of arcs which, if removed from the graph, make it possible to topologically sort it. Useful for dealing with graphs with cycles.
* [http://en.wikipedia.org/wiki/D._E._Knuth D. E. Knuth], [http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming], Volume 1, section 2.2.3, which gives an algorithm for topological sorting of a partial ordering, and a brief history.
* [http://en.wikipedia.org/wiki/Dependency_graph Dependency graph]
== Reference ==
== Литература ==
* {{Cite book | last = Cook | first = Stephen A. | authorlink = Stephen Cook| title = A Taxonomy of Problems with Fast Parallel Algorithms | journal = Information and Control | volume = 64 | issue = 1–3| year = 1985 | pages = 2–22
| doi = 10.1016/S0019-9958(85)80041-3}}.
* {{Cite book | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen| last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson | last3 = Rivest | first3 = Ronald L. | author3-link = Ronald L. Rivest| last4 = Stein | first4 = Clifford | author4-link = Clifford Stein | contribution = Section 22.4: Topological sort| edition = 2nd | isbn = 0-262-03293-7| pages = 549–552 | publisher = MIT Press and McGraw-Hill| title = [[Introduction to Algorithms]]
| year = 2001}}.
* {{Cite book | last = Jarnagin | first = M. P.| title = Automatic machine methods of testing PERT networks for consistency | year = 1960| series = Technical Memorandum No. K-24/60 | publisher = U. S. Naval Weapons Laboratory| location = Dahlgren, Virginia}}.
* {{Cite book | last = Kahn | first = Arthur B.| title = Topological sorting of large networks | journal = Communications of the ACM| volume = 5 | issue = 11 | year = 1962 | pages = 558–562
| doi = 10.1145/368996.369025}}.
* {{Cite book | last = Tarjan | first = Robert E. | authorlink = Robert Tarjan| title = Edge-disjoint spanning trees and depth-first search | journal = Acta Informatica | volume = 6 | issue = 2 | year = 1976 | pages = 171–185| doi = 10.1007/BF00268499}}.
* {{Cite book | last1 = Vernet | first1 = Oswaldo| last2 = Markenzon | first2 = Lilian | contribution = Hamiltonian problems for reducible flowgraphs| title = Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97) | year = 1997| pages = 264–267
| doi = 10.1109/SCCC.1997.637099}}.
== Spoljašnje veze ==
* [http://www.nist.gov/dads/HTML/topologicalSort.html -{NIST Dictionary of Algorithms and Data Structures: topological sort}-]
{{DEFAULTSORT:Тополошко уређење}}
[[Категорија:Графовски алгоритми]]
[[Категорија:Алгоритми сортирања]]
[[Категорија:Теорија графова]]
| |||