abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 15:22 | Komunita

Daniel Vetter ve zprávě rozeslané do vícero e-mailových konferencí shrnuje situaci kolem financování služeb poskytovaných projektům Freedesktop.org, zvláště spojeným s X.Org (grafické knihovny atp.). Vzhledem k rostoucí popularitě služeb jako CI (Continuous Integration) rostou také náklady na hosting (očekávané výdaje od 75 tisíc dolarů za rok), a proto se hledá sponzor, nebo bude nutné služby v horizontu několika měsíců omezit.

Fluttershy, yay! | Komentářů: 3
dnes 14:55 | Zajímavý článek

Knot DNS slaví deset let své existence. Projekt autoritativního DNS serveru Knot DNS patří mezi nejstarší projekty Laboratoří CZ.NIC. Dnes je tomu právě deset let od uložení prvotního prototypu serveru commitem 2da03d5da do veřejného repozitáře Git.

Ladislav Hagara | Komentářů: 0
dnes 14:11 | Nová verze

Byla vydána nová verze 2.53.1 svobodného multiplatformního balíku internetových aplikací SeaMonkey (Wikipedie). Přehled novinek v poznámkách k vydání. Hlavní změny jsou pod kapotou. Nová hlavní verze 2.53 používá základ z Firefoxu a Thunderbirdu 60.

Ladislav Hagara | Komentářů: 0
dnes 07:00 | Zajímavý software

Budou to tři roky, co Canonical ukončil vývoj mj. grafického prostředí Unity8 a souvisejících projektů jako smartphone s Ubuntu Touch. Toho se ujala komunita UBports a vedle toho vznikl fork Yunit, který již neexistuje, zatímco Unity8 se dostane do Debianu. Nebude se však jmenovat Unity8, nýbrž Lomiri, jak bylo nyní oznámeno.

Fluttershy, yay! | Komentářů: 0
dnes 06:00 | Zajímavý projekt

Úrad podpredsedu vlády SR pre investície a informatizáciu vyhlásil výzvu na podporu migrácie na open source a podporu budovania inteligentných miest a regiónov. Dátum uzavretia 1. hodnotiaceho kola je 21.04.2020. Žiadatelia môžu získať od 200 000 do 1 000 000 eur.

atirage21 | Komentářů: 0
dnes 05:00 | IT novinky

Otevřená certifikační autorita Let's Encrypt oznámila, že vydala již miliardu certifikátů. Při spuštění veřejné bety Let's Encrypt, v prosinci 2015, bylo celosvětově pomocí HTTPS stahováno cca 40 % webových stránek. Dnes je to 81 %. V USA dokonce 91 %. Podrobnosti na stránce se statistikami. Let's Encrypt má aktuálně 13 zaměstnanců na plný úvazek a roční rozpočet přibližně 3,35 milionu dolarů.

Ladislav Hagara | Komentářů: 8
včera 15:33 | Komunita

Fedora stále hledá nové logo. První návrhy byly představeny již před rokem. Designérka Fedory Máirín Duffy ukázala na Twitteru aktuální verzi a žádá uživatele o zpětnou vazbu.

Ladislav Hagara | Komentářů: 20
včera 13:55 | Nová verze

Android-x86, tj. port mobilního operačního systému Android na standardní PC s architekturou x86, byl vydán v nové stabilní verze 9.0-r1. Přehled novinek v oficiálním oznámení.

Ladislav Hagara | Komentářů: 16
včera 13:11 | Komunita

Mozilla definitivně opouští IRC. Vloni začala hledat novou veřejnou komunikační platformu. Dosud používala IRC (plus interně neveřejný Slack a po nějakou dobu i Mattermost). Nicméně IRC i servery zastarávaly a zejména použitelnost na mobilních zařízeních byla často problematická. Po zvažování a zkoušení různých alternativ se Mozilla přiklonila k otevřenému protokolu Matrix (můžete také znát referenčního klienta Riot) a na konci února IRC vypne.

Ladislav Hagara | Komentářů: 28
včera 13:00 | IT novinky

Raspberry Pi slaví 8 let. Při této příležitosti bylo Raspberry Pi 4 s 2 GB RAM zlevněno o 10 dolarů. Napořád.

Ladislav Hagara | Komentářů: 2
Vydržela vám novoroční předsevzetí?
 (11%)
 (6%)
 (3%)
 (81%)
Celkem 211 hlasů
 Komentářů: 0
Rozcestník

Noční můra Edsgera Dijkstry?

29.5.2006 02:20 | Přečteno: 3145× | ostatní | poslední úprava: 10.11.2006 13:07

S Dijkstrovým algoritmem pro vyhledávání nejkratší cesty v ohodnoceném grafu se již setkal asi každý, kdo se v programování dostal alespoň o trochu dále, než k obligátnímu "Hello World!".

