Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм метода ветвей и границ

1. Находим в каждой строке матрицы стоимостей проезда минимальной элемент и вычитаем его из каждого элемента этой строки. Если в полученной матрице окажутся столбцы, не содержащие нулевых элементов, то в каждом из них находим минимальный элемент и вычитаем его из всех элементов этого столбца. Таким образом, приходим к матрице, каждая строка и каждый столбец который содержат, по меньшей мере, один нулевой элемент.

2. Суммируем все минимальные элементы строк и столбцов, которые вычитали для проведения матрицы. Эта сумма является нижней границей Н множества решений, которая берется в качестве корня дерева решений.

3. Если в каждой строке и в каждом столбце было ровно по одному нулевому элементу, то эти элементы образовали бы оптимальный маршрут, и оптимальная стоимость проезда равнялась бы Н.

4. Если это не так, то по матрице стоимости строят одно звено оптимального маршрута. Если выбирают звено (i,j) (где i- строки, j- номер столбца матрицы стоимостей), то решение не должно содержать других звеньев соответствующих элементам i- ой строки и j- го столбца. Для выбора звена оптимального маршрута, выбираем вершины (i,j), для которых Cij = 0. Рассмотрим маршруты, не содержащие звено (i,j). Пункт i должен быть связан с некоторым другим пунктом и поэтому каждый маршрут, не содержащий узел (i,j) должен содержать звено, у которого стоимость не меньше минимального значения элемента i- ой строки, не считая Cij, равного нулю. Аналогично, для того чтобы в пункт j можно было попасть из некоторого другого пункта, маршрут, не содержащий узел (i,j), должен содержать звено, у которого стоимость не меньше, чем стоимость минимального значения элемента j-го столбца, не считая Cij. Сумму минимальной стоимости в i- ой строке (за исключением Cij) и минимальной стоимости в j-ом столбце (за исключением Cij) называют вторичным штрафом Fij. Значение Fij равно минимальному штрафу, которому мы подвергаемся, если не включаем звено(i,j) в оптимальный маршрут. Если штраф за не использование звена вычислить для всех звеньев, у которых Cij=0, то можно сравнить соответствующие значения Fij и включить текущий маршрут такое звено (i,j), для которого штраф за не использование звена максимальный. То есть включая звено (i,j), мы получаем выигрыш в стоимости, равный максимальному значению Fij. Таким образом, нижняя граница ветви дерева маршрутов, по ветке, не включающий узел (i,j), должна быть ровна сумме текущей нижней границе и максимального штрафа за не использование звена (i,j).

5. Чтобы определить новую нижнюю границу маршрутов, включающих звено (i,j), необходимо преобразовать матрицу стоимости. Если в маршрут включено некоторое звено (i,j), то в дальнейшем мы не рассматриваем i-ю строку и j-ый столбец. Кроме того, звено (i,j) является звеном некоторого ориентированного цикла, и но не может принадлежать этому же маршруту. Последнее условие можно выполнить, положив c_ij=co. Из рассмотрения следует исключить и так называемые запрещенные звенья, с помощью которых в дальнейшем могут быть образованы замкнутые циклы, включающие в себя неполное множество пунктов (могут быть образованы под маршруты) элементы матрицы стоимости, соответствующие этим звеньям, берут равными ∞. Нижняя граница для маршрута, содержащего звено (i,j), вычисляется после приведения матрицы, полученной вычеркиванием i-ой строки и j-го столбца, как H с предыдущего уровня и констант приведения (то есть минимумов строк и столбцов, которые вычитались из новой матрицы для получения нулевых элементов в каждой строке и в каждом столбце). Далее процесс выбора звеньев оптимального решения повторяется, пока не построится замкнутый передвижения коммивояжера.

H+Fij H₁

6. Построенный таким образом полный маршрут будет оптимальным, если его стоимость не превосходит стоимости любого маршрута, соответствующего другим звеньям дерева решений. Если есть ветви дерева стоимость движения, по которым меньше, чем стоимость движения по оптимальному маршруту, следует возвратиться на эти ветки и просчитать маршруты по ним. Процедуру анализа предыдущих промежуточных точек ветвления, которые могли бы определить более дешевый маршрут, называют возвратом. Матрицу стоимости в данном случае называют матрицей стоимости возврата (в ней в соответствии с веткой отражения звена (m,k), ставится запрещение движения по этому звену c_mk=∞). С новой матрицей стоимости возврата выполняют описанные процедуры ветвления и построения границ. В результате выбирают маршрут с наименьшим значением нижней границы.