Verze z 11. 6. 2008, 23:57 editovat Petr Kopač (diskuse \| příspěvky) Prověření uživatelé 7 587 editací úvod a obrázek z enwiki, algoritmus napsán "z hlavy" => _bude to chtít zkontrolovat/upravit_		Verze z 18. 6. 2008, 22:05 editovat zrušit editaci Petr Kopač (diskuse \| příspěvky) Prověření uživatelé 7 587 editací + obrázek a oprava algoritmu Přejít na další porovnání →
Řádek 1: [[Soubor:Pert_chart_colored.gif\|thumb\|309px\|[[Program Evaluation and Review Technique\|PERT]] síťový diagram pro projekt s pěti milníky (10 až 50) a šesti činnostmi (A až F). Projekt má dvě kritické cesty: B-C nebo A-D-F, minimální doba trvání tohoto projektu je tedy 7 měsíců (s použitím fast-trackingu). Činnost E je podkritická, tzn. může se zpozdit až o 2 měsíce, aniž by zpozdila projekt.]] Metoda '''kritické cesty''' ({{Vjazyce\|en}} {{cizojazyčně\|en\|'''Critical Path Method'''}}, zkráceno '''CPM''') je matematický [[algoritmus]] plánování průběhu množiny činností projektu. Je to jeden z důležitých nástrojů [[řízení projektů]]. Řádek 7 ⟶ 6: == Algoritmus nalezení kritické cesty == <!-- bylo by nejlepší udělat animák, kdo ho udělá? :) --> [[Soubor:Critical path algorithm.svg\|Příklad grafu - červeně je vyznačena kritická cesta ABDGH.\|thumb\|right\|300px]] Sestrojíme [[orientovaný graf\|orientovaný]], [[ohodnocený graf\|ohodnocený]] graf reprezentující projekt. Každá hrana v něm má svoji váhu a každý vrchol své označení + dvě prázdné proměnné (levá a pravá) pro zápis hodnot [[cesta (grafy)\|cest]]. Hrany, které budou ležet na cestách si budeme označovat. Graf může obsahovat i více než jednu kritickou cestu. Nejprve projdeme graf zleva ze vstupního vrcholu (hodnota jeho levé proměnné je na začátku 0). Do levé proměnné tohoto vrcholu pak zapíšeme hodnotu cesty (hodnota cesty z předchozího vrcholu + hodnota hrany). Hranu vybíráme tak, že při vstupu do nějakého vrcholu budeme vybírat vždy hranu, ze které dostaneme nejvyšší hodnotu cesty (např. do vrcholu D půjdeme po hraně z B, protože cesta má hodnotu 7, což je vyšší než z C, kde má cesta hodnotu 4). Nejprve projdeme graf ze vstupního vrcholu (hodnota jeho levé proměnné je na začátku 0) a skončíme ve výstupním vrcholu, hodnoty cest zapíšeme do levé proměnné. Cestu vybíráme tak, že při vstupu do nějakého vrcholu budeme vybírat vždy hranu s nejvyšší možnou hodnotou. Do levé proměnné tohoto vrcholu pak zapíšeme hodnotu cesty (hodnota cesty z předchozího vrcholu + hodnota hrany). Tímto postupem vyplníme levé proměnné všech vrcholů a dojdeme až do výstupního (koncového) vrcholu grafu. V jeho levé proměnné nyní máme minimální délku projektu. Druhý průchod grafu začínáme v koncovém vrcholu, opíšeme hodnotu z jeho levé proměnné do pravé a jdeme proti směru orientovaných hran (vpravo). Nyní však vybíráme ~~hranu~~cestu s nejmenší možnou hodnotou a její hodnotu hran odečítáme ~~od původní hodnoty~~, výsledek zapíšeme do pravé proměnné vrcholu (např. do D půjdeme přes G, protože dostaneme hodnotu 7, což je menší, než kdybychom tam šli přímo z H). Když dojdeme do počátečního bodu, měli bychom v něm mít vpravo 0. Vrcholy se stejnými hodnotami vlevo a vpravo leží na kritické cestě~~. Pokud jsme si značili hrany, kterými jsme do bodů došli, máme i kritické cesty (nemusí být pouze jedna)~~. == Odkazy ==

Metoda kritické cesty: Porovnání verzí