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 14:11 | Komunita

Některým uživatelům Firefoxu se tento týden do Firefoxu nainstalovalo neznámé rozšíření Looking Glass 1.0.3 (png). Ve fórů Mozilly se řešilo, zda se nejedná o malware. Mozilla později informovala, že se jednalo o reklamu na seriál Mr. Robot. Řadě uživatelů Firefoxu se jednání Mozilly vůbec nelíbilo. Mozilla proto automatickou instalaci doplňku ukončila [Hacker News, reddit].

Ladislav Hagara | Komentářů: 1
včera 12:00 | Nová verze

Po cca 3 týdnech od vydání Linux Mintu 18.3 s kódovým jménem Sylvia a prostředími MATE a Cinnamon byla oznámena také vydání s prostředími KDE a Xfce. Podrobnosti v poznámkách k vydání (KDE, Xfce) a v přehledech novinek s náhledy (KDE, Xfce). Linux Mint 18.3 je podporován do roku 2021.

Ladislav Hagara | Komentářů: 6
15.12. 12:55 | Nová verze

Byla vydána verze 17.12.0 KDE Aplikací (KDE Applications). Přehled novinek v kompletním seznamu změn a na stránce s dalšími informacemi. Aplikace, které nebyly dosud portovány na KDE Frameworks 5, byly z KDE Aplikací odstraněny.

Ladislav Hagara | Komentářů: 52
15.12. 03:00 | Komunita

Na Humble Bundle lze získat počítačovou hru Company of Heroes 2 (Wikipedie, YouTube) běžící také v Linuxu zdarma. Speciální akce končí v sobotu v 19:00.

Ladislav Hagara | Komentářů: 0
15.12. 02:00 | Zajímavý software

Christian Kellner představil na svém blogu projekt Bolt řešící bezpečnost rozhraní Thunderbolt 3 na Linuxu. Pomocí příkazu boltctl nebo rozšíření GNOME Shellu lze komunikovat s démonem boltd a například zakázat neznámá zařízení a předejít tak útokům typu Thunderstrike nebo DMA.

Ladislav Hagara | Komentářů: 8
15.12. 01:00 | Nová verze

Po půl roce vývoje od vydání verze 11.0 byla vydána verze 11.1 svobodného softwaru pro vytváření datových úložišť na síti FreeNAS (Wikipedie). Nejnovější FreeNAS je postaven na FreeBSD 11.1. Přehled novinek v příspěvku na blogu. Zdůraznit lze zvýšení výkonu OpenZFS, počáteční podporu Dockeru nebo synchronizaci s cloudovými službami Amazon S3 (Simple Storage Services), Backblaze B2 Cloud, Google Cloud a Microsoft Azure

Ladislav Hagara | Komentářů: 0
14.12. 23:55 | Nová verze

Po dvou měsících vývoje od vydání verze 235 oznámil Lennart Poettering vydání verze 236 správce systému a služeb systemd (GitHub, NEWS).

Ladislav Hagara | Komentářů: 10
14.12. 20:00 | Nová verze Ladislav Hagara | Komentářů: 0
14.12. 19:33 | Pozvánky

Pražská Fedora 27 Release Party, oslava nedávného vydání Fedory 27, se uskuteční 19. prosince od 19:00 v prostorách společnosti Etnetera (Jankovcova 1037/49). Na programu budou přednášky o novinkách, diskuse, neřízený networking atd.

Ladislav Hagara | Komentářů: 0
14.12. 18:11 | Nová verze

Byla vydána verze 2.11.0 QEMU (Wikipedie). Přispělo 165 vývojářů. Provedeno bylo více než 2 000 commitů. Přehled úprav a nových vlastností v seznamu změn.

Ladislav Hagara | Komentářů: 0
Jak se vás potenciálně dotkne trend odstraňování analogového audio konektoru typu 3,5mm jack z „chytrých telefonů“?
 (8%)
 (0%)
 (1%)
 (1%)
 (75%)
 (14%)
