Specifikace zápočtového příkladu v C/C++
Tomáš Hradecký

Autoatlas-hledání nejkratší cesty
---------------------------------

Obecný popis
------------
Mnou zamýšlený zápočtový program je pěkným využitím
teorie grafů v praxi - pomocí něj bude uživatel moci
hledat nejkratší cestu silniční sítí a to podle různých
kritérií (délka trasy, doba jízdy, spotřeba pohonných
hmot). Bude též možné prohlédnout trasu jízdy na mapě.
Toto jsou základní a pro uživatele nejdůležitější
funkce. Další vylepšení jsou možná.

Reprezentace silniční sítě
--------------------------
Silniční síť hodlám představovati grafem, ve kterém
každý vrchol (město) je dán nejen svým číslem a názvem,
nýbrž i dvěma souřadnicemi v rovině. Hrany (silnice)
mají své ohodnocení dle 1.DÉLKY TRASY 2.DOBY JÍZDY
3.SPOTŘEBY BENZÍNU.
Platí ale jistá omezení, která jsou dána použitým
algoritmem, který potřebuje znát dobré dolní odhady
vzdáleností mezi městy. Zde vystupuje na povrch aspekt
dvourozměrné plochy, na níž je silniční síť umístěna:
mapa bude mít zadané MĚŘÍTKO- bude určeno, kolik metrů
"je" jeden pixel.
Nyní vysvětlím situaci na příkladu vzdáleností- to
samé bude podobně platit pro čas a pro spotřebu.
Silnice mezi městy bude kreslena jako čára. Ohodnocení
hrany musí být vyšší než tato vzdálenost vzdušnou čarou.
Tímto získávám dobré dolní odhady vzdáleností VŠECH měst
navzájem mezi sebou jako jejich vzdálenost vzdušnou
čarou. Tu lze lehce spočíst ze souřadnic měst a měřítka.
Podobně platí pro čas a benzín.

Algoritmus
----------
Prostý Dijkstrův algoritmus by byl pro velký graf
pomalý-vyhledává totiž cestu zcela náhodně.
My můžeme využít toho, že máme graf zadán v rovině,
kde euklidovská vzdálenost dvou vrcholů je vždy dobrým
dolním odhadem vzdálenosti cesty po silnici a můžeme
(zjednodušeně řečeno) vydávat se nejprve do těch
vrcholů, které se blíží k cílovému vrcholu. Toto platí
pro všechna kritéria(vzdálenost,čas,benzín).
Tento postup je exaktně popsán jako Dijkstrův
algoritmus s heuristikou a to například v učebnici
KAPITOLY Z DISKRÉTNÍ MATEMATIKY (Matoušek,Nešetřil.
první vydání v r.1996, Matfyzpress) na straně 102.
Vyhledávání probíhá vždy jen podle jednoho kritéria-
ostatní dvě jsou používána jako doplňková.

Prostředí
---------
Beta verze bude psaná s cílem zjistit
prakticky efektivnost algoritmu, počítám tedy
s použitím Borland C/C++ pro DOS.

A to je vše?
------------
Doufám, že jsem do specifikace uvedl dostatek údajů.
Pokud budete mít nějaké dotazy nebo připomínky, pošlete
je, prosím, na e-mail: HRADTOM@POST.CZ.

Poznámky k ROČNÍKOVÉMU PROJEKTU II
----------------------------------
-DOS betaverze pro předmět Programování v C/C++ již
byla odladěna a úspěšně předvedena.Betaverze pro předmět
RP2 bude již psána ve vývojovém prostředí Borland C++ Builder


Zpět na stránku programu