Задача коммивояжера или «задача о странствующем торговце». Также встречается название «задача китайского почтальона»


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



Скачать 61,64 Kb.
страница3/3
Дата11.12.2022
Размер61,64 Kb.
#196522
ТипЗадача
1   2   3
Связанные:
задача коммивояжера

Алгоритм решения задачи коммивояжера (метод ветвей и границ):

  • Построение матрицы с исходными данными — в таблицу заносятся расстояния (Cij) между городами, при этом строкам соответствуют города отбытия, а столбцам города прибытия

  • Нахождение минимумов по строкам — в каждой строке определяется минимальное число (di) и выписывается в отдельный столбец

  • Редукция строк — из значений ячеек каждой строки вычитаем соответствующий минимум (Cij = Cij — di), не затрагивая при этом клетки с M

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

  • Редукция столбцов — из значений ячеек каждого столбца вычитаем соответствующий минимум (Cij = Cij — dj), не затрагивая при этом клетки с M

  • Нахождение корневой нижней границы (делаем это только один раз, в следующие разы пункт 6 пропускаем) — вычисляем нижнюю границу в стартовой (корневой) точке решения, как сумму найденных ранее минимумов.

  • Вычисление оценок нулевых клеток — считаем оценки (pij) для каждой ячейки с нулями, как сумму минимумов по строке и столбцу, в которых располагается нулевая клетка, не учитывая при этом саму нулевую клетку

  • Выбор нулевой клетки с максимальной оценкой — ищем среди нулевых клеток обладающую наибольшей оценкой.

  • Редукция матрицы — вычеркиваем относящиеся к выбранной клетке строку и столбец, а также заменяем значение ячейки, соответствующей обратному пути на M

  • Вычисление нижней границы первой ветви (включающей отрезок пути) — вновь находим минимумы по строкам, проводим редукцию строк, находим минимумы по столбцам, проводим редукцию столбцов, после чего вычисляем локальную нижнюю границу, как сумму предыдущей локальной нижней границы и минимумов (Hk = Hk-1 + ∑di + ∑dj), и добавляем вершину в граф

  • Вычисление нижней границы второй ветви (не включающей отрезок пути) — считаем локальную нижнюю границу, как сумму предыдущей локальной нижней границы и оценки выбранной ранее нулевой клетки (Hk* = Hk-1 + pij), и добавляем вершину в граф

  • Выбор ветви с минимальным значением нижней границы — среди еще не ветвившихся вершин выбираем обладающую минимальным значением локальной нижней границы (вне зависимости от того, какую ветвь рассматриваем в данный момент)

  • Если полный маршрут еще не найден, продолжаем решение, если найден — переходим к пункту 10 — если маршрут еще не найден, то ход дальнейшего решения зависит от выбранной ветви: (а) первая ветвь — переходим к пункту 7, (б) вторая ветвь — в клетку с максимальной оценкой ставим M и переходим к пункту 2, (в) другая ветвь — возвращаемся к соответствующим ей этапу решения и таблице данных

  • Построение полного маршрута и определение его длины — соединяем все найденные ранее отрезки пути в полный маршрут и считаем его общую длину (данные берем из исходной таблицы).




Источник: Галяутдинов Р.Р. Задача коммивояжера - метод ветвей и границ // Сайт преподавателя экономики. [2020].
Скачать 61,64 Kb.

Поделитесь с Вашими друзьями:
1   2   3




База данных защищена авторским правом ©psihdocs.ru 2023
обратиться к администрации

    Главная страница