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í
×
včera 23:33 | Zajímavý software

Byl vydán ShellCheck ve verzi 0.4.6. Jedná se o nástroj pro statickou analýzu shellových skriptů. Shellové skripty lze analyzovat na webové stránce ShellChecku, v terminálu nebo přímo z textových editorů. Příklady kódů, na které analýza upozorňuje a doporučuje je přepsat. ShellCheck je naprogramován v programovacím jazyce Haskell. Zdrojové kódy jsou k dispozici na GitHubu pod licencí GPLv3.

Ladislav Hagara | Komentářů: 0
včera 23:33 | Pozvánky

Czech JBoss User Group zve na setkání JBUG v Brně, které se koná ve středu 5. dubna 2017 v prostorách Fakulty informatiky Masarykovy univerzity v místnosti A318 od 18:00. Přednáší Pavol Loffay na téma Distributed Tracing and OpenTracing in Microservice Architecture.

… více »
mjedlick | Komentářů: 0
včera 11:33 | Zajímavý článek

Národní centrum kybernetické bezpečnosti (NCKB) vypracovalo (pdf) 26 podrobných bezpečnostních doporučení pro síťové správce. Tato doporučení jsou nastavena tak, aby je bylo možné aplikovat v každé instituci. Jsou rozdělena na tři základní části: bezpečnost infrastruktury, bezpečnost stanic a serverů a bezpečnost uživatelů.

Ladislav Hagara | Komentářů: 9
včera 05:55 | Komunita

Prezident Nadace pro svobodný software (FSF) Richard M. Stallman vyhlásil na slavnostním ceremoniálu v rámci konference LibrePlanet 2017 vítěze Free Software Awards za rok 2016. Ocenění za společenský přínos získal SecureDrop (Wikipedie). Za rozvoj svobodného softwaru byl oceněn Alexandre Oliva (Wikipedie).

Ladislav Hagara | Komentářů: 0
včera 04:44 | Nová verze

Byla vydána verze 0.7.0 debugovacího nástroje cgdb. Mezi novinky patří například zvýrazňování syntaxe jazyka Rust. Podrobnosti v poznámkách o vydání.

Neel | Komentářů: 0
25.3. 22:00 | Komunita

Portál Stack Overflow po roce opět vyzpovídal své uživatele, jedná se především o vývojáře softwaru, a zveřejnil (podcast) detailní výsledky průzkumu. Průzkumu se letos zúčastnilo více než 64 tisíc vývojářů. Jejich nejmilovanější platformou je linuxový desktop. Ten je také druhou nejpoužívanější platformou vývojářů.

Ladislav Hagara | Komentářů: 7
24.3. 11:55 | Komunita

Vývojový tým OpenSSL ve spolupráci s iniciativou Core Infrastructure konsorcia Linux Foundation spustil proces přelicencování této kryptografické knihovny ze současné licence na licenci Apache Licence v 2.0 (ASLv2). Nová licence usnadní začleňování OpenSSL do dalších svobodných a open source projektů. Všichni dosavadní vývojáři OpenSSL (Authors) obdrží v následujících dnech email s prosbou o souhlas se změnou licence.

Ladislav Hagara | Komentářů: 32
24.3. 01:11 | Komunita

Před třemi týdny Mozilla.cz představila projekt Photon, jehož cílem je návrh a implementace nového vzhledu Firefoxu. Včera zveřejnila první náhled vzhledu Photon. Práce na projektu Photon jsou rozděleny do pěti týmů, které celkem čítají 19 lidí. Zaměřují se na zlepšení prvního spuštění Firefoxu a zaujetí nových uživatelů, celkovou úpravu vzhledu, zlepšení animací, zrychlení odezvy uživatelského rozhraní a také upravení nabídek. Vývoj lze sledovat v Bugzille.

Ladislav Hagara | Komentářů: 50
23.3. 20:00 | Komunita

OneDrive pro firmy je již ve webových prohlížečích na Linuxu stejně rychlý jako na Windows. Microsoft opravil chybu z listopadu loňského roku. OneDrive pro firmy běžel na Linuxu mnohem pomaleji než na Windows. V popisu chyby bylo uvedeno, že stačilo v prohlížeči na Linuxu nastavit v user-agentu Windows a vše se zrychlilo. Odpovědí Microsoftu bylo (Internet Archive: Wayback Machine), že Linux není podporován. Po bouřlivých diskusích na redditu i Hacker News byla chyba nalezena a opravena.

Ladislav Hagara | Komentářů: 9
23.3. 19:00 | Zajímavý projekt

