Методические указания по выполнению курсовых работ по курсу (стр. 4 из 6)
- Метод ветвей и границ
Применение данного метода к задаче коммивояжера, будет отличаться принципом, по которому осуществляется ветвление, и методами получения верхней и нижней оценок. В данном случае будет рассмотрено не дихотомическое ветвление, а полный перебор добавляемых вершин. В качестве начальной вершины ветвления можно выбрать произвольную (например, первую).
Нижняя оценка может быть получена следующим образом:
 | (10) |
Верхняя – как решение задачи методом ближайшего соседа (алгоритм см. выше).
Шаг 1. Производим ветвление от вершины
таким образом, чтобы не производить циклов.Шаг 2. Для каждой ветки, соответствующей добавлению в маршрут ребра (
вычисляем верхнюю и нижнюю оценку. 
.Шаг 3. Если в существует направление
, нижняя оценка в котором больше верхней в направлении 
: 
, то направление 
можно исключить из дальнейшего рассмотрения.Шаг 4. Повторяем шаги 1-3 до полного построения маршрута.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать матрицу переходов. Вершины ветвления помечать соответствующим номером добавляемой в решение переменной
. Для каждой вершины ветвления отображать верхнюю и нижнюю оценки (эти оценки можно расставлять не у вершины, а у ребра) . Отбрасываемые ветви помечать цветом.Режим обучения:
Пользователь помечает вершины ветвления и отбрасывает неперспективные ветки. Если ветвление идет в не правильном направлении, то пользователь предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.
- Метод динамического программирования
Обозначим через
- длину пути, проходящего по всем вершинам множества 
, с началом в вершине с номером i и концом в вершине с номером 1. Рекуррентное соотношение для задачи коммивояжера выглядит следующим образом:  , | (11) |
При граничных условиях:
 | (12) |
Значение, полученное в результате вычисления соотношения (11), является оптимальным решением исходной задачи.
Алгоритм состоит в последовательном вычислении соотношений (11), процесс поиска решения отображается в виде дерева.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать задачу. Вершины ветвления помечать соответствующим номером добавляемой в решение переменной
. Помечать ребра значениями 
или 
, если достигнуты граничные условия. Ветви с наименьшей суммарной длиной помечать цветом.Режим обучения:
Пользователь помечает вершины ветвления и расставляет расстояния на ребрах. Если метки расставляются не правильно или выбрана не правильная вершина ветвления, то пользователь предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.
4. Задача построения максимального потока
Постановка задачи
Дана сеть G(V, E) с источником s и стоком t. Каждое ребро имеет заданную пропускную способность
. В этой сети необходимо найти максимальное значение потока, проходящего из источника s в сток t. Задаче о максимальном потоке соответствует задаче о минимальном разрезе. В задаче о минимальном разрезе необходимо найти такой разрез графа G(V, E): 
, имеющий минимальное значение суммы пропускных способностей дуг соединяющих 
и 
. Величина максимального потока равна величине минимального разреза (теорему, доказывающую это утверждение, можно найти в работе [2]).Методы решения
Метод Форда-Фалкерсона (иногда он называется методом меток) является первым из предложенных методов поиска максимального потока и базисным для многих алгоритмов, предложенных позднее. Более подробно с данным методом можно ознакомиться в работах [2, 3].
- Алгоритм Форда-Фалкерсона
Из источника осуществляется поиск до тех пор, пока не будет достигнут сток. По найденному пути осуществляется насыщение потока, величина потока из вершины
в вершину 
обозначается как 
. В ходе алгоритма каждой вершине 
присваивается метка, состоящая из двух частей: смежная вершина, с указанием направления потока, и поток через вершину. При этом если поток идет из вершины в вершину , то метка имеет вид [ 
], иначе [ 
].Шаг 1. Присвоить вершине
метку [0, 
]. Обозначим текущую вершину 
.Шаг 2. Берем произвольную помеченную вершину
, рассматриваем все не помеченные смежные с вершины 
.Если
, 
, метка [+ 
].Иначе, если
, 
, метка [ 
].Шаг 3. Повторяем шаг 2 пока не будут выполнены следующие условия:
Если помечена вершина
, то переходим на Шаг 4.Если вершина
не помечена и меток больше нельзя расставить, то выход.Шаг 4. Пользуясь метками, производим насыщение ребер, начиная с вершины
.Если пометка вершины
имеет вид [+ 
], то 
.Если пометка вершины
имеет вид [ 
], то 
.Переходим в вершину
: 
.Повторяем шаг 4 пока не достигнем источника:
.Шаг 5. Переходим на шаг 1.
Замечание: полученные на последней итерации пометки позволяют определить минимальный разрез. В него входят ребра, соединяющие помеченные и непомеченные вершины.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины отображаются метки [
], для ребер отображается пропускная способность и проходящий поток 
. Насыщенные ребра выделяются цветом.