ГУАП
КАФЕДРА №41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
ассистент |
|
|
|
Б.К. Акопян |
|
|
|
|
|
|
|
|
|
|
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №5
ПРИМЕНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
по курсу: Прикладные методы оптимизации
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. №
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2022
Цель работы
Изучение метода ветвей и границ применительно к решению задачи коммивояжера.
Индивидуальный вариант
Индивидуальный вариант номер 10 в соответствии с таблицей 1.
Таблица 1 – Индивидуальный вариант задания
Оценка жадным алгоритмом в качестве произвольного маршрута:
X0 = {(1,2); (2,3); (3,4); (4,1)}
Тогда F(X0) = 7 + 1 + 1 + 10 = 19
Ход работы
1.Определили значения α и β, дополнить ими исходную матрицу расстояний
(Таблица 1).
1 = 2, 2 = 1, 3 = 1, 4 = 51 = 2 2 = 3 3 = 0 4 = 0
N |
1 |
|
2 |
3 |
4 |
di |
|
|
|
|
|
|
|
1 |
|
- |
7 |
4 |
2 |
2 |
|
|
|
|
|
|
|
2 |
|
3 |
- |
1 |
8 |
1 |
|
|
|
|
|
|
|
3 |
|
5 |
7 |
- |
1 |
1 |
|
|
|
|
|
|
|
4 |
|
10 |
8 |
5 |
- |
5 |
|
|
|
|
|
|
|
dj |
|
2 |
3 |
0 |
0 |
0 |
|
|
|
|
|
|
|
2.Вычислили нижнюю границу на всем множестве допустимых решений D.
Вычислить верхнюю оценку на рассматриваемом множестве допустимых решений жадным алгоритмом. При необходимости обновить рекорд х0.
H(D)=H ({1}, )= 2+1+1+5+2+3+0+0 = 14
2
3.Осуществить ветвление имеющегося множества на подмножества.
I= {1,2}, J= и I= {1}, J= {2}
4. Для каждого из получаемых подмножеств повторяем, при необходимости отсекая множества согласно правому правилу отсечений, до тех пор, пока не будет найдено оптимальное решение
Первое ветвление
|
1 |
|
2 |
|
3 |
|
4 |
di |
|
|
|
|
|
|
|
|
|
1 |
|
- |
|
2 |
|
2 |
0 (2) |
2 |
|
|
|
|
|
|
|
|
|
2 |
|
0 (2) |
|
- |
|
0 (0) |
7 |
0 |
|
|
|
|
|
|
|
|
|
3 |
|
2 |
|
3 |
|
- |
0 (2) |
2 |
|
|
|
|
|
|
|
|
|
4 |
|
3 |
|
0 (2) |
|
0 (0) |
- |
0 |
|
|
|
|
|
|
|
|
|
dj |
|
2 |
|
2 |
|
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
d(1,4) = 2 + 0 = 2;
d(2,1) = 0 + 2 = 2;
d(2,3) = 0 + 0 = 0;
d(3,4) = 2 + 0 = 2;
d(4,2) = 0 + 2 = 2;
d(4,3) = 0 + 0 = 0
Наибольшая сумма констант приведения равна (2 + 0) = 2 для ребра (1,4),
следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Исключение ребра
|
1 |
|
2 |
3 |
4 |
di |
|
|
|
|
|
|
|
1 |
|
- |
2 |
2 |
- |
2 |
|
|
|
|
|
|
|
2 |
|
0 |
- |
0 |
7 |
0 |
|
|
|
|
|
|
|
3 |
|
2 |
3 |
- |
0 |
0 |
|
|
|
|
|
|
|
4 |
|
3 |
0 |
0 |
- |
0 |
|
|
|
|
|
|
|
dj |
|
0 |
0 |
0 |
0 |
2 |
|
|
|
|
|
|
|
H(1*,4*) = 14 + 2 = 16 |
|
|
|
|
||
Включение ребра |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
3 |
di |
|
|
|
|
|
|
|
|
2 |
|
0 |
- |
0 |
0 |
|
|
|
|
|
|
|
|
3 |
|
2 |
3 |
- |
0 |
|
|
|
|
|
|
|
|
4 |
|
3 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
dj |
|
0 |
0 |
0 |
2 |
|
|
|
|
|
|
|
|
H(1,4) = 14 + 2 = 16 ≤ 16
3
Поскольку нижние границы подмножества (1,4) и подмножества (1*,4*) равны, то
ребро (1,4) включаем в маршрут с новой границей H = 16
Второе ветвление
|
1 |
|
2 |
|
3 |
di |
|
|
|
|
|
|
|
2 |
|
0 (0) |
|
- |
0 (0) |
0 |
|
|
|
|
|
|
|
3 |
|
0 (1) |
|
1 |
- |
1 |
|
|
|
|
|
|
|
4 |
|
- |
|
0 (1) |
0 (0) |
0 |
|
|
|
|
|
|
|
dj |
|
0 |
|
1 |
0 |
0 |
|
|
|
|
|
|
|
d(2,1) = 0 + 0 = 0;
d(2,3) = 0 + 0 = 0;
d(3,1) = 1 + 0 = 1;
d(4,2) = 0 + 1 = 1;
d(4,3) = 0 + 0 = 0
Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (3,1),
следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).
Исключение ребра
|
1 |
|
2 |
|
3 |
|
di |
|
|
|
|
|
|
|
|
2 |
|
0 |
|
- |
|
0 |
0 |
|
|
|
|
|
|
|
|
3 |
|
- |
|
1 |
|
- |
1 |
|
|
|
|
|
|
|
|
4 |
|
- |
|
0 |
|
0 |
0 |
|
|
|
|
|
|
|
|
dj |
|
0 |
|
0 |
|
0 |
1 |
|
|
|
|
|
|
|
|
H(3*,1*) = 16 + 1 = 17 |
|
|
|
|
|
|
|
Включение ребра |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
2 |
|
3 |
|
di |
|
|
|
|
|
|
|
|
|
|
2 |
|
- |
|
0 |
|
0 |
|
|
|
|
|
|
|
|
|
4 |
|
0 |
|
0 |
|
0 |
|
|
|
|
|
|
|
|
|
dj |
|
0 |
|
0 |
|
0 |
|
|
|
|
|
|
|
|
|
H(3,1) = 16 + 0 = 16 ≤ 17 |
|
|
|
|
|
|
|
Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества
(3*,1*), то ребро (3,1) включаем в маршрут с новой границей H = 16
Всоответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,3) и (4,2).
Врезультате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,2), (2,3), (3,1),
Длина маршрута равна F(Mk) = 16
4
Вывод
В ходе данной лабораторной работы был изучен метод ветвей и границ применительно к решению задач коммивояжера.
5