Задание № 2. Задача о коммивояжере.
Метод ветвей и границ
Расстояния между пунктами заданы матрицей: Оценка на перспективном множестве: Оценка на перспективном множестве: Оценка на перспективном множестве: Дерево решения имеет следующий вид: Ответ: l* =C15+C52+C24+C43+C36+C61=1+1+1+1+1+1=6. Нижняя граница цикла: d0=6 (). Х52=1+5=6, следовательно,. Х43=2+2=4, следовательно,. Х36=1+1=2, следовательно,. Оценка длины цикла:. Оценка длины цикла:. Оценка… Читать ещё >
Задание № 2. Задача о коммивояжере. Метод ветвей и границ (реферат, курсовая, диплом, контрольная)
Расстояния между пунктами заданы матрицей:
С =. | ||||||||
Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы C по строкам:
hн= min (i) hнi
hн | |||||||||
С' =. | |||||||||
Произведем приведение матрицы C по столбцам: gi = min (х) gнi
С' =. | ||||||||
gi | ||||||||
В итоге получаем полностью приведенную (редуцированную) матрицу:
hн | |||||||||
С0 =. | |||||||||
gi | |||||||||
Величины hн и gi называются константами приведения.
Нижняя граница цикла: d0=6 ().
Шаг № 1.
Определяем ребро ветвления и разобьем все множество допустимых значений Q0 относительно этого ребра на два непересекающихся подмножества () и (), т. е., где.
В приведенной матрице исследуем все нулевые переходы.
бн | |||||||||
C0 =. | 0(4). | ||||||||
0(0). | 0(0). | ||||||||
0(2). | |||||||||
0(4). | |||||||||
0(2). | |||||||||
0(0). | 0(0). | ||||||||
вi | |||||||||
Наибольшая сумма констант приведения равна.
х15= б1 + в5 =2+2=4,.
следовательно,.
множество разбивается на два подмножества и .
Оценка длины цикла: .
В результате получим другую сокращенную матрицу (5×5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hн | ||||||||
C1=. | ||||||||
gi | ||||||||
d1=0.
Шаг № 2.
Определяем ребро ветвления и разобьем все множество допустимых значений Q1 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
бн | ||||||||
0(0). | 0(0). | |||||||
0(2). | ||||||||
C1=. | 0(4). | |||||||
0(2). | ||||||||
0(0). | 0(0). | |||||||
вi | ||||||||
Наибольшая сумма констант приведения равна.
х43=2+2=4, следовательно,.
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (4×4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hн | |||||||
C2 =. | |||||||
gi | |||||||
d2=0.
Шаг № 3.
Определяем ребро ветвления и разобьем все множество допустимых значений Q2 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
бн | |||||||
C2 =. | 0(0). | 0(0). | |||||
0(2). | |||||||
0(2). | |||||||
0(0). | 0(0). | ||||||
вi | |||||||
Наибольшая сумма констант приведения равна.
х36=1+1=2, следовательно,.
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (3×3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hн | ||||||
C3 =. | ||||||
gi | ||||||
d3=0.
Шаг № 4.
Определяем ребро ветвления и разобьем все множество допустимых значений Q3 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
бн | ||||||
0(0). | 0(1). | |||||
C3 =. | 0(6). | |||||
0(5). | ||||||
вi | ||||||
Наибольшая сумма констант приведения равна.
х52=1+5=6, следовательно,.
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (2×2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hн | |||||
C4 =. | |||||
gi | |||||
d4=0.
В соответствии с этой матрицей включаем в маршрут и .
Ответ: l* =C15+C52+C24+C43+C36+C61=1+1+1+1+1+1=6.
Дерево решения имеет следующий вид: