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í
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
včera 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 0
včera 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
2.12. 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 18
2.12. 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 8
2.12. 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 2
2.12. 12:55 | Nová verze

Google Chrome 55 byl prohlášen za stabilní. Nejnovější stabilní verze 55.0.2883.75 tohoto webového prohlížeče přináší řadu oprav a vylepšení (YouTube). Opraveno bylo také 36 bezpečnostních chyb. Mariusz Mlynski si například vydělal 22 500 dolarů za 3 nahlášené chyby (Universal XSS in Blink).

Ladislav Hagara | Komentářů: 4
2.12. 11:55 | Pozvánky

Máte rádi svobodný software a hardware nebo se o nich chcete něco dozvědět? Přijďte na 135. sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.

xkucf03 | Komentářů: 0
2.12. 00:10 | Nová verze

Byla vydána verze 3.2 svobodného systému pro detekci a prevenci průniků a monitorování bezpečnosti počítačových sítí Suricata. Z novinek lze zmínit například podporu protokolů DNP3 a CIP/ENIP, vylepšenou podporu TLS a samozřejmě také aktualizovanou dokumentaci.

Ladislav Hagara | Komentářů: 0
1.12. 21:00 | Nová verze

Byla vydána beta verze Linux Mintu 18.1 s kódovým jménem Serena. Na blogu Linux Mintu jsou hned dvě oznámení. První o vydání Linux Mintu s prostředím MATE a druhé o vydání Linux Mintu s prostředím Cinnamon. Stejným způsobem jsou rozděleny také poznámky k vydání (MATE, Cinnamon) a přehled novinek s náhledy (MATE, Cinnamon). Linux Mint 18.1 bude podporován až do roku 2021.

Ladislav Hagara | Komentářů: 0
1.12. 16:42 | Nová verze

Byl vydán Devuan Jessie 1.0 Beta 2. Jedná se o druhou beta verzi forku Debianu bez systemd představeného v listopadu 2014 (zprávička). První beta verze byla vydána v dubnu letošního roku (zprávička). Jedna z posledních přednášek věnovaných Devuanu proběhla v listopadu na konferenci FSCONS 2016 (YouTube, pdf).

Ladislav Hagara | Komentářů: 0
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 767 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

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: 599×
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: 73 | blog: Výlevníček | 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: 37 | Praha
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: 66
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.