abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×

    dnes 14:11 | Bezpečnostní upozornění

    Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) upozorňuje na hrozbu spojenou s používáním mobilní aplikace WeChat a její čínské verze Weixin (dále jen WeChat). Ta sbírá velký objem uživatelských dat, a právě to by – v kombinaci se způsobem jejich sběru – mohlo sloužit k přesnému zacílení kybernetických útoků.

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

    LibreQoS je svobodná aplikace vhodná pro poskytovatele internetové připojení pro rezervaci a řízení datových toků zákazníků (QoS - Quality of Service, QoE - Quality of Experience). Zdrojové kódy jsou k dispozici na GitHubu pod licencí GPLv2. Aktuální verze je 1.4.

    Ladislav Hagara | Komentářů: 0
    včera 23:22 | Nová verze

    Byla vydána Beta 1 verze KDE 6 (Plasma, Frameworks a Gear) postavené na Qt 6. Testovat lze například v distribuci KDE Neon. Stabilní verze je plánována na konec února 2024. Předchozí velké vydání 5 vylo vydáno téměř před 10 lety (červenec 2014).

    Ladislav Hagara | Komentářů: 15
    včera 23:00 | Komunita

    Open-source webmail Roundcube se připojil k balíku aplikací Nextcloudu. Převzetí firmou Nextcloud ale plánováno není, pouze integrace a podpoření vývoje.

    Fluttershy, yay! | Komentářů: 0
    včera 18:44 | IT novinky

    Stability AI představila SDXL Turbo, tj. umělou inteligenci pro generování obrázků z textového popisu v reálném čase, viz ukázka na YouTube.

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

    Svobodná webová platforma pro sdílení a přehrávání videí PeerTube (Wikipedie) byla vydána v nové major verzi 6. Přehled novinek i s náhledy a videi v oficiálním oznámení a na GitHubu (6.0.0, 6.0.1).

    Ladislav Hagara | Komentářů: 0
    včera 11:55 | IT novinky

    S eDoklady lze mít od ledna 2024 občanku v mobilní aplikaci [Digitální a informační agentura – DIA].

    Ladislav Hagara | Komentářů: 5
    včera 07:00 | IT novinky

    Google představil novou doménu nejvyššího řádu: .meme. Viz například knowyour.meme nebo find.meme.

    Ladislav Hagara | Komentářů: 9
    28.11. 21:22 | IT novinky

    IKEA představila 3 senzory pro chytrou domácnost: senzor na dveře a okna PARASOLL, bezdrátový pohybový senzor VALLHORN a senzor úniku vody BADRING. Budou kompatibilní s Home Assistant?

    Ladislav Hagara | Komentářů: 1
    28.11. 20:44 | Nová verze

    Weston, referenční implementace kompozitoru pro Wayland, byl vydán ve verzi 13.0.0. Přehled novinek v oznámení.

    Ladislav Hagara | Komentářů: 0
    Používáte modální textový editor?
     (75%)
     (3%)
     (2%)
     (20%)
    Celkem 289 hlasů
     Komentářů: 8, poslední 16.11. 22:24
    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: 633×
    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: 78 | blog: Jenda | JO70FB
    Rozbalit Rozbalit vše Re: Hledání cesty
    Vlna?
    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: 56 | 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: 56 | 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: 56 | 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: 70
    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.