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íží...
dnes 11:00 | Bezpečnostní upozornění

Byly zveřejněny informace o bezpečnostní chybě CVE-2016-8655 v Linuxu zneužitelné k lokální eskalaci práv. Chyba se dostala do linuxového jádra v srpnu 2011. V upstreamu byla opravena minulý týden [Hacker News].

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

Přibližně před měsícem bylo oznámeno, že linuxová distribuce SUSE Linux Enterprise Server (SLES) běží nově také Raspberry Pi 3 (dokumentace). Obraz verze 12 SP2 pro Raspberry Pi 3 je ke stažení zdarma. Pro registrované jsou po dobu jednoho roku zdarma také aktualizace. Dnes bylo oznámeno, že pro Raspberry Pi 3 je k dispozici také nové openSUSE Leap 42.2 (zprávička). K dispozici je hned několik obrazů.

Ladislav Hagara | Komentářů: 4
včera 06:00 | Zajímavý software

OMG! Ubuntu! představuje emulátor terminálu Hyper (GitHub) postavený na webových technologiích (HTML, CSS a JavaScript). V diskusi k článku je zmíněn podobný emulátor terminálu Black Screen. Hyper i Black Screen používají framework Electron, stejně jako editor Atom nebo vývojové prostředí Visual Studio Code.

Ladislav Hagara | Komentářů: 29
včera 06:00 | Zajímavý článek

I letos vychází řada ajťáckých adventních kalendářů. QEMU Advent Calendar 2016 přináší každý den nový obraz disku pro QEMU. Programátoři se mohou potrápit při řešení úloh z kalendáře Advent of Code 2016. Kalendáře Perl Advent Calendar 2016 a Perl 6 Advent Calendar přinášejí každý den zajímavé informace o programovacím jazyce Perl. Stranou nezůstává ani programovací jazyk Go.

Ladislav Hagara | Komentářů: 8
3.12. 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ářů: 14
3.12. 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ářů: 25
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ářů: 16
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ářů: 5
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
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 774 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Obchodní cestující vs. reálný svět

Josef Kufner avatar 21.2.2011 10:44 Josef Kufner | skóre: 66
Obchodní cestující vs. reálný svět
Přečteno: 598×
Ahoj,

mám GPS souřadnice své aktuální polohy, cílové polohy a pak několik dalších míst, která chci v libovolném pořadí navštívit. Jak najít optimální cestu?

Neznám cesty mezi jednotlivými body ani jejich vzdálenosti či dobu za jak dlouho trvá přesun mezi nimi. Jediné, co mám je jejich vzdálenost vzdušnou čarou.

Pokud zadám pevné pořadí bodů, je už celkem lehké předat seznam Google Maps a nechat si cestu nakreslit (příklad). Otázkou však je, jak seřadit místa po cestě tak, aby cesta byla nejlepší, hlavně v případě, kdy chci použít hromadnou dopravu a nikoliv vlastní auto – návaznosti spojů můžou jednoduchým odhadem celkem hodně zamávat.
Hello world ! Segmentation fault (core dumped)

Odpovědi

21.2.2011 11:12 kuka
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
Jestli jsem to spravne pochopil tak neznas cenu cesty mezi uzly (dokonce ani jestli existuje). Tzn. takove zadani nema reseni. Vuci jake metrice by tedy cesta mela byt "nejlepsi" - cena, delka, doba? Jak to souvisi s programovanim?
Josef Kufner avatar 21.2.2011 11:18 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
Otázka je o tom, jak takovou cenu automatizovaně zjistit, abych při zadání několika míst dostal cestu, kudy a v jakém pořadí kam jít.

Metriku jsem neuváděl konkrétní, protože na ní v podstatě až tak nezáleží a prakticky to je kombinace ceny a doby.
Hello world ! Segmentation fault (core dumped)
Michy avatar 21.2.2011 16:55 Michy | skóre: 11 | Praha
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
Problém obchodního cestujícího nespočívá v obtížnosti nalezení algoritmu, ale v tom, že složitost triviálního algoritmu exponenciálně roste s počtem míst, která je třeba projít. Efektivnější algoritmus zatím nikdo nevymyslel. Více viz. wiki
21.2.2011 18:28 petr_p | skóre: 59 | blog: pb
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
Nikoliv algoritmus, ale problém. Tudíž efektivnější algoritmus vymyslet nelze.
21.2.2011 20:57 karel
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
To se právě neví. Pokud by se někomu podařilo najít efektivnější algoritmus, tak by to znamenalo, že P=NP. A to je zatím nerozhodnutý problém.
Martin Tůma avatar 21.2.2011 18:00 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět

Ale tu metriku musíš definovat, jinak neřešíš problém obchodního cestujícího, ale problém "ženská" - nevim co chci. Nelze zkrátka hledat to nejlepší, když ani nevíš co je dobrý...

Každý má právo na můj názor!
poky74 avatar 21.2.2011 18:55 poky74 | skóre: 36 | blog: Zápisník | Vrchlabí
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět

To je naprosto perfektní hláška, dávám do bookmarků :-D

Chcete Linuxové samolepky nebo Tuxe na klíče? ->
21.2.2011 20:22 NeoV | skóre: 23
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
+1 :-D
21.2.2011 19:21 JS
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
Kolik je tech bodu? Pokud jich je min nez 8, proste vyzkousej vsechny moznosti..

Pokud jich je vic, asi by se vyplatilo pouzit geneticky algoritmus, protoze tam se dobre zadavaji a meni kriteria, a neni to slozite naprogramovat (ale zas je to celkem pomale).
Josef Kufner avatar 21.2.2011 22:22 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
No, koukám, že jsem si s tím titulkem pěkně zadělal :-D

Samotné seřazení bodů je v pohodě, to z wikipedie vemu njaký pěkný algoritmus a je hotovo. To oč mi jde je, jak k té hromádce bodů sehnat hrany. Tedy jde o doplnění grafu o hrany těsně před tím, než na to pustím algoritmus obchodního cestujícího.

Jako takové polovičaté řešení se nabízí použít jako metriku vzdálenosti vzdušnou čarou a takto seřazené body předat plánovači cesty v Google Maps. Ovšem při použití hromadné dopravy to není příliš užitečné.
Hello world ! Segmentation fault (core dumped)
21.2.2011 22:53 NeoV | skóre: 23
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
no tak si z google maps dotiahni informaciu o vzdialenosti (autom) medzi kazdymi dvoma bodmi a a tieto vystupy vzdialenosti ti budu tvorit hrany....
22.2.2011 09:17 JS
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
To prave neudelas, protoze volba tech hromadnych prostredku je soucast te optimalizacni ulohy (neni to obchodni cestujici, protoze v tve uloze maji prestupy v uzlech ruznou cenu, a navic zalezi na case, kdy se tam dostanes). Neda se tedy udelat ani to, ze by se vybiraly dve po sobe jdouci hrany (tedy trojice vrcholu) a s nimi se to vyzkouselo, a tato data pouzit jako vstup pro reseni.

Ale ja bych to proste bruteforcoval (popr. muzes zvolit par nahodnych reseni a ta pak mirne perturbovat). Ono se Googlu nic nestane, a clovek s tim nestravi tolik casu.
AraxoN avatar 22.2.2011 15:37 AraxoN | skóre: 45 | blog: slon_v_porcelane | Košice
Rozbalit Rozbalit vše Re: Obchodní cestující vs. reálný svět
A fine is a tax for doing wrong. A tax is a fine for doing well.

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.