Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Филатов_Отчет5_Системный_Анализ

.doc
Скачиваний:
11
Добавлен:
10.12.2018
Размер:
451.58 Кб
Скачать

Наибольшая сумма констант приведения равна 9 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(2*,1*) =126 + 9 =135

Исключение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d21 заменяем на ∞, для исключения образования негамильтонова цикла. (ПОМЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕТКА)

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

i j

2

3

5

6

 

1

ура

0

8

5

3

5

ура

1

0

 0

4

0

11

ура

33

 0

6

12

0

0

ура

 

 0

 0

 0

 

Нижняя граница подмножества (3,4) равна:

HОвал 10(2,1) = 126 + 0 = 126

(*5,*4)

(5,4)

Прямая со стрелкой 14Прямая со стрелкой 13

Овал 16

Овал 15

(2,1)

Прямая со стрелкой 20

(*2,*1)

Прямая со стрелкой 18

Овал 17Овал 19

Шаг №3

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на ∞ и определяем для них сумму образовавшихся констант приведения.

i j

2

3

5

6

1

ура

0

8

5

3

5

ура

1

0

4

0

11

ура

33

6

12

0

0

ура

i j

2

3

5

6

1

5

3

6

4

16

6

0

1

H(4*,2*) = 126+16=142

i j

3

5

6

1

0

ура

5

0

3

ура

1

0

0

6

0

0

ура

0

0

0

0

H(4,2) = 126

Овал 23

(*5,*4)

(5,4)

Прямая со стрелкой 27Прямая со стрелкой 26

Овал 28

Овал 29

(2,1)

Прямая со стрелкой 480

(*2,*1)

Прямая со стрелкой 481

Овал 483Овал 482

Прямая со стрелкой 487Прямая со стрелкой 488

(*4,*2)

(4,2)

Овал 484Овал 485

Шаг №4

i j

3

5

6

1

0

ура

5

3

ура

1

0

6

0

0

ура

i j

3

5

6

1

5

3

6

6

0

1

H = (3*,6*) =126+6=132

i j

3

5

1

0

ура

6

ура

0

H = (3,6) = 126

Остались переходы 1-3, 6-5.

Путь: 5-4-2-1-3-6-5

Длина пути 126.

H(4,2) = 126

Овал 491

(*5,*4)

(5,4)

Прямая со стрелкой 495Прямая со стрелкой 494

Овал 496

Овал 497

(2,1)

Прямая со стрелкой 500

(*2,*1)

Прямая со стрелкой 501

Овал 503Овал 502

Прямая со стрелкой 507Прямая со стрелкой 506

(*4,*2)

(4,2)

Овал 508Овал 509

(*3,*6)

(3,6)

Прямая со стрелкой 513Прямая со стрелкой 512

Овал 510Овал 511

Ответ: Кротчайший маршрут: 5 4 2 1 3 6 5

Длина маршрута 126

2. Жадный метод

i j

1

2

3

4

5

6

1

9

8

49

47

13

2

7

15

40

46

22

3

8

12

55

39

7

4

35

29

40

49

62

5

37

34

35

39

37

6

12

17

5

44

36

 

 

 

 

 

 

 

минимальный элемент 5.

Переходы:

из 6 в 3 5

из 3 в 1 8

из 1 во 2 9

из 2 в 4 40

из 4 в 5 49

из 5 в 6 37

Итоговый маршрут: 6-3-1-2-4-5-6. Длина равна 148

Попытаемся еще укоротить маршрут, дополнив данный метод “методом локальных улучшений”

Поочередно меняем местами пары элементов:

6-3-1-2-4-5-6 = 148

i j

1

2

3

4

5

6

1

9

8

49

47

13

2

7

15

40

46

22

3

8

12

55

39

7

4

35

29

40

49

62

5

37

34

35

39

37

6

12

17

5

44

36

 

 

 

 

 

 

 

Нач. путь

6

1

3

2

4

5

6

Сумма

Значения

12

8

12

40

49

37

 

158

Путь

6

3

1

2

4

5

6

 

Значения

5

8

9

40

49

37

 

148

Путь

6

1

2

3

4

5

6

 

Значения

12

9

15

55

49

37

 

177

Путь

6

1

3

4

2

5

6

 

Значения

12

8

55

29

46

37

 

187

Путь

6

1

3

2

5

4

6

 

Значения

12

8

12

46

39

62

 

179

Путь

6

1

3

2

4

6

5

 

Значения

12

8

12

40

62

36

 

170

В обрат

6

5

4

2

3

1

6

 

Значения

36

39

29

15

8

13

 

140

Нач. путь

6

5

4

2

3

1

6

Сумма

Значения

36

39

29

15

8

13

 

140

Путь

6

4

5

2

3

1

6

 

Значения

44

49

34

15

8

13

 

163

Путь

6

5

2

4

3

1

6

 

Значения

36

34

40

40

8

13

 

171

Путь

6

5

4

3

2

1

6

 

Значения

36

39

40

12

7

13

 

147

Путь

6

5

4

2

1

3

6

 

Значения

36

39

29

7

8

7

 

126

Путь

6

5

4

2

3

6

1

 

Значения

36

39

29

15

7

12

 

138

В обрат

6

1

3

2

4

5

6

 

Значения

12

8

12

40

49

37

 

158