Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [ 37 ] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

*L3.2.4. Сравнение эвристических алгоритмов (проверка). Проведите сравнительную проверку алгоритма GTS2 с вашим алгоритмом из упр. 3.2.3. Прогоните оба алгоритма на одних и тех же тестовых задачах. Сравните найденные стоимости туров, а также соответствующие величины математического ожидания и дисперсии времени работы.


L = (7,9, 7,1,6,2,4,3) Nff=3 а


L= {7,9,7,6,2,4,3) Nf=4

Рис. 3.2.8. Аномалия при использовании эвристического алгоритма первого попавшегося размещения; упаковка становится хуже, когда убран предмет.

*3.2.5. Эвристический алгоритм для задачи об укладке рюкзака (разработка, анализ). Имеется рюкзак объема V и неограниченный запас каждого из N различных видов предметов. Каждый предмет вида i имеет известные объем у,- и стоимость т,-, i=l, ... , Л. В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы общая стоимость упакованных предметов была наибольшей, а их общий объем не превосходил V. Форма предметов в задаче не рассматривается.

Разработайте и проанализируйте грубый эвристический алгоритм для задачи об упаковке рюкзака.

**3.2.6. Задача покрытия множества (разработка, анализ). S - множество элементов. §={Fi} для любого 1=1, . . . , п-это множество из п множеств, каждое из которых состоит из элементов S. Задача состоит в нахождении наименьшего числа множеств из , таких, что объединение этих множеств содержит все элементы множества S. Эта задача известна как задача минимального покрытия множества.



Разработайте эвристический алгоритм, дающий возможное решение этой задачи. Проанй-тизируйте работу, необходимую. для реализации этого эвристического алгоритма.

*3.2.7. Тур коня (модель, разработка). Снова рассмотрим эвристический алгоритм поиска тура для коня из разд. 2.1. Разработайте другой эвристический алгоритм для этой же задачи.

3.3. Программирование с отходом назад

Метод разработки алгоритма, известный как программирование с отходом назад, можно описать как организованный исчерпывающий поиск, который часто позволяет избежать исследования всех возможностей. Этот метод особенно удобен для решения задач, требующих проверки потенциально большого, но конечного числа решений.

Задача о велосипедном замке

В качестве примера рассмотрим комбинационный замок для велосипеда, состоящий из набора N переключателей, каждый из которых может быть в положении «вкл» или «выкл». Замок открывается только при одном наборе положений переключателей, из которых не менее \ N/2J (целая часть от N/2) находятся в положении «вкл». Пред1ю-ложим, что мы забыли эту комбинацию, а нам надо отпереть замок. Предположим также, что мы готовы перепробовать (если необходимо) все комбинации. Нам нужен алгоритм для систематического генерирования этих комбинаций. Если проигнорировать условие \ N/2J, то для замка существует 2 возможных комбинаций. (Покажите, что это так.) Неплохие шансы иайти правильную комбинацию могут быть при N10. Однако условие \ N/2J позволит отбросить (или лучше не генерировать) многие комбинации.

Промоделируем каждую возможную комбинацию вектором из нулей и единиц. На i-м месте будет 1, если г-й переключатель находится в положении «вкл», и О, если i-й переключатель -• в положении «выкл». Множество всех возможных Л-векторов хорошо моделируется с помощью двоичного дерева (см. разд. 2.2). Каждая вершина k-ro Уровня этого дерева будет соответствовать определенному набору первых k компонент yV-вектора. Две ветви, идущие вниз из вершины этого уровня, соответствуют двум возможным значениям (&+1)-й компоненты в /V-векторе. У дерева будет уровней. Рис. 3.3.1 на примере N=4 поясняет основную конструкцшс).

Условие, заключающееся в том, что число переключателей в положении «вкл» должно быть не меньше [. N/2 J , позволяет нам не образовывать части дерева, которые не могут привести к правильной комбинации. Например, рассмотрим вершину 00 на рис. 3.3.1. Так как правая ветвь (к ООО) не может привести к допустимой комбинации, нет нужды ее формировать. Если какие-то вершины, следующие за рассматриваемой вершиной, не удовлетворяют ограничению задачи, то эти вершины не надо рассматривать. В данном случае никакие из



вершин, находящихся внутри пунктирных линий, не нужно исследовать и даже формировать.

Теперь, воспользовавшись этой моделью двоичного дерева, можно изложить процедуру отхода назад для образования только тех комбинаций, в которых по крайней мере L /2 J переключателей находятся в положении «вкл». Алгоритм сводится к пересечению дерева.

Корень


УррВвиь О

Уро8т 1

Уровень 3

11111110 1101 1100 1011 1010 iooi\iooo)oiii о110 0101о1оо)оо1Л.5010ооо1оооо/ УрВень Рис. 3.3.1. Двоичное дерево, представляющее iV-векторы из нулей и единиц.

Двигаемся вниз по дереву, придерживаясь левой ветви, до тех пор, пока это возможно. Достигнув конечной вершины, опробуем соответствующую комбинацию. Если она не подходит, поднимаемся на один уровень и проверяем, можем ли мы спуститься опять по другой ветви. Если это возможно, берем самую левую из неисследованных ветвей. Если нет, отходим вверх еще на один уровень и пытаемся спуститься из этой вершины. Перед спуском проверяем, можно ли удовлетворить условие об Л/2 J включенных переключателях в последующих вершинах. В ситуации, изображенной на рис. 3.3.1, этот алгоритм просмотрит следующую последовательность вершин:

11 111

1111 111

1110

111 И

Проверка этой комбинации. Отход, так как 1111 - конечная вершина. Спуск по единственной непросмотренной ветви вниз, проверка этой комбинации. Снова отход.

Отход дальше, так как из 111 все ветви просмотрены.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [ 37 ] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0012