Zítra proběhne jednodenní online konference InstallFest 2021. Na programu je celá řada zajímavých přednášek, workshopů a také stánků. Dění lze sledovat na Twitteru.
Byla vydána nová verze 6.5 v Javě napsané aplikace pro komplexní návrh rozmístění nábytku a dalšího vybavení v interiérech Sweet Home 3D. Vyzkoušet lze online verzi. Nedávno byly aktualizovány také knihovny nábytku.
Nové verze webových prohlížečů Firefox a Chrome byly vydávány každých 6 týdnů. Vývojářům Firefoxu se nelíbilo, že Chrome bude mít vždy větší číslo verze, proto se rozhodli vydávat nové verze Firefoxu každé 4 týdny. Aktuální stav: Firefox 86 byl vydán v 8. týdnu a Chrome 89 v 9 týdnu letošního roku. V kterém týdnu bude mít Firefox větší číslo verze než Chrome?
… více »Thom Holwerda popisuje na OSnews pracovní stanici Raptor Blackbird Secure Desktop (architektura POWER9) a své zkušenosti s ní včetně provozu desktopových aplikací.
Byla vydána nová verze 1.54 editoru zdrojových kódů Visual Studio Code (Wikipedie). Přehled novinek i s náhledy a animovanými gify v poznámkách k vydání. Ve verzi 1.54 vyjde také VSCodium, tj. komunitní sestavení Visual Studia Code bez telemetrie a licenčních podmínek Microsoftu.
Check Point zveřejnil report, podle kterého NSA v roce 2013 vytvořila exploit pro operační systém MS Windows. Exploit sloužil k lokální eskalaci práv. O rok později tento exploit ukradli hackeři z Číny. Až po dvou letech byl exploit zveřejněn a Microsoft vydal aktualizaci. Jinými slovy, celé téma se točí o tom, jak NSA zřejmě přispěla ke globálnímu snížení kybernetické bezpečnosti. Celý příběh podrobně naleznete na checkpoint.com.
Framework Flutter (Wikipedie) pro vývoj mobilních, webových i desktopových aplikací byl vydán ve verzi 2 a související programovací jazyk Dart (Wikipedie) byl vydán ve verzi 2.12. Proběhla online konference Flutter Engage. Videozáznam je k dispozici na YouTube. Canonical zde oznámil (Twitter, YouTube), že Flutter je výchozí volba pro vývoj nových aplikací pro Ubuntu.
Společnost AMD na YouTube představila novou grafickou kartu AMD Radeon RX 6700 XT postavenou na architektuře RDNA 2. V prodeji bude od 18. března. Její cena byla stanovena na 479 dolarů.
Uživatelsky přívětivý shell fish byl vydán ve verzi 3.2.0 Vylepšuje uživatelské rozhraní (doplňování, práce s historií úprav textu aj.), přidává napovídání argumentů dalších aplikací, zjednodušuje syntaxi (expanze rozsahů), opravuje chyby.
Steam Link je nově dostupný také pro 64bitový x86 Linux. Streamovat hry z výkonného počítače s nainstalovanou službou Steam lze tedy vedle telefonu, tabletu nebo televize i do počítače s Linuxem. Instalovat Steam Link lze z Flathubu. Od prosince 2018 je k dispozici Steam Link pro Raspberry Pi.
RTFM - Read Tumič's FlaMes!
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"
.
Tiskni
Sdílej:
Ty asi nebudeš Pražák, co?!
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.
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.
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.
Ale tohle nám asi neříkali ani na matfyzuPredmet slozitost, fibbonaciho haldy i jejich aplikace v Dijstrove algoritmu se probiraly... ;).
B____C \ / \/ A | | Ddé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, ..)
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ě.
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).
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)
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í...
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?
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".