Notoricky známý o tomto algoritmu je pak fakt, že jeho asymptotická složitost při použití prioritní fronty implementované jako binární halda je O(|H|log|U|). Již méně známé, i když z algoritmu jasně vyplývající, je ale to, že tato prioritní fronta musí kromě obvyklých operací push() a pop() umožňovat i změnu priority prvků uvnitř fronty (a následné obnovení fronty). A to se v okamžiku, kdy narazí kosa na kámen a vy jste nuceni algoritmus implementovat v nějakém programovacím jazyku, ukazuje jako poměrně problematická záležitost. Minimálně pokuď je zvoleným jazykem C++. Prioritní fronta ze standartní šablonové knihovny STL totiž touto vlastností neoplývá...

Pokuď vám nejde o každou instrukci a můžete si dovolit určité (a právě velikost tohoto "určité" je oč tu dneska běží) zhoršení časové složitosti, lze nicméně tento problém obejít a Dijkstrův algoritmus upravit následovně:

Vertex *start, *current, *neighbour;
Edge *e;


start->setDistance(0);
queue.push(start);

while (!queue.empty()) {
    current = queue.top();
    queue.pop();

    if (!current->getVisited()) {
        current->setVisited(true);

        e = current->getFirstEdge();
        while (e != NULL) {
            neighbour = e->getEnd();

            if ((neighbour->getDistance() == -1) // -1 = nekonečno
               || (neighbour->getDistance() > current->getDistance() + e->getLength())) {
                neighbour->setDistance(current->getDistance() + e->getLength());
                neighbour->setPrev(current);
            }
            queue.push(neighbour);

            e = e->getNext();
        }
    }
}

(Graf je implementován pomocí seznamu následníků)

Úprava spočívá v přidání atributu visited (bool) ke každému uzlu. Tento atribut slouží k určení, zda už byl uzel objeven či nikoliv a umožňuje rozhodnout, zda se s daným uzlem na vrcholu fronty zabývat či nikoliv. Druhou změnou totiž je, že pokud některý ze sousedů právě zpracovávaného uzlu zkracuje cestu do aktuálního uzlu, není u něj pouze upravena vzdálenost, ale je znovu zařazen do fronty (na místo odpovídající upravené vzdálenosti). Při odebírání uzlu z fronty je pak "platný" pouze první výskyt daného uzlu, ostatní je možné(nutné) ignorovat.

Uvedená modifikace zůstává (alespoň doufám ;-) korektní co se týče nalezených nejkratších cest, otázkou ale je, jak tyto úpravy změní časovou složitost algoritmu. Zcela jistě se zvýší režie zařazování uzlů do fronty, ale změní se i složitost asymptotická? Může fronta asymptoticky přerůst |U|? Jak se toto zhoršení projeví na běžných grafech typu "silniční síť"? Bude toto zhoršení tak výrazné, že celý algoritmus "znehodnotí"? To jsou otázky, které čekají na opravdové programátory ve vašich řadách. Já si své teorie a odhady pojídače koláčků zatím nechám pro sebe (podělím se o ně s vámi radši až v diskuzi ke "článku" ;-).

       

Hodnocení: 90 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

29.5.2006 06:34 mivrap | blog: Mirkovo
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
a co je to za slovo, to "pokuď" ?
Martin Tůma avatar 29.5.2006 09:07 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

Ty asi nebudeš Pražák, co?! ;-)

Každý má právo na můj názor!
29.5.2006 07:27 lukipuki | skóre: 4 | blog: | Štokholm
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Tvoj algoritmus má zložitosť O(|H| log |U^2|), čo je O(H log |U|). Totiž log(x^2)=2log(x).

Tvoje riešenie je korektné. Mimochodom, vlastnosť visited musíš mať implementovanú aj v pôvodnej verzii algoritmu.
/dev/null: Permission denied
Martin Tůma avatar 29.5.2006 09:07 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Mimochodom, vlastnosť visited musíš mať implementovanú aj v pôvodnej verzii algoritmu.

Nemusím. Ne-mu-sím! ;-) Standartně jsou všechny vrcholy zařazeny do fronty při inicializaci algoritmu a jejich náležení/nenáležení frontě již samo o sobě udává, zda-li byl vrchol již "objeven" či nikoliv.

Každý má právo na můj názor!
29.5.2006 08:27 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
1) Dijkstrův algoritmus lze aplikovat na grafy s nezáporným ohodnocením hran, což je dost důležité zmínit.

2) Časová složitost v případě použití binární haldy je obecně O(|V+E|lg|V|), což je O(|E|lg|V|), když jsou všechny vrcholy dosažitelné z výchozího vrcholu.