Celkem 1007 hlasů
 Komentářů: 45, poslední 1.12. 19:00
    Rozcestník

    Dotaz: Hledání cesty

    poky74 avatar 21.12.2009 19:30 poky74 | skóre: 36 | blog: Zápisník | Vrchlabí
    Hledání cesty
    Přečteno: 610×
    Ahoj všem :). Právě makám na jednom vcelku řekl bych zajímavém projektu a řeším docela zásadní problém, a to najití nejkratší cestu k cíli.

    Situace: Máme čtvercovou mapu, polohu (x,y) objektu a polohu cíle - také x,y.

    Posunovat se můžeme čtyřmi směry, nahoru dolu, doleva a doprava.

    Na mapě je vcelku dost překážek, překážky v podstatě tvoří cestu.

    Asi by to chtělo nějaký algoritmus, ale na to asi nemám hlavu, protože mě zatím nic nenapadá.

    Může někdo nahodit směr? Prosím vás nějak jednoduše, s tímhle typem úloh nemám žádné zkušenosti...

    Díky
    Chcete Linuxové samolepky nebo Tuxe na klíče? ->

    Řešení dotazu:


    Odpovědi

    Jendа avatar 21.12.2009 20:17 Jendа | skóre: 74 | blog: Výlevníček | JO70FB
    Rozbalit Rozbalit vše Re: Hledání cesty
    Vlna?
    Why did the multithreaded chicken cross the road? to To other side. get the
    poky74 avatar 21.12.2009 22:52 poky74 | skóre: 36 | blog: Zápisník | Vrchlabí
    Rozbalit Rozbalit vše Re: Hledání cesty
    Díky za link, konečně něco co jsem pochopil :D

    Avšak, tímto způsobem se vyzkoušejí prakticky všechny možnosti, což je řekl bych dost složité, ale díky za nakopnutí, zatím to vypadá nejpravděpodobněji :)
    Chcete Linuxové samolepky nebo Tuxe na klíče? ->
    22.12.2009 08:58 podlesh | skóre: 38 | Freiburg im Breisgau
    Rozbalit Rozbalit vše Re: Hledání cesty
    Moc jsem to podrobně nezkoumal, ale zřejmě se jedná o Dijkstrův algoritmus. Ten je obecně (tj. pro obecné grafy) optimální, nicméně toto je speciální případ kde je ideální A* algoritmus (viz odkaz dole). Rozdíl spočívá právě v tom, že A* zavádí heuristiku zajišťující že se nejprve vyzkoušejí možnosti vedoucí přímo směrem k cíli (což pravděpodobně stačí).
    hikikomori82 avatar 21.12.2009 20:43 hikikomori82 | skóre: 18 | blog: foobar | Košice
    Rozbalit Rozbalit vše Re: Hledání cesty
    vencour avatar 21.12.2009 21:13 vencour | skóre: 55 | blog: Tady je Vencourovo | Praha+západní Čechy
    Rozbalit Rozbalit vše Re: Hledání cesty

    Jak přesně zní zadání? Co víš hned a co se dozvíš později? Překážky mají nějaké ohodnocení? Co vlastně víš o té mapě? Jak jsou body a uzly spojené?

    Když jsem kdysi dostal řešit Jízdní řád na FAVce, tak jsem o orientovaných ohodnocených grafech moc nevěděl (začátek druháku).

    Ty nejhlubší objevy nečekají nutně za příští hvězdou. Jsou uvnitř nás utkány do vláken, která nás spojují, nás všechny.
    poky74 avatar 21.12.2009 22:42 poky74 | skóre: 36 | blog: Zápisník | Vrchlabí
    Rozbalit Rozbalit vše Re: Hledání cesty
    Najít na mapě cestu z bodu A do bodu B.

    Konkrétně je to dělané tak že se vypočítá cesta, bod A se na mapě přesune o jedno pole a provedou se další akce, takhle to bude v cyklu dokud souřadnice A se nebudou rovnat souřadnicím B.

    Z databáze si mohu vytáhnout souřadnice všech objektů na mapě, tedy souřadnice bodů A,B dále souřadnice všech překážek a souřadnice "cest" - rozuměj polí kde nic není, nic nebrání průchodu.

    Překážky ohodnocení nemají, jednoduše se na dané pole dá vstoupit (projít jím) nebo nedá.

    Znám rozměry, dokážu si z databáze vytáhnout údaje o daném políčku.

    Je to čtvercová mapa, jeden čtverec vedle druhého, horizontálně jich je 23 a vertikálně 13.

    Je to tedy obdélník který obsahuje 299 políček.
    Chcete Linuxové samolepky nebo Tuxe na klíče? ->
    vencour avatar 21.12.2009 23:16 vencour | skóre: 55 | blog: Tady je Vencourovo | Praha+západní Čechy
    Rozbalit Rozbalit vše Re: Hledání cesty

    A co ty překážky, jak je chceš vyjádřit? Nějakou penalizací?

    Předpokládam, že meze mapy jsou tam proto, aby sis všim, že za roh to nejde.

    Fakt Tě nic nenapadá, jak na to? Vzal bych pro začátek Googla a teorii grafů.

    Ty nejhlubší objevy nečekají nutně za příští hvězdou. Jsou uvnitř nás utkány do vláken, která nás spojují, nás všechny.
    poky74 avatar 22.12.2009 01:41 poky74 | skóre: 36 | blog: Zápisník | Vrchlabí
    Rozbalit Rozbalit vše Re: Hledání cesty
    Překážky? Pole kde je překážka je jakoby uzamčené, vyplněné, nejde se na ně přesunou, musejí se obejít.
    Chcete Linuxové samolepky nebo Tuxe na klíče? ->
    vencour avatar 22.12.2009 07:03 vencour | skóre: 55 | blog: Tady je Vencourovo | Praha+západní Čechy
    Rozbalit Rozbalit vše Re: Hledání cesty

    Ok, ale Ty chceš napsat program, ne? Proto musíš lidskou hodnotu a význam nějak přeložit pro počítač.

    Ty nejhlubší objevy nečekají nutně za příští hvězdou. Jsou uvnitř nás utkány do vláken, která nás spojují, nás všechny.
    poky74 avatar 22.12.2009 12:01 poky74 | skóre: 36 | blog: Zápisník | Vrchlabí
    Rozbalit Rozbalit vše Re: Hledání cesty
    Ty informace tahám z databáze
    Chcete Linuxové samolepky nebo Tuxe na klíče? ->
    Josef Kufner avatar 22.12.2009 12:27 Josef Kufner | skóre: 67
    Rozbalit Rozbalit vše Re: Hledání cesty
    BFS se dá napsat vcelku jednoduše tak, že na jeden select projdeš všechny možnosti vrámci jedné "vlny" (tj. pole o stejné vzdálenosti). Myslím, že v tomhle případě by to mohlo být asi nejrychlejší a přitom jednoduché.
    Hello world ! Segmentation fault (core dumped)
    Řešení 1× (kouby)
    22.12.2009 02:17 H4wk | skóre: 9 | blog: H4wkuv_blog
    Rozbalit Rozbalit vše Re: Hledání cesty
    23x13? Nepřemýšlet, vrazit BFS a je to.
    Korespondenční Seminář z Programování - Pro každého středoškoláka, který to s programováním myslí vážně.
    21.12.2009 21:38 petr_p | skóre: 59 | blog: pb
    Rozbalit Rozbalit vše Re: Hledání cesty

    Metrice tohoto prostoru se také říká manhattanská. Zkuste hledat pod tímto názvem.

    V podstatě všechny cesty, které se nevrací jsou stejně dlouhé (ať už jedete „úhlopříčkou“ nebo po hraně „obdélníku“).

    Obecný algoritmus na hledání nejkratší cesty je Dijkstrův. Jistě není problém převést mapu do reprezentace grafu a pustit na ni Dijkstru. Ale taková reprezentace bude asi velmi hustá a Dijkstra má kvadratickou složitost, což asi nebude výpočetně nejrychlejší řešení.

    Pro manhattonskou geometrii určitě bude existovat něco lepšího a asi bude i spousta ověřených implementací, protože to co chcete, je klasický příklad z her. Leč já nic takového neznám.

    Pokud nehrozí řešení bludiště (přesné zadání jste nerozvedl), asi by šlo něco napsat přístupem dynamického programování, kde by se dalo dostat lepší než kvadratickou složitost.

    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.