Problém obchodního cestujícího

Problém obchodního cestujícího

Návštěvníci mají možnost pokusit se vyřešit jeden z klasických obtížných problémů teoretické informatiky - Problém obchodního cestujícího (Travelling Salesman Problem - TSP). Problém sestává z nalezení nejkratší okružní trasy mezi danými městy za předpokladu znalosti jejich vzájemných vzdáleností. Exponát sestává z velké vodorovné mapy s vyznačenými městy (10-20), z nichž trčí kolíčky se zářezem. Návštěvník spojuje města provázkem nebo silonovým lankem, které vytahuje z počátku a na němž je číselná stupnice ukazující vzdálenost. V jistém místě je vyznačena vzdálenost optimálního řešení, takže v každém okamžiku návštěvník vidí jak moc se k němu přiblížil.

Exponát je doplněn grafickým panelem o složitých problémech, jak „dobré“ jsou v nich počítače a zda se vyrovnají lidem.

Cíl
Ukázat příklad teoreticky obtížného optimalizačního problému, v němž lidé dosahují oproti počítačům relativně dobrých výsledků v krátkém čase.

Mám zájem