Student World

Golombovo pravítko (Golomb Ruler) je příkladem úlohy s omezujícími podmínkami. Jedná se o takové pravítko, kde se vzdálenosti všech značek vyjádřené přirozenými čísly od sebe navzájem liší.

Úlohu se třeba upřesnit: v první řadě nám nejde jen o značky sousední, ale o všechny dvojice. Za druhé pak pro X značek hledáme pravítko s nejmenší možnou délkou. Pro pravítka delší než 24 značek už vesměs neznáme řešení. Hrubá síla počítačů selže, takže i když nějakým postupem dokážeme najít nějaké řešení, nejsme v záplavě čísel schopni dokázat, že se jedná o pravítko nejkratší (optimální, angl. zkratka OGR). Přitom se samozřejmě nejedná o žádný nerozhodnutelný apod. problém, stavový prostor je určen jednoznačně, je konečný, akorát příšerně velký.

Příklad: pro velikost pět vypadá optimální pravítko
0, 1, 4, 9, 11
První bod 0 má od ostatních vzdálenosti 1, 4, 9 a 11, druhý bod 1 je od ostatních vzdálen 3, 8 a 10, za bodem 4 jsou další body vzdálené 5 a 7 cm a poslední dvojice má vzdálenost 2.
Celková délka optimálního pravítka o velikosti 2 je 11
Druhé řešení stejné délky: 0, 2, 7, 10, 11
Další řešení: 0, 3, 4, 9, 11

Jak vidíme, první dvě řešení jsou symetrická, což představuje jedno ze zjednodušení úlohy (takže ke třetímu řešení existuje ještě na základě téže symetrie čtvrté). Zjistíme-li v nějaké úloze, že N jako vzdálenost 1. a 2. značky od sebe není přípustná, platí totéž i pro vzdálenost značek posledních. Kromě těchto a dalších odstranění symetrií lze stavový prostor omezit také shora – všechna známá Golombova pravítko jsou kratší než X na 2.
Existuje několik formalizací problému i způsobů prohledávání stavového prostoru, přesto ale žádných zvláštních úspěchů dosaženo nebylo. Přece jen jde o NP úplný problém.
Problém není jen teoretickou hříčkou (kde příslušný popis mimochodem připomíná hru sudoku), ale nalézá i praktické využití například v radioastronomii.

Zdroj: Kolektiv autorů: Umělá inteligence 5, Academia, Praha 2007. Část R. Barták: Omezující podmínky: od sudoku po vesmírné aplikace

Poznámky:
Konkrétně využití v radioastronomii:
„Představte si 2 antény a velmi vzdálený zdroj rádiového signálu. Na každou z antén dopadá signál v jiné fázi. Podle vzájemné vzdálenosti antén, vlnové délky a fázového rozdílu signálů lze spočítat množiny bodů, ve kterých zdroj signálu může být. Pro jinak vzdálenou dvojici antén a jiný naměřený fázový rozdíl jsou tyto množiny jiné. Bod, ve kterém zdroj signálu skutečně je, leží někde v průniku těchto dvou množin. Čím víc dvojic, tím přesnější průnik, přesnější určení směru (zaostření) i vzdálenosti zdroje. Ovšem zajímavé jsou jen ty rozteče antén, které se neopakují. Pro 25 antén je to 300 dvojic. Ale jak je rozestavit, aby se vzdálenosti neopakovaly?“ (viz zde)

Protože se jedná o problém náročný na výpočetní sílu, není divu, že se objevila i snaha o distribuovaný internetový projekt. Aktuální stav počítání a klient ke stažení viz zde.

Trochu překvapivé je, že sice existují řešení dlouhých pravítek, ale neumíme ověřit, zda jsou optimální. Pro NP úplný problém by už přece ověření mělo být úlohou řádově lehčí.

autor Pavel Houser