|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Slobodskoy 2:5015/128.22 19 May 2002 21:09:01
To : Sergey Sundeev
Subject : Re: решение задачи коммивояжера методом ветвей и границ
--------------------------------------------------------------------------------
Привет, Sergey!
До меня докатились слухи, что ты что-то там написал о "решение задачи
коммивояжера методом ветвей и границ"! Так, так... надо бы разобраться...
SS> Сабж. Или что нибудь похожее.
Из курса "Математические основы информатики":
Решение задачи коммивояжера Методом Ветвей и Границ (МВГ).
Есть R = ||Rij||nxn - расстояния,
X = ||Xij||nxn, Xij = 1 (если идем из i-ого в j-ый), 0, если не идем.
Ограничения:
(1) Сумма(Xij для i=1..n) = 1, j = 1..n
(2) Сумма(Xij для j=1..n) = 1, i = 1..n
//Оба ограничения обозначают единственность попадания в город и обязательное
посещение всех городов
(3) Xij принадлежит {0,1}
(4) Ui - Uj + n*Xij <= n-1, i<>j, i,j = 1..n
//Это чтобы не было циклов. Есть док-во этого факта.
//Ui - доп. переменные, интерпретируются как номер по порядку посещения
коммивояжером города i
Критерий:
(5) F(x,U) = сумма(сумма(RijXij для j = 1..n) для i = 1..n) -> min
Это была, собственно, формулировка задачи, теперь решение МВГ:
Индивидуальные процедуры:
Для нахождения верхней оценки (V) используется "жадный алгоритм", т.е. из
1-ого двигаемся в тот город, расстояние до кот. минимально и т.д. Это даст
допустимое решение, знач. критерия на котором и определит верхнюю оценку.
Для нахождения нижней оценки (H) нужно построить релаксацию задачи
коммивояжера, убирая ограничение (4) - это получается задача о назначениях, но
ее сложность O(n^3), что довольно трудоемко, поэтому строится релаксация к
задаче о назначениях, удаляем либо ограничение (1), либо (2). Для решения
релаксированной задачи предлагается такая процедура: в таблице X выбираются и
суммируются минимальные элементы в каждой строке (пусть их сумма - N),
очевидно, это будет решение релаксированной задачи без ограничения (1). Затем
выбираются и суммируются минимальные элементы в каждом столбце (их суммма - M),
это будет решение задачи релакс. задачи без (2). В качестве нижней оценки
выбирается max(N,M).
Процедура ветвления:
Рассматриваются все оставшиеся нерассмотренные направления.
Процедура отсева:
Если в одном направлении верхняя оценка - V1, а в другом нижняя - H2, и
V1<=H2, то можно больше не идти по второму направлению.
Процедура останова:
Если в результате решения осталось одно неотброшенное направление, в кот. V=H
(нижняя и верхняя оценки совпадают), то задача решена и решение определяется
тем путем, кот. мы шли по этому направлению.
Все, теперь решаем задачу МВГ, т.к. все процедуры этого метода ясны. Если
что-то неясно с самим МВГ - пиши...
Пока, Sergey..
Vitaly Slobodskoy
FIDO: 2:5015/128.22
E-Mail: vital@mail.nnov.ru
--- WP/95 Rel 1.78E (215.0) Reg.
* Origin: Тому,кто ЭТО придумал,надо в голову гвоздь забить!Я его
ПРЕЗИРАЮ!(ДМБ) (2:5015/128.22)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: решение задачи коммивояжера методом ветвей и границ 
