Задача коммивояжера или «задача о странствующем торговце». Также встречается название «задача китайского почтальона»
Алгоритм решения задачи коммивояжера (метод ветвей и границ)
Скачать 61,64 Kb.
|
задача коммивояжера
| Алгоритм решения задачи коммивояжера (метод ветвей и границ):
Построение матрицы с исходными данными — в таблицу заносятся расстояния (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. Поделитесь с Вашими друзьями:
|