Byla vyhlášena soutěž Hackaday Prize 2017. Soutěž je určena vývojářům open source hardwaru. Pro výherce je připraveno celkově 250 tisíc dolarů. Každý ze 120 finalistů získá tisíc dolarů. Nejlepší pak navíc 50, 30, 20, 15, 10 a 5 tisíc dolarů. Jedná se již o čtvrtý ročník soutěže. V roce 2014 zvítězil projekt globální sítě open source pozemních satelitních stanic SatNOGS. V roce 2015 zvítězil open source systém pro řízení elektrických invalidních vozíků pohybem očí Eyedriveomatic. V roce 2016 zvítězil modulární robot Dtto.

Ladislav Hagara | Komentářů: 0
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (14%)
 (2%)
 (71%)
 (3%)
 (10%)
Celkem 947 hlasů
 Komentářů: 72, poslední 1.3. 11:16
    Rozcestník

    Dotaz: Grafové algoritmy - najkratsia cesta vs. vrcholmy

    29.11.2010 16:36 rss
    Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Přečteno: 607×
    Mám orientovaný graf s ohodnotenými hranamy a chcem prejsť všetky vrcholy tak aby výsledná cesta bola najkratšia (súčet hodnôt hrán bol najmenší). Neviem aký algoritmus použiť.

    Zo školy si už nič nepamätám tak som si prešiel pár základných grafových algoritmov ale zdá sa mi že tento problém nepasuje na ani jeden algoritmus (Obchodný cestujúca, Dijkstrov, Borúvkuv, Janikov, Ford-Fulkernson,..).

    Obchodný cestujúci to nieje, tam je podmienka že štart a cieľ musí byť v tom istom vrchole a každý vrchol sa môže prejsť iba raz. Toto mi je jedno kde je štart a cieľ a tiež mi je jedno koľkokrát sa cez vrchol prejde...

    Čínsky poštár to tiež nieje, pretože tam ide o to aby sa každá hrana prešla iba raz a to mi je jedno...

    Takto som postupne vylúčil všetky algoritmy a nemám nič :-)

    Odpovědi

    29.11.2010 19:01 frr | skóre: 32
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Řešíte akademické cvičení, nebo praktickou úlohu? Pokud jde o praktickou úlohu, tak se nestyďte a prostě odněkud začněte programovat :-)

    Nejvíc práce Vám dá podle mého "infrastruktura" - implementace datových struktur, loadování dat z disku, nějaký výstup (uživatelské rozhraní) - budete tu topologii skutečně graficky zobrazovat (případně i zadávat)? Až budete mít tohle hotovo, pak si můžete hrát s heuristikou algoritmu - ala "robot Karel" :-)

    Pokud by hrany byly rovnocenné, asi bych začal tím, že bych se snažil procházet graf "od buka do buka" (jako když na lyžích křižujete sjezdovku). Tj. začal bych třeba "jdi do sousedního uzlu, který je nejvíc vlevo z dosud nenavštívených" - a když bych narazil na koncový uzel (žádný další nenavštívený uzel), zkusil bych pátrat po nejbližším dalším dosud nenavštíveném uzlu (pátral bych 1,2,3... hopy okolo) nebo bych si pamatoval, ve kterém uzlu jsem naposledy zaznamenal víc než jednu možnost, kam se vydat, a tam bych se vrátil. A pokračoval bych doprava. Anebo dál doleva, ale pak by to nebylo "cik cak", ale "zvenčí dovnitř" (resp. zevnitř ven, podle toho kde jste začal). V dalším kroku bych mohl zkusit zohlednit v rozhodování cenu další hrany (nějakou váhou). Nebo bych mohl zkusit nějakou "shlukovou analýzu blízkého okolí (N hopů)" - abych si zbytečně nevytvářel "dlouhé slepé větve", nebo abych elegantně "vyčistil malé lokální smyčky bez únikových cest", třeba i s lokální dooptimalizací hrubou silou (všechny možnosti). Nebo bych v "blízkém okolí" detekoval cykly v grafu a vyhýbal bych se dražším hranám... Zkuste přemýšlet, jak byste problém řešil selským rozumem (za volantem s mapou v ruce) - a algoritmus zapsat jako program.

    Tak mě napadá: je to rovinný (2D) graf, nebo amorfní chumel? (při zobrazení v 2D se hrany kříží a vedou klidně napříč celým grafem) Tam by pak neměly smysl pojmy "napravo a nalevo" :-)

    Nemám v oboru formální vzdělání - nicméně mám představu, že tohle nemá nějaké "jediné správné a přímo spočítatelné" řešení. Problém typu "obchodní cestující" má k Vašemu zadání skutečně nejblíž. Patrně velmi přesně Vaše zadání odpovídá praktickému problému různých kurýrních služeb (pošta, DHL/UPS/TNT/DPD/PPL/GP...). Četl jsem, že to někdo zkouší třeba pomocí genetických algoritmů. Taky mi to připomíná některá "témata" Xscreensaveru :-)
    [:wq]
    29.11.2010 19:14 frr | skóre: 32
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Aha, on je orientovaný :-( Otrava...
    [:wq]
    29.11.2010 19:20 frr | skóre: 32
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Orientovaný nebo ne, napadlo mě začít nějakou shlukovou analýzou. Najít jakási "těžiště" a k nim "gravitovat".

    Pokud je orientovaný, možná bych se snažil napřed najít 1) uzly, odkud není cesty ven nebo kde není cesty dovnitř a 2) uzavřené oblasti, odkud není cesty ven nebo kde není cesty dovniř. To je základ pro posouzení, zda vůbec máte šanci všecky uzly projít, případně kde začít a kde skončit - a do kterých uzlů či oblastí se lze vrátit.

    Takový obchodní cestující, kde všecky cesty jsou jednosměrky? :-)
    [:wq]
    29.11.2010 19:32 petr_p | skóre: 59 | blog: pb
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy

    Problém má určitou složitost. Takže sebelepší algoritmus nebude lepší, než je třída problému. Pokud je problém NP-úplný, tak na polynomickou složitost algoritmu zapoměňte.

    Samozřejmě, když si odpostíme podmínku optimálnosti, tak se dají vymyslet heuristiky, které občas trochu pomůžou.

    29.11.2010 19:01 Radek Miček | skóre: 23 | blog: radekm_blog
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Váš problém je NP-úplný. Pokud bude vstupem úplný graf, kde platí trojúhelníková nerovnost, tak se v optimálním sledu neopakují vrcholy, tudíž je to cesta, a tudíž je váš problém TSP pro cesty v grafu s trojúhelníkovou nerovností, který je NP-úplný.
    29.11.2010 19:07 Radek Miček | skóre: 23 | blog: radekm_blog
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Intuitivní důkaz :-)
    29.11.2010 19:34 Radek Miček | skóre: 23 | blog: radekm_blog
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Řešení lze kódovat jako permutace vrcholů grafu. Tudíž bych mezi permutacemi hledal takovou, která reprezentuje nejlepší řešení.

    Napřed bych spočítal tranzitivní uzávěr grafu. Pak bych vybral vrcholy, co v té permutaci mohou být první, druhé, třetí, čtvrté... Zvolil bych první vrchol a podíval se, který vrchol může být další, zvolil ho... Dále bych průběžně propagoval důsledky svých voleb směrem dolů, abych případný problém odhalil co nejdříve (jako v CSP). Stejně tak je možné testovat délku cesty průbežně.
    stativ avatar 29.11.2010 19:02 stativ | skóre: 54 | blog: SlaNé roury
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Proč si vyloučil Borůvku a Jarníka? Mě se zdá, že je to přesně to, co potřebuješ (minimální kostra).
    Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
    stativ avatar 29.11.2010 19:03 stativ | skóre: 54 | blog: SlaNé roury
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Aha, on je orientovaný, to jsem krapet přehlédl.
    Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
    29.11.2010 21:46 rss
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Je to čisto praktický problém, nie akademický...

    Ide o to, že mám v krajine okolo jednej dediny pár zaujímavých miest všeliako poprepájaných cestamy, cestičkamy, stezkamy, ktoré by som si chcel v lete na bicykli pozrieť. Je to presne 15 bodov takže mi je jedno akú bude mať algoritmus výpočtovú zložitosť (ak nebude NP-úplný to by už boli asi bilióny potenciálnych ciest). Samozrejme toto sa dá určiť intuatívne z hlavy pohľadom do mapy ale kež už som kedysi absolvoval predmet Diskrétna matematika tak mi to dalo chrobáka do hlavy :-)

    Tak som si určil, že tie body v krajine sú vrcholy grafu a hrany medzi nimi sú rôzne možné cesty ohodnotené počtom kilometrov medzi nimi. Lenže potom ma napadlo, že kritérium vzdialenosti nieje jediné, podľa ktorého sa človek v teréne rozhoduje. Tento algoritmus by ma totiž napríklad viedol z hrebeňa dole do doliny lebo je tam blízky bod a potom naspäť hore na hrebeň na nejaký ďalší bod, ktorý je trebars len o kúsok ďalej. Lenže človek by logicky dal prednosť prejsť najprv 2 body hore na hrebeni v jednej nadmorskej výške aj keď sú trebars dvojnásobne vzdialené ako bod v doline. A až potom by zišiel dole aby v kuse nechodil hore-dole čo by ma na biku vyčerpalo :-)

    Preto som z grafu urobil digraf (orientovaný graf) aby som smer AB (dolekopcom) mohol ohodniť inak ako opačný smer BA (horekopcom). Takto môžem hrane z bodu A do B dať hodnotu 4 (4 km) a naopak z B do A dať 6 (4 km + 2 ako penalizácia že to je hore kopcom). Túto penalizáciu budem dávať len tak subjektívne z hlavy podľa sklonu kopca. Určite by sa dal nájsť aj nejaký algoritmus ktorý by tu penalizáciu vypočítaval automaticky ako rozdiel nadmorskej výšky dvoch bodov...Ďalšia penalizácia môže byť či to je pekná/rozbitá cesta, atraktívne/neatraktívne okolie...No a výsledok je že mám ako som písal v prvom príspevku orientovaný graf s hranami ohodnotenými nejakými hodnotamy a chcem prejsť v grafe všetky vrcholy s najmenšou "vzdialenosťou" (v uvodzovkách pretože ako som písal, ohodnotenie hrán nevyjadruje len vzdialenosť).

    Žiadne ďalšie obmedzenia niesu. Začať a skončiť môžem kde chcem. Ak to je výhodné tak vrcholom grafu môžem prejsť aj viackrát (ale minimálne raz). Po rovnakých hranách môžem prechádzať tiež viackrát, po nevýhodných hranách nemusím ísť ani raz...
    29.11.2010 22:48 Radek Miček | skóre: 23 | blog: radekm_blog
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Když to je jen 15 vrcholů a cesta vede z každého do každého tak bych to řešil takto:

    Spočítal bych nejkratší cesty z každého vrcholu do každého. Protože je řešení (průchod vrcholy) reprezentován permutací, tak lze projít všech n! permutací, u každé si zapamatovat skóre a pak vydat tu nejlepší. Jelikož 15! už je celkem velké číslo, tak bych to těch patnáct prvků rozdělil všemi možnými způsoby (6435) na 2 části (7 a 8 vrcholů). V první části bych našel nejlepší (=nejlevnější) permutaci, která končí číslem 1, nejlepší, která končí číslem 2, ... Ve druhé části bych našel nejlepší, která začíná číslem 1, nejlepší začínající číslem 2, ... Pak bych tyto nejlepší permutace ze 7 a 8 prvků zkusil různě pospojovat a zapamatoval bych si nejlepší řešení. Takto jsem zpracoval jedno rozdělení z 6435 a 6434 mi ještě zbývá.

    Celé to pak lze řešit obdobně metodou rozděl a panuj. Prostě se ta čísla v permutaci rozdělí na 2 části všemi možnými způsoby a pak tyto dvě části zase spojuji.
    30.11.2010 19:32 mc_bizon | skóre: 3
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    6453 * 7! * 8 ! = 15!. Žiadnym rozdeľovaním si nepomôžeš.
    30.11.2010 20:17 Radek Miček | skóre: 23 | blog: radekm_blog
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Jenže já mám zhruba 6435 * (7! + 8! + čas na spojení).
    30.11.2010 09:34 frr | skóre: 32
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Chtělo by to nějaký algoritmus, který by poskládal trasy tak, aby člověk jel pořád jenom skopce dolů :-)
    [:wq]
    30.11.2010 19:52 FooBar
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    Bagr Z., Buldozer C.A.T. Nekonecny presun zeminy na trase cyklisty. In Proceedings of the 99th ACM Symposium of Algorithms and Heavy Machinery, page 101, November 2010. ?;)
    30.11.2010 19:48 mc_bizon | skóre: 3
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    http://en.wikipedia.org/wiki/Edmonds's_algorithm

    Čítal som len ten prvý odstavec, ale vyzerá to byť to čo potrebuješ
    1.12.2010 13:38 extremni lama | skóre: 14 | blog: e_lama
    Rozbalit Rozbalit vše Re: Grafové algoritmy - najkratsia cesta vs. vrcholmy
    tak jestli je to 15 bodu tak mas 15! = 1.3e12 permutaci takze na dnestnich pocitacich by se dali projit i vsechny... Teda pokud ti nevadi na vysledek par minut pockat.

    Jinak pokud nepotrebujes optimalni reseni, ale staci ti nejaky "dostatecne dobry" tak bych na to sel nejak takhle:
    for i in 1..1000: # or another big number instead of 1000
            x = random_permutation()
            if length(x) < best_length:
                    best_x = x;
                    best_length = length(x)
    
    The enemy of my enemy is still my enemy.

    Založit nové vláknoNahoru

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

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