Дискретно-непрерывная математика (стр. 52 )

если путь проходит через i (в сетевом графике τi — продолжительность работы i, в нашей интерпретации — время пребывания туриста в пункте i); здесь перемещениями между пунктами мы пренебрегаем (турист считает только то время, в течение которого он знакомится с достопримечательностями).

Два пути σk и σl, которые приводят в один и тот же пункт (в наших обозначениях іk (σk) = іl (σl)), сравнимы. Правило доминирования естественно вытекает из того, что можно говорить о критическом пути для каждого пункта, так как можно построить для каждого пункта самый длинный путь, который соединяет его с начальным пунктом. Заметим, что каждая часть критического пути есть критический путь в том смысле, что лежащие на критическом пути пункты i и j также соединены «наиболее длинно» и не существует другого пути, который соединяет эти пункты «более длинным образом».

Во многих задачах поска «наилучших» траекторий путь обладает свойством оптимальности (удовлетворяет принципу оптимальности). В таких случаях правила доминирования находятся легко и естественно

Утверждение (правило доминирования). Из двух сравнимых путей σk и σl «лучше» тот, у которого больше длина пути.

Это утверждение следует из предыдущего замечания.

В задачах подобного типа — поиска некоторого одного пути на графе обычно обходятся без построения порфириана. Такая возможность обеспечивается приемом расстановки меток на графе, т. е. прокладыванием путей σk на самом сетевом графике (маршруте туриста) — например, красным карандашом сверху по плану, вычерченному предварительно черной тушью.

Соединим предварительно с исходным пунктом те вершины сетевого графика, в которые приводят пути от исходного пункта и только от него. Отметим эти пункты j, т. е. наведем дополнительно на графике пути, которые соединяют их с исходным пунктом, и проставим возле них метку r(j) — пройденное расстояние, длину пути.

Пусть теперь отмечены какие-то пункты. Найдем пункт i, в который приводят стрелки только из отмеченных метками r(j) пунктов j. Построим теперь

r(j) + τ(i) (5.80)

и выберем среди них максимальное. Тот пункт j, который дает максимальное (5.80), соединим с пунктом i, т. е. наведем стрелку, соединяющую j с i, и отметим i величиной (5.80).

Решение закончится, когда конечный пункт станет отмеченным. Рис. 5.37 приводит только что описанный алгоритм.

Рис. 5.37. Схема поиска критического пути методом расстановки

меток.

1. Подготовка информации о графе и значениях r(i). 2. «Отмечаем» исходную вершину: полагаем для нее r(j)=0, ставим «метку» i =0. 3. Ищем вершину j, в которую приходят стрелки только от отмеченных вершин. 4. Вычисляем для этой вершины r(i) + τj, находим i0, для которого эта сумма максимальна, отмечаем вершину j: полагаем для нее r(j)= r(i0)+ τіj и ставим «метку» i0. 5. Проверяем: конечная вершина отмечена? 6. Решение найдено, остается по меткам восстановить критический путь.

5.19. Отсеивание вариантов. Ветви и границы

1. Схема «ветвей и границ». Представьте, что каким-то образом нам удается оценить для каждого σk, что среди продолжений σk можно получить в лучшем случае σ2п с некоторым F(σ2п). Такую оценку F(σ2п) мы будем называть «обещанием» и обозначать через b(σk).

Оставим пока в стороне вопрос, как получено такое «обещание» (насколько можно ему верить).

Рассмотрим следующую идею отсеивания вариантов в процессе построения порфириана.

Будем подвергать ветвлению σk с наиболее удобным (т. е. наибольшим в случае задачи максимизации, наименьшим при минимизации) «обещанием».

Это правило ветвления будем использовать до тех пор, пока не получим некоторое (окончательное) σ0п. Вычислим F(σ0п). Теперь можно отсеять (запретить ветвление) все те σk, для которых b(σk )≥F(σ0п) — в задаче минимизации (или b(σk )≤F(σ0п) в задаче минимизации).

