- •Методические указания к контрольной работе
- •Содержание
- •Теоретический материал
- •1. Построение матрицы с исходными данными.
- •2. Нахождение минимума по строкам.
- •3. Редукция строк.
- •4. Нахождение минимума по столбцам.
- •5. Редукция столбцов.
- •6. Вычисление оценок нулевых клеток.
- •7. Редукция матрицы.
- •8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
- •9. Вычисление итоговой длины пути и построение маршрута.
- •Задание к контрольной работе
- •Варианты исходных данных
- •Приложения
2. Нахождение минимума по строкам.
Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.
Город |
1 |
2 |
3 |
4 |
di |
1 |
М |
5 |
11 |
9 |
5 |
2 |
10 |
М |
8 |
7 |
7 |
3 |
7 |
14 |
М |
8 |
7 |
4 |
12 |
6 |
15 |
М |
6 |
3. Редукция строк.
Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).
Город |
1 |
2 |
3 |
4 |
di |
1 |
М |
0 |
6 |
4 |
5 |
2 |
3 |
М |
1 |
0 |
7 |
3 |
0 |
7 |
М |
1 |
7 |
4 |
6 |
0 |
9 |
М |
6 |
В итоге в каждой строке будет хотя бы одна нулевая клетка.
4. Нахождение минимума по столбцам.
Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.
Город |
1 |
2 |
3 |
4 |
di |
1 |
М |
0 |
6 |
4 |
5 |
2 |
3 |
М |
1 |
0 |
7 |
3 |
0 |
7 |
М |
1 |
7 |
4 |
6 |
0 |
9 |
М |
6 |
dj |
0 |
0 |
1 |
0 |
|
5. Редукция столбцов.
Вычитаем из каждого элемента матрицы соответствующее ему dj.
Город |
1 |
2 |
3 |
4 |
di |
1 |
М |
0 |
5 |
4 |
5 |
2 |
3 |
М |
0 |
0 |
7 |
3 |
0 |
7 |
М |
1 |
7 |
4 |
6 |
0 |
8 |
М |
6 |
dj |
0 |
0 |
1 |
0 |
|
В итоге в каждом столбце будет хотя бы одна нулевая клетка.
6. Вычисление оценок нулевых клеток.
Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.
Город |
1 |
2 |
3 |
4 |
1 |
М |
0 (4) |
5 |
4 |
2 |
3 |
М |
0 |
0 |
3 |
0 |
7 |
М |
1 |
4 |
6 |
0 |
8 |
М |
И так по всем нулевым клеткам:
Город |
1 |
2 |
3 |
4 |
1 |
М |
0 (4) |
5 |
4 |
2 |
3 |
М |
0 (5) |
0 (1) |
3 |
0 (4) |
7 |
М |
1 |
4 |
6 |
0 (6) |
8 |
М |