3) Ve skutečnosti můžeme dosáhnout složitosti O(|V|lg|V|+|E|) použitím Fibonacciho haldy (lepší amortizovaná složitost). Ale tohle nám asi neříkali ani na matfyzu;-).
Math, as Barbie says, is hard.
Martin Tůma avatar 29.5.2006 09:12 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

Tohle jsou samozřejmě další dobře známé vlastnosti Dijkstrova algoritmu (dokonce i ta možnost využití Fibonacciho haldy se udává snad v každém popisu algoritmu), některé vlastnosti jsem dokonce zmínil v textu, ale oč tu běží je čistě implementační záležitost a vlastnosti "přiohnutého" algoritmu.

Každý má právo na můj názor!
29.5.2006 09:19 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Zajímavé. V textu tvrdíš, že se moc neví, že při "implementaci" s použitím binární haldy je potřeba měnit prioritu uvnitř haldy. Mohl bys tedy ukázat pseudokód (rozuměj popis algoritmu), který by bez této "funkce" fungoval? A pokud ne, jak je možné, že se o tom "moc neví":-)?
Math, as Barbie says, is hard.
Martin Tůma avatar 29.5.2006 09:35 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Mohl bys tedy ukázat pseudokód (rozuměj popis algoritmu), který by bez této "funkce" fungoval?

Uááá. Agoritmus, který tuto funkci nepotřebuje je právě ten ukázkový kód. O něm to celý je!

A pokud ne, jak je možné, že se o tom "moc neví"?

To že se o nutnosti této funkce použité fronty "moc neví" je myšleno tak, že si to člověk naplno uvědomí, až když musí algoritmus implementovat, protože takovou frontu obyčejně nemá k dispozici. Rozhodně to ale neni nějaký zajímavý a málo probádaný teoretický aspekt Dijkstrova algoritmu jako takového.

Každý má právo na můj názor!
29.5.2006 09:47 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
No vidíš;-). Já to nedočetl, protože nechápu, proč bych měl algoritmus zpomalit kvůli tomu, že knihovna neobsahuje triviální funkci nad binární haldou. Klíčové slovo je to _nechápu_:-). Tak se nezlob...
Math, as Barbie says, is hard.
29.5.2006 13:10 Honza Král | skóre: 3 | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Ale tohle nám asi neříkali ani na matfyzu;-).
Predmet slozitost, fibbonaciho haldy i jejich aplikace v Dijstrove algoritmu se probiraly... ;)
29.5.2006 16:16 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Ještě pořád je to povinné? Karolinky hledat nebudu;-)... Co mě na matfyzu vždycky pobaví je předmět, který probere látku vcelku povrchně, ale nakousne toho co nejvíc. Za pár semestrů ho totiž v rámci takřka stejného sylabu rozšíří další. Viz třeba ADS - Složitost. Jinak co se algoritmů týče, tak si člověk (nejen) na matfyzu vystačí s Introduction to algorithms z MIT. Jen je třeba dávat pozor v předmětech, kde se pracuje s B-stromy - zavádějí je tam trochu jinak (ve výsledku je to samozřejmě stejné) a algoritmy operací jsou taky trochu jiné (ve srovnání s evergreenem od prof. Pokorného či zmíněných ADS).
Math, as Barbie says, is hard.
elviin avatar 29.5.2006 09:09 elviin | skóre: 29 | blog: elviin | Plzeň-Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Ja to nikdy nepouzil, ale mozna se ti to Martine hodi. Je to funkce z boostu:
dijkstra_shortest_paths
29.5.2006 11:44 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Podle mě to korektní není, protože to nezajišťuje, že "nevisited" vrcholy budou v té frontě uspořádány podle odhadu délky nejkratší cesty.

Vezměme si takovýto podgraf nějakého grafu
B____C
 \  /
  \/
  A
  |
  |
  D
délky hrany tyto d(A,D)=3, d(A,C)=4, d(A,B)=1, d(B,C)=1

začneme v A, do fronty přijde B(1), D(3), C(4); v dalším kroku teda zkoumám B, C dám nový odhad 2

takže fronta "nevisited" vrcholů je D(3), C(2)

což by asi být nemělo, ne?

(kdyby z D vycházela nějaká hrana a na ní byl nalepenej nějakej graf H, přidali bychom ještě hranu CD s ohodnocením třeba 0.5, tak se správně nenajde nejkratší cesta do H přes AB, BC, CD, ..)
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
Martin Tůma avatar 29.5.2006 15:09 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

Možná to neni z popisu zcela zřejmý, ale použitá fronta je samozřejmě stále prioritní. Situace, že by v ní byla posloupnost D(3), C(2) tak nemůže nastat.

