Dokument

Zdanie 1
Ponieważ macierz odległości jest symetryczna (czyli odległość od sklepu X do sklepu Y jest taka

sama jak ze sklepu Y do X), możemy zastosować następującą procedurę.
Na początku załóżmy, że nasz komiwojażer ma wrócić do sklepu z którego wystartował.

Ustalamy długość trasy, która zawiera tylko trzy sklepy (np. sklep 1, 2 i 3):
Trasa sklep 1 sklep 2 sklep 3 sklep 1 ma 3+7+4=14 km.

→

(Uwaga: trasa sklep 2 sklep 3 sklep 1 sklep 2 też ma 14 km i wszystkie trasy pomiędzy

→

tymi trzema sklepami - jeśli wracamy do sklepu początkowego - mają po 14 km, więc nie ma

znaczenia, czy mówimy o trasie sklep 1 sklep 2 sklep 3 sklep 1, czy o trasie sklep 2

→

sklep 3 sklep 1 sklep 2)

→

Dodajmy do tego sklep 4. Możemy to zrobić na 3 sposoby:

–

pomiędzy sklepem 1 a sklepem 2. Kosztuje to dodatkowe 2km drogi, bo droga między
sklepem 1 a sklepem 2 to 3km, a droga sklep 1 sklep 4 sklep 2 to 2+3=5km;

→

–

pomiędzy sklepem 1 a sklepem 3 – dodatkowe 4km

–

pomiędzy sklepem 2 a sklepem 3 – dodatkowe 2km.

A więc najlepiej wstawić sklep 4 pomiędzy sklep 1 a 2 lub między 2 a 3.
Teraz wstawmy sobie sklep 5. Możemy to zrobić na 6 sposobów:

–

pomiędzy sklepem 1 a sklepem 2 – dodatkowe 9km

–

pomiędzy sklepem 1 a sklepem 3 – dodatkowe 8km

–

pomiędzy sklepem 1 a sklepem 4 – dodatkowe 15km

–

pomiędzy sklepem 2 a sklepem 3 – dodatkowy 1km

–

pomiędzy sklepem 2 a sklepem 4 – dodatkowe 10km

–

pomiędzy sklepem 3 a sklepem 4 – dodatkowe 7km

A więc najlepiej wstawić sklep 5 pomiędzy sklep 2 a 3.
i na koniec wstawmy sobie sklep 6. Możemy to zrobić na 10 sposobów:

–

pomiędzy sklepem 1 a sklepem 2 – dodatkowe 4km

–

pomiędzy sklepem 1 a sklepem 3 – dodatkowe 9km

–

pomiędzy sklepem 1 a sklepem 4 – dodatkowe 8km

–

pomiędzy sklepem 1 a sklepem 5 – brak dodatkowych km

–

pomiędzy sklepem 2 a sklepem 3 – dodatkowe 3km

–

pomiędzy sklepem 2 a sklepem 4 – dodatkowe 4km

–

pomiędzy sklepem 2 a sklepem 5 – dodatkowy 1km

–

pomiędzy sklepem 3 a sklepem 4 – dodatkowe 9km

–

pomiędzy sklepem 3 a sklepem 5 – dodatkowe 7km

–

pomiędzy sklepem 4 a sklepem 5 – to nawet skraca trasę o 1 km

A więc najlepiej wstawić sklep 6 pomiędzy sklep 4 a 5.
No więc spróbujmy. Mamy naszą trasę między trzema sklepami:

sklep 1 sklep 2 sklep 3 sklep 1

→

Wstawiamy sklep 4 pomiędzy sklep 1 a 2:

sklep 1 sklep 4 sklep 2 sklep 3 sklep 1

→

Wstawiamy sklep 5 pomiędzy sklep 2 a 3:

sklep 1 sklep 4 sklep 2 sklep 5 sklep 3 sklep 1

→

Wstawiamy sklep 6 pomiędzy sklep 4 a 5: Nie da się!
Musimy więc zobaczyć, na jakiej zamianie najmniej stracimy. Widać, że jeśli sklep 6 wstawimy
między 1 a 5 zamiast między 4 a 5 to stracimy tylko 1 km. Ale takie wstawianie też jest

niemożliwe.
następne w kolejce jest wstawienie sklepu 6 między 2 a 5 (stracimy 2km). I to już się da

zrobić:

sklep 1 sklep 4 sklep 2 sklep 6 sklep 5 sklep 3 sklep 1

→

można się zastanowić, czy nie lepiej wstawiać nieoptymalnie sklep 4 albo 5 zamiast sklepu 6.
Popatrzmy: wybierając dla sklepu 4 lokalizację między 2 a 3 nie tracimy żadnych kilometrów,

ale blokujemy sobie możliwość wstawienia sklepu 5 między 2 a 3, a to kosztuje co najmniej 6
km. Wstawiając sklep 4 między 1 a 3 tracimy 2 km, a więc tyle samo, co na nieoptymalnym

wstawieniu sklepu 6, a więc nic się nie poprawia. Z kolei wstawiając nieoptymalnie sklep 5
tracimy co najmniej 6 km.
Zostajemy więc przy trasie

sklep 1 sklep 4 sklep 2 sklep 6 sklep 5 sklep 3 sklep 1

→

Ma ona 2+3+2+3+4+4=18 km i jest to najkrótsza trasa pozwalająca objechać wszystkie
sklepy i wrócić do pierwszego. Warto zauważyć, że tworzy ona koło, a więc komiwojażer może

wyruszyć z dowolnego sklepu i do niego wróć i zawsze (jeśli będzie jechał wg powyższej trasy
przejedzie 18 km).
W zadaniu nie jest jednak sprecyzowane czy ma on wracać do sklepu, z którego wyruszył. Jeśli
nie, to wystarczy usunąć z naszej trasy najdłuższą drogę, czyli jedną z dróg 4-kilometrowych.

Np. usuwamy drogę ze sklepu 5 do 3. A więc nasz komiwojażer musi zacząć w sklepie 3 i ma
trasę:

sklep 3 sklep 1 sklep 4 sklep 2 sklep 6 sklep 5,

→

która ma 14 km i jest to najkrótsza trasa pozwalająca objechać wszystkie sklepy bez wracania

do pierwszego.
Teraz najdłuższa droga. patrzymy na to co obliczaliśmy wyżej i dokładamy do naszej trasy z

trzema sklepami najdłuższe (a nie najkrótsze, jak do tej pory) drogi:

sklep 1 sklep 2 sklep 3 sklep 1

→

Wstawiamy sklep 4 pomiędzy sklep 1 a 3:

sklep 1 sklep 2 sklep 3 sklep 4 sklep 1

→

Wstawiamy sklep 5 pomiędzy sklep 1 a 4:

sklep 1 sklep 2 sklep 3 sklep 4 sklep 5 sklep 1

→

Wstawiamy sklep 6 pomiędzy sklep 3 a 4:

sklep 1 sklep 2 sklep 3 sklep 6 sklep 4 sklep 5 sklep 1

→

taka trasa ma więc 3+7+8+5+9+8=40 km i jest to najdłuższa trasa pozwalająca objechać
wszystkie sklepy i wrócić do pierwszego.
Jeśli nie chcemy wracać do pierwszego sklepu, to wystarczy usunąć z naszej trasy najkrótszą
drogę, czyli drogę 3-kilometrową ze sklepu 1 do 2. A więc nasz komiwojażer musi zacząć w

sklepie 2 i ma trasę:

sklep 2 sklep 3 sklep 6 sklep 4 sklep 5 sklep 1,

→

która ma 37 km i jest to najdłuższa trasa pozwalająca objechać wszystkie sklepy bez wracania
do pierwszego.
Zadanie 2
Robimy dokładnie identycznie jak zadanie 1:
Trasa węzeł 1 węzeł 2 węzeł 3 węzeł 1 ma 100+120+140=360 zamówień.

→

Dodajmy do tego węzeł 4. Możemy to zrobić na 3 sposoby:

–

pomiędzy węzłem 1 a węzłem 2. Daje to dodatkowe 150 zamówień, bo między węzłem
1 a węzłem 2 jest 100 zamówień, a droga węzeł 1 węzeł 4 węzeł 2 to

→

150+100=250 zamówień;

–

pomiędzy węzłem 1 a węzłem 3 – dodatkowe 40 zamówień

–

pomiędzy węzłem 2 a węzłem 3 – dodatkowe 10 zamówień.

A więc najlepiej wstawić węzeł 4 pomiędzy węzeł 1 a 2.
Teraz wstawmy sobie węzeł 5. Możemy to zrobić na 6 sposobów:

–

pomiędzy węzłem 1 a węzłem 2 – utrata 10 zamówień

–

pomiędzy węzłem 1 a węzłem 3 – utrata 70 zamówień

–

pomiędzy węzłem 1 a węzłem 4 – utrata 20 zamówień

–

pomiędzy węzłem 2 a węzłem 3 – utrata 60 zamówień

–

pomiędzy węzłem 2 a węzłem 4 – dodatkowe 20 zamówień

