2015-04-30
2380
Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.
| Город | di | ||||
| М | |||||
| М | |||||
| М | |||||
| М |
Редукция строк.
Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).
| Город | di | ||||
| М | |||||
| М | |||||
| М | |||||
| М |
В итоге в каждой строке будет хотя бы одна нулевая клетка.
Нахождение минимума по столбцам.
Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.
| Город | di | ||||
| М | |||||
| М | |||||
| М | |||||
| М | |||||
| dj |
Редукция столбцов.
Вычитаем из каждого элемента матрицы соответствующее ему dj.
| Город | di | ||||
| М | |||||
| М | |||||
| М | |||||
| М | |||||
| dj |
В итоге в каждом столбце будет хотя бы одна нулевая клетка.
|
|
|
Вычисление оценок нулевых клеток.
Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.
| Город | ||||
| М | 0 (4) | |||
| М | ||||
| М | ||||
| М |
И так по всем нулевым клеткам:
| Город | ||||
| М | 0 (4) | |||
| М | 0 (5) | 0 (1) | ||
| 0 (4) | М | |||
| 0 (6) | М |
Редукция матрицы.
Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).
| Город | ||||
| М | 0 (4) | |||
| М | 0 (5) | 0 (1) | ||
| 0 (4) | М | |||
| 0 (6) | М |
Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).
| Город | ||||
| М | 0 (4) | |||
| М | 0 (5) | М | ||
| 0 (4) | М | |||
| M | М |
Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
Если мы еще не нашли все отрезки пути, то возвращаемся ко второму пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.
|
|
|
Если все отрезки пути найдены (или найдены еще не все отрезков, но оставшаяся часть пути очевидна) – переходим к пункту 9.
Вычисление итоговой длины пути и построение маршрута.
Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными.
В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4.
Общая длина пути: L = 30.