Prošel jsem si tebou uváděnej příklad, a nevidim v tom problém, na danym grafu algoritmus funguje korektně.

Každý má právo na můj názor!
29.5.2006 16:44 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Možná to neni z popisu zcela zřejmý, ale použitá fronta je samozřejmě stále prioritní. Situace, že by v ní byla posloupnost D(3), C(2) tak nemůže nastat.
Tak to jsem teda nepochopil. Píšeš, že "Prioritní fronta ze standartní šablonové knihovny STL totiž touto vlastností neoplývá...", kde "touto vlastností" sem pochopil jako změna priority. Tedy jsem se domníval, že fronta 3, 4, 5 se nepřeuspořádá, pokud změním prioritu u druhého prvku na 2, tedy bude v podobě 3, 2, 5. Takhle to teda není? Pokud ne, tak jsem nějak nepochopil celý blogpost.

Jinak na tom "nakresleném grafu" by to neselhalo, domnívám se, že by to selhalo až na grafu, kde z D vede nějaká hrana a přidáme ještě hranu CD váhy 0.5 (což jsem naznačil v minulém příspěvku v závorce).
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
Martin Tůma avatar 29.5.2006 17:08 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Tak to jsem teda nepochopil. Píšeš, že "Prioritní fronta ze standartní šablonové knihovny STL totiž touto vlastností neoplývá...", kde "touto vlastností" sem pochopil jako změna priority. Tedy jsem se domníval, že fronta 3, 4, 5 se nepřeuspořádá, pokud změním prioritu u druhého prvku na 2, tedy bude v podobě 3, 2, 5. Takhle to teda není? Pokud ne, tak jsem nějak nepochopil celý blogpost.

Změnu priority fronta z STL neumožňuje, proto se taky místo změny priority přidává uzel do fronty znovu, čímž se samozřejmě zařadí na správné místo. Vrchol tedy může být ve frontě několikrát, přičemž jen jeho první výskyt je "platný".

Jinak na tom "nakresleném grafu" by to neselhalo, domnívám se, že by to selhalo až na grafu, kde z D vede nějaká hrana a přidáme ještě hranu CD váhy 0.5 (což jsem naznačil v minulém příspěvku v závorce).

Uvažoval jsem samozřejmě ten rozšířený graf (s hranou CD)

Každý má právo na můj názor!
29.5.2006 17:17 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Nevšiml jsem si toho queue.push(neighbour); Prostě po změně odhadu vzdálenosti sousedů už jsem zvyklý, že dál nic není :-)

Takže sorry, podcenil jsem tě :-)
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
29.5.2006 16:49 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
BTW Nechceš někam dát kompletní zdroják?
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
29.5.2006 16:55 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
Zdroják být ani nemusí - stačí důkaz správnosti algoritmu.
Math, as Barbie says, is hard.
29.5.2006 17:01 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
No já bych si spíš chtěl vyzkoušet, jak teda vlastně funguje ta fronta...
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
Martin Tůma avatar 29.5.2006 18:03 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

A Kefalín, čo Vy si predstavujete pod takým "důkaz správnosti algoritmu"?! ;-)

Obávám se, že ten už si budeš muset udělat sám. Nejsem matfyzák, takže se do podobných "experimentů" pouštím jen v případech krajní nouze, což zrovna tenhle není...

Každý má právo na můj názor!
Martin Tůma avatar 29.5.2006 17:51 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

Tady ho máš, ten "majstrštyk" ;-)

http://tumic.wz.cz/fel/#36CPP

Každý má právo na můj názor!
Martin Tůma avatar 29.5.2006 22:11 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

Slíbil jsem, že zde vyslovím můj názor na složitost takto modifikovaného algoritmu, která je IMHO (a už to tady zaznělo stále O(|H|log|U|).

Jediné co se mění je počet prvků(uzlů) v prioritní frontě, který oproti "originálnímu" algoritmu může být až |U|^2. Nicméně proto, že log(|U|^2) = 2log|U| = O(log|U|), zůstává asymptotická časová složitost algoritmu O(|H|log|U|). Skutečná složitost nicméně samozřejmě naroste, ale na "běžných" grafech IMHO nijak výrazně.

Nějaké námitky?

Každý má právo na můj názor!
Martin Tůma avatar 29.5.2006 23:43 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

Tak si odpovím sám. Zas tak růžový to asi přece jenom nebude... "Hlavní" cyklus se může provést až |H|*|U|, zařazení do fronty pak má složitost log(|H|*|U|). Celková asymptotická složitost řešení tedy spíše bude O(|H|*|U| + log(|H|*|U|)) = O(|H|*|U|), tedy horší, než u "originálu".

Každý má právo na můj názor!

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.