Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1716


2.2. полный перебор с отсечением вариантов

2.2.1. Задача о рюкзаке (перебор вариантов)

Постановка задачи. В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа i имеет вес wi и стоимость vi (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через ki, тогда требуется максимизировать v1 × k1+v2 × k2+...+vn × kn при ограничениях w1 × k1+w2 × k2+...+wn × kn £ W, где ki – целые (0 £ ki £ [W/wi]), квадратные скобки означают целую часть числа.

Рассмотрим простой переборный вариант решения задачи, работоспособный только для небольших значений n (определить, для каких?). Итак, данные:

 

      Сonst MaxN= /* максимальная размерность */;

      Int n,w:;/*количество предметов, максимальный вес */

      Int Weight,Price[MaxN] ;/*вес, стоимость предметов*/

      Int Best,Now[MaxN]; /*наилучшее, текущее решения */

LongInt    MaxPrice; /*наибольшая стоимость */

 

Решение, его основная часть – процедура перебора:

      Rec1(k,w,st);

/*k – порядковый номер группы предметов, w – вес, который следует набрать из оставшихся предметов, st – стоимость текущего решения*/

       {

      1    if ((k>n) и (st > MaxPrice)) { /*найдено решение*/

2                                             Best← Now; MaxPrice ← st; }

      3    else if (k<=n )

                   for( i←0; i ≤ w div Weight[k] ; i← i+1) {

                   Now[k]← i;

                   Rec1(k+1,W–i * Weight[k],st+i*Price[k]);

                   };

       };

 

Инициализация переменных, вывод решения и вызывающая часть (Rec1(1,w,0)) очевидны. В данном алгоритме отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета. В блоке предварительной обработки целесообразно найти какое-то решение. Лучше если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. 

2.2.2. Задача о коммивояжере (перебор вариантов)

Постановка задачи. Классическая формулировка задачи известна уже более 200 лет: имеются n городов, расстояния между которыми заданы, и из каждого города можно попасть во все остальные города. Коммивояжеру необходимо выйти из какого-то города, посетить остальные n – 1 городов по одному разу и вернуться  в исходный город. При этом маршрут коммивояжера должен быть минимальной  длины или стоимости.

Задача коммивояжера принадлежит классу NP-полных, т. е. неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n – 1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.

 

Формальная модель данной задачи. Математической моделью задачи о коммивояжере является полный, взвешенный орграф, который может быть задан матрицей расстояний. Поиск пути коммивояжера – это поиск гамильтонова цикла в графе с минимальной стоимостью. Так как, граф полный, решение всегда существует.

 

Перебор вариантов. Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данном методе.

 

Структуры данных. Const Max=100;

int A[Max][Max] /*матрица расстояний между городами*/

byte B[Max][Max] ;/*Вспомогательный массив, элементы каждой строки матрицы сортируются в порядке возрастания, но сами элементы не переставляются, а изменяются в матрице В номера столбцов матрицы А */

      byte Way, BestWay[Max] ;/*Хранится текущее решение и

                                        лучшее решение*/

      int Nnew[1..Max];/*Значение элемента массива 0 говорит о том, что в соответствующем городе коммивояжер уже побывал */

int BestCost;/*Стоимость лучшего решения*/

 

Идея решения. Пусть мы находимся в городе с номером v.

      Шаг 1. Если расстояние (стоимость), пройденное коммивояжером до города с номером v, не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из данной ветви дерева перебора.

      Шаг 2. Если рассматривается последний город маршрута (осталось только вернуться в первый город), то следует сравнить стоимость найденного нового решения со стоимостью лучшего, из ранее найденных. Если результат сравнения положительный, т.е. нашли лучшее решение, то значения BestCost и BestWay следует изменить (запомнить лучшее) и выйти из этой ветви дерева перебора.

      Шаг 3. Пометить город с номером v как рассмотренный, записать этот номер по значению Count в массив Way.

      Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то повторить данные шаги алгоритма с измененными значениями v, Count, Cost, иначе – на следующий шаг.

      Шаг 5. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора.

Пример. Для задачи из шести городов. На рис. 2.3 приведены матрицы А и В. Матрица В отражает состояние матрицы А после сортировки элементов каждой строки матрицы А. (Напомним, что в матрице В записываются не элементы матрицы А, а – номера столбцов сортируемых элементов.)

 

Примечание. Можно использовать любой из методов сортировок. Символом @ обозначено бесконечное расстояние.

 

@

 27

43

16

30

26

7

@

16

1

30

25

20

13

@

35

5

0

21

16

25

@

18

18

12

46

27

48

@

5

23

5

5

9

5

@

4

6

2

5

3

1

 

4

1

3

6

5

2

 

6

5

2

1

4

3

 

2

5

6

1

3

4

 

6

1

3

2

4

5

 

2

3

5

4

1

6

 

                                А                                                            B                        

 

Рис. 2.3

 

                     A                                                       B

 

3

2

4

1

 

3

1

4

2

 

4

2

1

3

 

1

2

3

4

 

 

@

4

0

9

 

  5

@

0

5

 

6

4

@

1

 

0

2

6

@

 

Рис. 2.4

Прежде чем перейти к обсуждению алгоритма, целесообразно разобрать этот перебор на примере. В рассмотренном примере размерность задачи уменьшена. Коммивояжер должен посетить четыре города. На рис. 2.4 даны матрицы А и В для этого примера и дерево решений, где указан порядок просмотра городов. В кружках – номера городов, рядом с кружками – суммарная стоимость проезда до этого города из первого.

 

Алгоритм решения задачи  коммивояжера

 

Solve(v,Count,Cost);

/*v – номер текущего города; Count – счетчик числа пройденных городов; Cost – стоимость текущего решения*/

 {

1        if (Cost >BestCost)  exit;/*Стоимость текущего решения превышает стоимость лучшего из ранее полученных решений.*/

2        if (Count равно N) { Cost← Cost+A[v,1];Way[N]← v;/* Последний город пути.      Достраиваем  решение и сравниваем его с лучшим решением из ранее полученных решений.*/

3         if( Cost < BestCost) {

4                                               BestCost← Cost; BestWay← Way;

} /*Запоминаем лучшее решение.*/

5                 exit;

             };

6    Nnew[v]← 0;Way[Count]← v;/*Город с номером v пройден, записываем его номер в путь коммивояжера*/

7      for( i←1; I ≤ N; i← i+1)

8      if (Nnew[B[v,i]] )

9             Solve(B[v,i], Count+1,Cost+A[v,B[v,i]]); /*Поиск города,

        в который коммивояжер может пойти из города с номером v*/

                Nnew[v] ← 1; /*Возвращаем город с номером v в число                 не пройденных*/

 };

Первый вызов – Solve(1,1,0).

 

Проверить работоспособность этого алгоритма можно на следующем примере (матрица А дана на рис. 2.5). Решение имеет вид 1 8 9 2 5 10 6 7 4 3 1, его стоимость 158.

Оцените время работы программы. Если у вас мощный компьютер, то создайте матрицу А[1..50,1..50] и попытайтесь найти наилучшее решение с помощью разобранного метода.

@

32

19

33

22

41

18

15

16

31

32

@

51

58

27

42

35

18

17

34

9

51

@

23

35

49

26

34

35

41

33

58

23

@

33

37

23

46

46

32

22

27

35

33

@

19

10

23

23

9

41

42

49

37

19

@

24

42

42

10

18

35

26

23

10

24

@

25

25

14

15

18

34

46

23

42