Поиск σп ( улучшающих σ0п) по описанной схеме продолжается до тех пор, пока не останется ни одного σk, который бы «предлагал лучшее» (чем у уже найденных σп) «обещание».

Таким образом, в схеме «ветвей и границ» (после умения строить порфириан) главное — это умение оценивать b(σk) для каждого σk.

Очевидно, при этом для каждого σk необходимо сформулировать некоторую вспомогательную задачу (вычисление b(σk)) и, конечно, более простую, чем исходная (поиск наилучшего σп среди продолжений σk).

Чаще всего вспомогательная задача формулируется как некоторое (естественное) упрощение исходной задачи.

Примером продуктивности этой рекомендации может служить следующая задача.

2. Задача о рюкзаке. Собираясь в поход, вы хотели бы взять п предметов, каждый предмет i весом аі и «ценностью» в походе сі.

Вы можете взять предметов с собой по весу не больше А (предполагается, что ai> A— иначе не было бы задачи!). Какие предметы взять?

Решение задачи можно представить последовательностью

Σп = х1, х2, . . ., хп ,

где

Таким образом, нам надо найти такую последовательность σп, что на ней

и достигается максимум хі сі.

Задача о рюкзаке, как задача теории расписаний, возникает, когда нужно определить перечень операций, которые следует включить в план выполнения в некоторый временнóй интервал (пятидневку, неделю) .

Построение вспомогательной задачи в этом случае осуществляется довольно просто и поучительно.

В исходной задаче о рюкзаке xі может принимать значение только 0 и 1. Отказ от этого предположения и приводит к вспомогательной, легко решаемой задаче:

0≤ xі ≤1.

Физически это означает, что грузы наши «сыпучие» и мы можем взять любую часть груза.

Решение задачи в случае сыпучих грузов очевидно.

Найдем величину , и пусть грузы благоустроены по убыванию , т. е. по величине «ценности» единицы веса груза,

Тогда необходимо брать груз, начиная с первого, до тех пор, пока мы не «засипем» рюкзак до веса А. Другими словами:

а) если а1 ≤А, то х1 = 1;

б) если

то хk = 1;

в) если

то

и xi = 0, i>k+1.

Решение задачи

в случае «сыпучих» грузов и может служить искомой оценкой — «обещанием» — значений F(σг), ибо , как нетрудно видеть,

F(σп)≤C(σп).

Построение порфириана достигается очевидным способом. Множество всех возможных σп разбивается на два: первое с х1 = 0, вторая с х1=1. Множества второго уровня σ2 есть разбиения полученных множеств в зависимости от того, х2 = 0 или х2 = 1 и т. п.

На рис. 5.38 представленная общая схема решения задачи о рюкзаке.

Рис. 5.38. Схема решения задачи о рюкзаке.

Множество возможных решений обозначим через σ0. Положим рекорд f* равным нулю. (Смысл рекорда f устанавливается в блоке 8.) Формулируем вспомогательную задачу (0≤χi ≤1), находим σ0∆(σ0). 2. Проверяем, есть ли в построенном фрагменте «висячие> вершины σk∆(σk). («Висячие» - те, в которых нет еще «продолжений», они же - мажоранты порфириана.) 3. Операция выбора: выбираем «висячую» вершину σk с ∆(σk)>f и при этом с наибольшим ∆(σk). Можно выбирать σk с ∆(σk)>f (при этом с наибольшим k) - это определит более эффективный «челночный» вариант схемы решения. 4. Операция ветвления: добавляем к порфириану две вершины: σ′k+1=σk,0 и σ′′k+1=σk,0 , вычеркиваем σ′′k+1, если ею определяется решение, недопустимое неравенством ∑аіγi <А (нарушает это условие). 5. Проверяем, σ′k+1 и σ′′k+1 – не являются ли они полными решениями, т. е. k + l=n? 6. Вычисляем для σ′k+1 и σ′′k+1 величину k + l=п. 7. Проверяем, найдется ли f (σk+1) > f. 8. Полагаем новое f равным максимальному из таких