Алгоритмрешения задачметодомветвейиграниц

включает следующуюпоследовательность:

1. Проводим операцию редукции матрицы расстояний по столбцам и строкам и находим нижнюю границу всего множествамаршрутов:H=adi+adj.

2.Вкаждой клетке, вкоторых dij=0,поочередно заменяем нули на ?после этого находим новые суммы констант приведенияdi+dj, каковые записываемвклеткахрядомснулемвскобках

3.Выбираемреброветвления(i,j)помаксимальнойвеличине суммыконстант приведения. Затемисключаем егоизмножества путемзаменыэлементаматрицыdij=?.Врезультатебудетобразованоподмножествомаршрутов{(i,j)}.

4.Редуцируемполученнуюматрицурасстоянийиопределяем нижнююграницуэтогоподмножествамаршрутовH(i,j).

5.Включаемдугу(i,j)вмаршрутпутемисключения i-йстрокииj-гостолбцаизматрицы изаменысимметричногоэлемента матрицыdji=?для исключенияобразованиянегамильтоновацикла.

i,j).

6. Редуцируем сокращенную матрицу и определяем нижнюю границу подмножества Н{(i, j)}

7. Сопоставляем нижние границы подмножеств Н{(i, j)} и

Н{(i, j)}

i,j)}

и подвергаем подмножество, имеющее меньшее значение нижней границы, ветвлению.

8.Определяемгамильтоновциклприполученииматрицы2?2.

Методика ответа задачи коммивояжера:

1.Построение матрицы с исходными данными — длины дорог соединяющих города представить в виде следующей таблицы:

В отечественном примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м вторым, в зависимости от направления перемещения (т.к. кое-какие ж/д дороги смогут быть с односторонним перемещением и т.д.). Расстояние от города к этому же городу обозначено буквой M. Кроме этого употребляется символ бесконечности. Это сделано чтобы этот отрезок путь был условно принят за вечно долгий. Тогда не будет смысла выбрать перемещение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2.Нахождение минимума по строчкам Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

3.Редукция строчков Проводим редукцию строчков – из каждого элемента в строчке вычитаем соответствующее значение отысканного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4.Нахождение минимума по столбцам Потом находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строчок.

5.Редукция столбцов Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6.Вычисление оценок нулевых клеток

Для каждой нулевой клетки оказавшейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строчку и минимального элемента по столбцу, в которых размещена эта нулевая клетка. Сама она наряду с этим не учитывается. Отысканные ранее di и dj не учитываются. Взятую оценку записываем рядом с нулем, в скобках. И без того по всем нулевым клеткам:

7.Редукция матрицы Выбираем нулевую клетку с громаднейшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого именно города к какому движемся, в отечественном примере от 4-ого к 2-му).

тот столбец и Ту строку, где появилось две «М» всецело вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

8. В случае если полный путь еще не отыскан, переходим к пункту 2, в случае если отыскан к пункту9 В случае если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и снова ищем минимумы по столбцам и строкам, проводим их редукцию, вычисляем оценки нулевых клеток и т.д. В случае если все отрезки пути отысканы (либо отысканы еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.

9. Вычисление итоговой длины пути и построение маршрута Отыскав все отрезки пути, остается лишь соединить их между собой и вычислить неспециализированную длину пути (цена поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными. В отечественном примере маршрут оказался следующий: 4 2 3 1 4. Неспециализированная протяженность пути: L = 30.

Задача

В Крыму для путешествия на автомобиле выделены города: Бахчисарай, Ай-Петри, Ялта, Алупка и Соколиное, расстояния между которыми записаны на ребрах неориентированного графа. Выстроить оптимальный маршрут проезда по городам Крыма.

Ответ

1.Расстояниямеждугородамипредставлены ввидематрицы:

Lij
М
М
М
М
М

Выстройте кратчайшийкольцевоймаршрут объездавсехгородов.

2.Нахождение минимума по строчкам di

Lij di
М
М
М
М
М

3.Редукция строчков строчков Проводим редукцию строчков – из каждого элемента в строчке вычитаем соответствующее значение отысканного минимума (di).

Lij
М
М
М
М
М

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4.Нахождение минимума по столбцам dj

Lij
М
М
М
М
М
dj

5.Редукция столбцов Вычитаем из каждого элемента матрицы соответствующий ему элемент dj.

Lij
М
М
М
М
М

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6.Вычисление оценок нулевых клеток

Lij
М 0(53)
М
М
М
М

Для каждой нулевой клетки оказавшейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строчку и минимального элемента по столбцу, в которых размещена эта нулевая клетка. Сама она наряду с этим не учитывается. Отысканные ранее di и dj не учитываются. Взятую оценку записываем рядом с нулем, в скобках. И без того по всем нулевым клеткам:

Lij
М 0(53)
М 0(31)
М 0(33)
0(28) М
0(59) 0(2) М

7.Редукция матрицы Выбираем нулевую клетку с громаднейшей оценкой и Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого именно города к какому движемся, в отечественном примере от 5-ого к 1-му).

Lij
М М
М 0(31)
М 0(33)
0(28) М
М 0(2) М

тот столбец и Ту строку, где появилось две «М» всецело вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

Lij
М
М 0(31)
М 0(33)
0(28) М

8. В случае если полный путь еще не отыскан, переходим к пункту 2.Нахождение минимума по строчкам di:

Lij di
М
М
М
М

Редукция строчков

Lij
М
М
М
М

4.Нахождение минимума по столбцам dj

Lij
М
М
М
М
dj

Редукция столбцов

Lij
М
М
М
М

6.Вычисление оценок нулевых клеток

Lij
0(52) М
М 0(0) 0(21)
М 0(14)
0(32) М

7.Редукция матрицы Выбираем нулевую клетку с громаднейшей оценкой и Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого именно города к какому движемся, в отечественном примере от 1-ого к 2-му).

Lij
М М
М 0(0) 0(21)
М 0(14)
0(32) М
Lij
0(0) 0(21)
М 0(28)
0(51) М

4-ого к 3-му).

Lij
0(0) 0(28)
М

Ответ: (1-5-2-3-4-1); Lmin=226км.

Глава4.Методыимоделитеорииграфовисетевогомоделирования

Рис.4.5.2.Неориентированныйграфзадачикоммивояжера

Ответ задачи коммивояжера. Способ границ и ветвей.


Также читать:

Понравилась статья? Поделиться с друзьями: