Решение задачи коммивояжёра. 5 городов

Ім'я файлу: Metod_dinam_progr_пример.doc
Розширення: doc
Розмір: 126кб.
Дата: 25.12.2020
скачати

ОБРАЗЕЦ ВЫПОЛНЕНИЯ ЗАЧЕТНОГО ЗАДАНИЯ №2

Метод динамического программирования решения задачи коммивояжера
В

качестве примера рассмотрим решение задачи коммивояжёра.
5 городов

Сначала рассматриваются все частичные решения длины на 1 меньше, чем тупиковые. В нашем случае:

i₁ i₂ i₃ i₄ 1 – тупиковые решения

1 i₁ i₂ i₃ i₄– частичные решения

Имеем одно продолжение: j(1,i₁,i₂,i₃,i₄)=(i₄,1)

Разобьем все частичные решения на 4 группы:

i₄=2 i₄=3 i₄=4 i₄=5

j=(2,1) j=(3,1) j=(4,1) j=(5,1)

f=C₂₁=5 f=C₃₁=19 f=C₄₁=9 f=C₅₁=22

Рассмотрим частичные решения длины на 1 меньше предыдущих.

Это решения вида

(1, i₁, i₂, i₃)
Для каждого из них найдём наилучшее продолжение. Оно зависит от того, через какие города мы уже прошли, и какой город был последним:

j(1, i₁, i_2,i₃)=(i₃, i₄,1)
i₃=2
если уже возможные вычисления

прошли города продолжения стоимости

(3,4) j=(2,5,1) f=C₂₅+f((5,1))=25+22=47

(3,5) j=(2,4,1) f=C₂₄+f((4,1))=30+9=39

(4,5) j=(2,3,1) f=C₂₃+f((3,1))=17+19=36
i₃=3

(2,5) j=(3,4,1) f=C₃₄+f((4,1))=6+9=15

(4,5) j=(3,2,1) f=C₃₂+f((2,1))=15+5=20

(2,4) j=(3,5,1) f=C₃₅+f((5,1))=1+22=23
i₃=4

(2,3) j=(4,5,1) f=C₄₅+f((5,1))=6+22=28

(2,5) j=(4,3,1) f=C₄₃+f((3,1))=24+19=43

(3,5) j=(4,2,1) f=C₄₂+f((2,1))=50+5=55

i₃=5

(2,4) j=(5,3,1) f=C₅₃+f((3,1))=7+19=26

(2,3) j=(5,4,1) f=C₅₄+f((4,1))=10+9=19

(3,4) j=(5,2,1) f=C₅₂+f((2,1))=8+5=13

Находим наилучшее продолжение для частичного решения длины ещё меньше на 1: (1,i₁,i₂)

S – множество всех возможных продолжений на один шаг.

Пуcть на b₀S достигается минимум:

min f(C_k-3, j(C₁, … ,C_k-3,b))=f(C_k-3,j(C₁C₂, … , C_k-3, b₀)), где k=5

Тогда наилучшим продолжением для частичного решения k-3 будет

j(C₁, … , C_k-3, b₀))
Пусть прошли города (1,2,3)

Тогда S((1,2,3))={4,5} остаются не пройденными

b=4 f(4, j(1,2,3,4))=C₃₄+f(j(1,2,3,4))=C₃₄+f((4,5,1))=6+28=34

b=5 f(5,j(1,2,3,5))=C₃₅+f(j(1,2,3,5))=C₃₅+f((5,4,1))=1+19=20

(3,5,4,1) – наилучшее продолжение.
(1,2,4) S((1,2,4))={3,5}

b=3 f(3, j(1,2,4,3))=C₄₃+f(j(1,2,4,3))=C₄₃+f((3,5,1))=24+23=47

b=5 f(5, j(1,2,4,5))=C₄₅+f(j(1,2,4,5))=C₄₅+f((5,3,1))=6+26=32

(4,5,3,1) – наилучшее продолжение
(1,2,5) S((1,2,5))={3,4}

b=3 f(3 j(1,2,5,3))=C₅₃+f(j(1,2,5,3))=C₅₃+f((3,4,1))=7+15=22

b=4 f(4, j(1,2,5,4))=C₅₄+f(j(1,2,5,4))=C₅₄+f((4,3,1))=10+43=53

(5,3,4,1) – наилучшее продолжение
(1,3,2) S((1,3,2))={4,5}

b=4 f(4, j(1,3,2,4))=C₂₄+f(j(1,3,2,4))=C₂₄+f((4,5,1))=30+28=58

b=5 f(5, j(1,3,2,5))=C₂₅+f(j(1,3,2,5))=C₂₅+f((5,4,1))=25+19=44

(2,5,4,1) – наилучшее продолжение
(1,3,4) S={2,5}

b=2 f(2, j(1,3,4,2))=C₄₂+f(j(1,3,4,2))=C₄₂+f((2,5,1))=50+47=97

b=5 f(5, j(1,3,4,5))=C₄₅+f(j(1,3,4,5))=C₄₅+f((5,2,1))=6+13=19

(4,5,2,1) – наилучшее продолжение
(1,3,5) S={2,4}

b=2 f(2, j(1,3,5,2))=C₅₂+f(j(1,3,5,2))=C₅₂+f((2,4,1))=8+39=47

b=4 f(4, j(1,3,5,4))=C₅₄+f(j(1,3,5,4))=C₅₄+f((4,2,1))=10+55=65

(5,2,4,1) – наилучшее продолжение
(1,4,2) S={3,5}

b=3 f(3, j(1,4,2,3))=C₂₃+f(j(1,4,2,3))=C₂₃+f((3,5,1))=17+23=40

b=5 f(5, j(1,4,2,5))=C₂₅+f(j(1,4,2,5))=C₂₅+f((5,3,1))=25+26=51

(2,3,5,1) –наилучшее продолжение

(1,4,3) S={2,5}

b=2 f(2, j(1,4,3,2))=C₃₂+f((2,5,1))=15+47=62

b=5 f(5, j(1,4,3,5))=C₃₅+f((5,2,1))=1+13=14

(3,5,2,1) – наилучшее продолжение
(1,4,5) S={2,3}

b=2 f(2, j(1,4,5,2))=C₅₂+f((2,3,1))=8+36=44

b=3 f(3, j(1,4,5,3))=C₅₃+f((3,2,1))=7+20=27

(5,3,2,1) – наилучшее продолжение
(1,5,2) S={3,4}

b=3 f(3, j(1,5,2,3))=C₂₃+f((3,4,1))=17+15=32

b=4 f(4, j(1,5,2,4))=C₂₄+f((4,3,1))=30+43=73

(2,3,4,1) – наилучшее продолжение

S={2,4}

b=2 f(2, j(1,5,3,2))=

+f(j(1,5,3,2))=

+f((2,4,1))=15+39=54

b=4 f(4, j(1,5,3,4))=

+f(j(1,5,3,4))=

+f((4,2,1))=6+55=61

(3,2,4,1) – наилучшее продолжение
(1,5,4) S={2,3}

b=2 f(2, j(1,5,4,2))=

+f((2,3,1))=50+36=86

b=3 f(3, j(1,5,4,3))=

+f((3,2,1))=24+20=44

(4,3,2,1) – наилучшее продолжение

Находим все частичные решения длины k-4 (ещё на единицу меньше),

то есть вида (1,

), и наилучшие продолжения для этих решений:
(1,2) S={3,4,5}

b=3 f(3, j(1,2,3))=

+f((3,5,4,1))=17+20=37

b=4 f(4, j(1,2,4))=

+f((4,5,3,1))=30+32=62

b=5 f(5, j(1,2,5))=

+f((5,3,4,1))=25+22=47

(2,3,5,4,1) – наилучшее продолжение
(1,3) S={2,4,5}

b=2 f(2, j(1,3,2))=

+f((2,5,4,1))=15+44=59

b=4 f(4, j(1,3,4))=

+f((4,5,2,1))=6+19=25

b=5 f(5, j(1,3,5))=

+f((5,2,4,1))=1+47=48

(3,4,5,2,1) – наилучшее продолжение
(1,4) S={2,3,5}

b=2 f(2, j(1,4,2))=

+f((2,3,5,1))=50+40=90

b=3 f(3, j(1,4,3))=

+f((3,5,2,1))=24+14=38

b=5 f(5, j(1,4,5))=

+f((5,3,2,1))=6+27=33

(4,5,3,2,1) – наилучшее продолжение

(1,5) S={2,3,4}

b=2 f(2, j(1,5,2))=

+f((2,3,4,1))=8+32=40

b=3 f(3, j(1,5,3))=

+f((3,2,4,1))=7+54=61

b=4 f(4, j(1,5,4))=

+f((4,3,2,1))=10+44=54

(5,2,3,4,1) – наилучшее продолжение

Рассмотрим все частичные решения длины k-5: мы вышли из первого города и можем направиться в любой из четырёх.

b=2 f(1, j(1,2))=

+f((2,3,5,4,1))=25+37=62

b=3 f(1, j(1,3))=

+f((3,4,5,2,1))=40+25=65

b=4 f(1, j(1,4))=

+f((4,5,3,2,1))=31+33=64

b=5 f(1, j(1,5))=

+f((5,2,3,4,1))=27+40=67

1-2-3-5-4-1 –маршрут с минимальной стоимостью.

Результаты решения представим в виде таблицы:

i₄=2

j=(2,1)

f=5

i₄=5

j=(3,1)

f=19

i₄=4

j=(4,1)

f=9

i₄=3

j=(5,1)

f=22

i₃=2(3,4)

j=(2,5,1)

f=47

i₃=2(3,5)

j=(2,4,1)

f=39

i₃=2(4,5)

j=(2,3,1)

f=36

i₃=3(2,4)

j=3,5,1)

f=23

i₃=3(2,5)

j=(3,4,1)

f=15

i₃=3(4,5)

j=(3,2,1)

f=20

i₃=4(2,3)

j=(4,5,1)

f=28

i₃=4(2,5)

j=(4,3,1)

f=24

i₃=4(3,5)

j=(4,2,1)

f=55

i₃=5(2,3)

j=(5,4,1)

f=19

i₃=5(2,4)

j=(5,3,1)

f=26

i₃=5(3,4)

j=(5,2,1)

f=13

(1,2,3)

(3,5,4,1)

f=20

(1,2,4)

(4,5,3,1)

f=32

(1,2,5)

(5,3,4,1)

f=22

(1,3,2)

(2,5,4,1)

f=44

(1,3,4)

(4,5,2,1)

f=19

(1,3,5)

(5,2,4,1)

f=47

(1,4,2)

(2,3,5,1)

f=40

(1,4,3)

(3,5,2,1)

f=14

(1,4,5)

(5,3,2,1)

f=27

(1,5,2)

(2,3,4,1)

f=32

(1,5,3)

(3,2,4,1)

f=54

(1,5,4)

(4,3,2,1)

f=44

(1,2)

(2,3,5,4,1)

f=37

(1,3)

(3,4,5,2,1)

f=25

(1,4)

(4,5,3,2,1)

f=33

(1,5)

(5,2,3,4,1)

f=40

(1,2,3,5,4,1)

f=62

(1,3,4,5,2,1)

f=65

(1,4,5,3,2,1)

f=64

(1,5,2,3,4,1)

f=67

© Усі права захищені
написати до нас