Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Sarjusz-Wolski Z.

1 2006

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: zadanie rozwózkowe

Sortuj według:

Ogranicz wyniki do:

Zadanie rozwózkowe, czyli problem komiwojażera

Sarjusz-Wolski Z.

Gospodarka Materiałowa i Logistyka

2006

nr 5

31-32

Na początku była gra-łamigłówka, wymyślona w 1859 r. przez sławnego irlandzkiego matematyka, Wiliama Rowana Hamiltona. Składał się na nią dwunastościan, którego każda z 12 ścian była foremnym pięciokątem, a we wszystkich 20 wierzchołkach schodziły się trzy krawędzie. Każdy wierzchołek tej bryły przedstawiał znane duże miasto (Bruksela, Dehli, Frankfurt itd.). Zagadka polegała na znalezieniu takiej trasy podróży, która by zapewniała tylko jednorazową wizytę w każdym mieście. Od niej wzięły swoją nazwę tzw. linie Hamiltona, stanowiące dzisiaj część teorii grafów. Problem komiwojażera ("the traveling salesman problem"), zwany też zadaniem rozwózkowym, przypomina linie Hamiltona, ale jest znacznie utrudniony - trasa (łuki grafu) obejmująca wszystkie punkty (węzły grafu) musi być trasą najkrótszą (ewentualnie generującą minimalne koszty transportu).