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 04:44 | Nová verze

    Byla vydána nová stabilní verze 3.24.0, tj. první z nové řady 3.24, minimalistické linuxové distribuce zaměřené na bezpečnost Alpine Linux (Wikipedie) postavené na standardní knihovně jazyka C musl libc a BusyBoxu. Přehled novinek v poznámkách k vydání.

    Ladislav Hagara | Komentářů: 0
    dnes 03:33 | Komunita

    Na čem pracují vývojáři v Rustu napsaného mikrokernelového unixového operačního systému Redox OS (Wikipedie)? Byl publikován přehled vývoje za květen. Vypíchnout lze nový scheduler EEVDF nebo port desktopového prostředí Xfce na Redox OS.

    Ladislav Hagara | Komentářů: 0
    včera 22:22 | Komunita

    Upozornění pro uživatele Asahi Linuxu: Neaktualizujte macOS na verzi 27 Golden Gate! Apple změnil detekci spouštěcích oddílů. Po aktualizaci oddíl s Asahi Linuxem nevidí. Snad je to jenom chyba.

    Ladislav Hagara | Komentářů: 0
    včera 15:11 | Komunita

    Na webu konference Den IPv6, která se konala 4. června v Národní technické knihovně v pražských Dejvicích, jsou nyní k dispozici všechny prezentace (v PDF) a jejich videozáznamy. Organizátory konference byly i letos sdružení CESNET, CZ.NIC a NIX.CZ.

    VSladek | Komentářů: 0
    včera 13:11 | Nová verze

    Byla vydána nová verze 9.1.0 správce sbírky fotografií digiKam (Wikipedie). Přehled novinek i s náhledy v oficiálním oznámení (NEWS). Vypíchnout lze vylepšené vyhledávání nebo podporu Pixel Motion Photos. Nejnovější digiKam je ke stažení také jako balíček ve formátu AppImage. Stačí jej stáhnout, nastavit právo ke spuštění a spustit.

    Ladislav Hagara | Komentářů: 0
    včera 11:44 | Pozvánky

    Přihlaste svou přednášku na další ročník konference LinuxDays, který proběhne 3. a 4. října na FIT ČVUT v pražských Dejvicích. Příjem témat poběží do konce prázdnin, pak proběhne veřejné hlasování a následně sestavení programu.

    Petr Krčmář | Komentářů: 2
    včera 04:44 | Nová verze

    Byla vydána nová verze 2.4.68 svobodného multiplatformního webového serveru Apache (httpd). Řešeno je mimo jiné 13 zranitelností.

    Ladislav Hagara | Komentářů: 2
    8.6. 22:44 | IT novinky

    Apple na své vývojářské konferenci WWDC26 (Worldwide Developers Conference, keynote) představil řadu novinek. Vypíchnout lze novou generaci Apple Intelligence a zbrusu novou Siri, která dostala název Siri AI. Kvůli Aktu o digitálních trzích (DMA) však funkce Siri AI nebudou v systémech iOS 27 a iPadOS 27 k dispozici uživatelům v Evropské unii.

    Ladislav Hagara | Komentářů: 0
    8.6. 22:22 | Nová verze

    Byla vydána nová verze 1.18.0 distribučního frameworku Flatpak (Wikipedie), tj. technologie umožňující distribuovat aplikace v podobě jednoho instalačního souboru na různé linuxové distribuce a jejich různá vydání. Přehled novinek na GitHubu. Vypíchnout lze podporu rozhraní /dev/kfd pro výpočty na kartách AMD (AMDKFD).

    Ladislav Hagara | Komentářů: 0
    8.6. 20:44 | Nová verze

    aMule (Wikipedie), tj. multiplatformní klient pro peer-to-peer sdílení souborů pro sítě eD2k and Kademlia, byl po více než pěti letech od vydání poslední verze 2.3.3, vydán v nové major verzi 3.0.0 (GitHub). S novou webovou stránkou a dokumentací.

    Ladislav Hagara | Komentářů: 5
    Které desktopové prostředí na Linuxu používáte?
     (11%)
     (8%)
     (2%)
     (15%)
     (31%)
     (3%)
     (6%)
     (3%)
     (15%)
     (26%)
    Celkem 1856 hlasů
     Komentářů: 30, poslední 3.4. 20:20
    Rozcestník


    Dotaz: Algoritmus - navrh dvojiteho bludiste

    15.9.2018 02:13 proste matfyzak
    Algoritmus - navrh dvojiteho bludiste
    Přečteno: 1868×

    Nazdar,

    znate hru bludiste Minotaurus? Jsou to pohyblive a nepohyblive bludiste nad sebou se dvema kulickami, takze pohyb neni uplne trivialni https://www.youtube.com/watch?v=GzWjoPpLoiw

    Vyresit jej v PC by melo jit jednoduse, BFS/DFS/Dijkstra, mozna neco jako A*. Ma otazka je jina: jak takove bludiste vygenerovat tak, aby bylo netrivialni na vyreseni?

    Poznamky:
    • Bezny postup na generovani jednoducheho bludiste pouzitim kostry grafu nestaci. Chybejici slepa ulicka znamena zablokovanou cestu a nutnost zkusit neco jine.
    • Opravdu zalezi na pozici obou kulicek. Taktez pri resitelnosti zalezi na zacatku a konci.
    • Snazil jsem se dokazat, ze je to NP tezke, nepovedlo se.
    • Na "trivialitu" by se pouzil pocet tahu na vyreseni. Vim, ze to nestaci - bludiste cik-cak je nejdelsi, ale nic lepsiho nemam.

    Napady:

    • O(n^7): Vygenerovat dve nahodne spojite bludiste v O(n^2), zkusit vsechny kombinace O(n^2) pozic kulicek a pro kazdou pozici vyresit narocnost, coz je teoreticky max vsech posunuti posuvne casti a pozic kulicek O(n^3).
    • O(n^3 * 2^{2n^2}) bruteforce tvaru bludist.
    • O(n^5 + ?): Vygenerovat jedno bludiste, genetickym algoritmem zkouset prodluzovat druhe bludiste a hodnotit prejdenou vzdalenost a snazit se dosahnout max.
    • O(?): Celociselne programovani (ILP) s par tisic podminkami opisujicimi bludiste a pohyby by to mohlo zvladnout. Moc nevim, jak.
    Da se to lepe? Treba ne pro neomezenou velikost "n", ale pro neco jako je v tom videu. Me algoritmy by neskoncili pred tepelnou smrti vesmiru.
    Tohle neni zadny ukol, jenom mi to vrta hlavou.

    Odpovědi

    16.9.2018 22:13 janek
    Rozbalit Rozbalit vše Re: Algoritmus - navrh dvojiteho bludiste
    Asi bude nejlepsi se zeptat ve skole ;) Tipnu si ze na to bude Dijkstra, podle wiki je O(n^2) nebo optimalizovany O(e + n log n), Vas dvojvrstvy 'minotaurus' je asi totez jenom vynasobeny vsema smysluplnyma polohama druhe vrstvy. Casova slozitost porad stejna, ale pro vice hran a vrcholu. Ani dve kulicky nic nezmeni. Napad na generovani ale nemam, asi kdyz dokazete specifikovat 'netrivialni', dostanete se blize k reseni.
    16.9.2018 22:51 Radek Isa | skóre: 14
    Rozbalit Rozbalit vše Re: Algoritmus - navrh dvojiteho bludiste
    Řekl bych, že problém je v malém počtu stavů. Pokud se dostaneš do jednoho stavu nemáš moc možností jak se dostat do stavu ve kterém jsi ještě nebyl. Tím je podstatně omezen stavový prostor. Stavem myslím pozici kuliček a pozici bludiště.

    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.