–

pomiędzy węzłem 3 a węzłem 4 – dodatkowe 70 zamówień

A więc najlepiej wstawić węzeł 5 pomiędzy węzeł 3 a 4.
i na koniec wstawmy sobie węzeł 6. Możemy to zrobić na 10 sposobów:

–

pomiędzy węzłem 1 a węzłem 2 – utrata 70 zamówień

–

pomiędzy węzłem 1 a węzłem 3 – utrata 80 zamówień

–

pomiędzy węzłem 1 a węzłem 4 – utrata 90 zamówień

–

pomiędzy węzłem 1 a węzłem 5 – dodatkowe 40 zamówień

–

pomiędzy węzłem 2 a węzłem 3 – utrata 70 zamówień

–

pomiędzy węzłem 2 a węzłem 4 – utrata 50 zamówień

–

pomiędzy węzłem 2 a węzłem 5 – dodatkowe 10 zamówień

–

pomiędzy węzłem 3 a węzłem 4 – dodatkowe 50 zamówień

–

pomiędzy węzłem 3 a węzłem 5 – dodatkowe 90 zamówień

–

pomiędzy węzłem 4 a węzłem 5 – dodatkowe 30 zamówień

A więc najlepiej wstawić węzeł 6 pomiędzy węzeł 3 a 5.
No więc spróbujmy. Mamy naszą trasę między trzema węzłami:

węzeł 1 węzeł 2 węzeł 3 węzeł 1

→

Wstawiamy węzeł 4 pomiędzy węzeł 1 a 2:

węzeł 1 węzeł 4 węzeł 2 węzeł 3 węzeł 1

→

Wstawiamy węzeł 5 pomiędzy węzeł 3 a 4: nie da się!
Musimy więc zobaczyć, na jakiej zamianie najmniej stracimy. Widać, że jeśli węzeł 5 wstawimy

między 2 a 4 zamiast między 3 a 4 to stracimy tylko 50 zamówień. Tak więc robimy:

węzeł 1 węzeł 4 węzeł 5 węzeł 2 węzeł 3 węzeł 1

→

Wstawiamy węzeł 6 pomiędzy węzeł 3 a 5: nie da się!
Musimy więc zobaczyć, na jakiej zamianie najmniej stracimy. Widać, że następną w kolejce

możliwością wstawienia węzła 6, jest wstawienie go pomiędzy węzły 3 i 4, ale to też się nie da.
Między 1 a 5 też nie, ale między 4 a 5 już tak (tracimy na tym 60 zamówień w stosunku do

wstawiania pomiędzy 3 a 5):

węzeł 1 węzeł 4 węzeł 6 węzeł 5 węzeł 2 węzeł 3 węzeł 1

→

W sumie wstawiając węzły 5 i 6 nieoptymalnie straciliśmy 110 zamówień. Można się
zastanowić, czy nie dałoby się tego zrobić lepiej. Popatrzmy na możliwości wstawienia węzła 4:

wstawiając go inaczej niż między 1 a 2 stracimy co najmniej 110 zamówień – nie ma więc

sensu tego zmieniać. Więc na pewno musimy mieć trasę

węzeł 1 węzeł 4 węzeł 2 węzeł 3 węzeł 1

→

Teraz w węźle 5: kolejną niewykorzystaną możliwością jest wstawienie go między 1 a 2, ale to
się nie da. Następna w kolejce jest możliwość wstawienia między 1 a 4, to się da zrobić i

stracimy na tym 90 zamówień w stosunku do optymalnego wstawienia węzła 5 między 3 a 4.
Mielibyśmy wtedy

węzeł 1 węzeł 5 węzeł 4 węzeł 2 węzeł 3 węzeł 1

→

Do tej trasy węzła 6 również nie możemy wstawić optymalnie (czyli między 3 a 5). Następną w

kolejce możliwością wstawienia węzła 6, jest wstawienie go pomiędzy węzły 3 i 4, ale to też się
nie da, a nawet gdyby się dało, to stracilibyśmy 40 zamówień w stosunku do optymalnego

wstawienia. czyli razem mielibyśmy już stratę 90+40=130 zamówień, podczas gdy na trasie

węzeł 1 węzeł 4 węzeł 6 węzeł 5 węzeł 2 węzeł 3 węzeł 1

→

straciliśmy ich 110.
Tak więc trasa

węzeł 1 węzeł 4 węzeł 6 węzeł 5 węzeł 2 węzeł 3 węzeł 1

→

jest najlepsza i nie da się jej poprawić. Mamy na niej 150+40+70+40+120+140=560

zamówień.