Дискретная математика. Громов Ю.Ю - 84 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

84
17. ЗАДАЧА О КОММИВОЯЖЁРЕ
Пусть имеется матрица A = [a
ij
]
n×n
с элементами a
ij
≥ 0 при i ≠ j и
a
ij
= ∞ в противном случае. Пусть S(n) является множеством подстановок
порядка n и Z(n) − множеством циклических подстановок из S(n). Каждому
элементу Z(n) вида
=π
n
iii
n
...
...21
21
сопоставим число
∑
π
=πσ
)(,
)(
ii
a
.
Требуется найти подстановку π
0
такую, что
)(min)(
)(
0
πσ=πσ
∈π
nZ
.
Величину σ(π
0
) будем обозначать иногда через σ
0
(A), подстановку π
0
называть оптимальной подстановкой, матрицу A − матрицей расстояний.
Для получения геометрического смысла сформулированной задачи
о коммивояжёре элементы a
ij
матрицы A следует рассматривать как дли-
ны дуг полного ориентированного графа G с n вершинами, задающего
антирефлексивное бинарное отношение. Тогда любая подстановка
π ∈ Z(n) определяет в графе гамильтонов контур, и задача состоит в оп-
ределении кратчайшего из всех таких контуров.
На практике задача о коммивояжере встречается там, где возникает
вопрос о наилучшем упорядочении каких-либо объектов, действий и т.п.
Например, при определении маршрута развозки товаров по торговым
точкам такого, чтобы длина пробега машины была бы минимальной; при
определении порядка обработки деталей на станке, который обеспечит
минимальное суммарное время переналадки станка, необходимой при
переходе от одной детали к другой.
Поскольку прямой перебор всех (n − 1)! возможностей в задаче о
коммивояжёре высокой размерности (при n ~ 10
2
…10
3
) даже с использо-
ванием современных ЭВМ практически неосуществим, рассмотрим эф-
фективный метод ветвей и границ, который даёт точное решение данной
задачи.
ν
0
ν
1
ν
2
ν
3
ν
4
ν
5
ν
6
ν
7
ν
8
ν
9
ν
10
ν
11
5
5
2
2
3
1
2
1
5
1
1
1 5
5
2
2
3
ν
12
ν
13
ν
14
ν
15
3
5
4
4 4
3
4

Страницы