рейтинговая работа. Рейтинговая работа. Кафедра Математика и информатика
 Скачать 0.56 Mb.
|
|
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца. Г2,5=2, Г3,1=0, Г3,2=0, Г4,2=0, Г4,5=0, Г5,1=0, Г5,2=0, Г5,3=3, Максимальное значение имеет Г5,3=3. Удалим из матрицы стоимости строку 5 и столбец 3. Внесем в текущий ориентированный граф дугу (5,3).
В строке 3 и столбце 5 отсутствует элемент равный ∞. Присвоим элементу (3,5) значение бесконечности чтобы избежать преждевременного замыкания контура. Текущая нижняя граница=12. Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца. Г2,5=2, Г3,1=2, Г3,2=0, Г4,2=0, Г4,5=0 В результате сравнения мы получили 2 одинаковых максимальных Г=2. Это означает что алгоритм разветвляется, и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г2,5=2. Удалим из матрицы стоимости строку 2 и столбец 5, и присвоим элементу (5,2) значение бесконечности. Внесем в текущий ориентированный граф дугу (2,5)
В строке 3 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (3,2) значение бесконечности чтобы избежать преждевременного замыкания контура. Текущая нижняя граница=12. После того, как ранг матрицы становится равным двум, мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы. НГр=12. Маршрут коммивояжера включает в себя дуги: (1, 4), (5, 3), (2, 5), (3, 1), (4, 2). Вернемся к возникшему у нас ветвлению и рассмотрим случай, при котором максимальное значение имеет Г3,1. Удалим из матрицы стоимости строку 1 и столбец 3. Внесем в текущий ориентированный граф дугу (3,1).
В строке 4 и столбце 5 отсутствует элемент равный ∞. Присвоим элементу (4,5) значение бесконечности, чтобы избежать преждевременного замыкания контура. После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы. НГр=12 Маршрут коммивояжера включает в себя дуги: (1, 4), (5, 3), (3, 1), (2, 5), (4, 2). Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г2,5. Удалим из матрицы стоимости строку 5 и столбец 2. Внесем в текущий ориентированный граф дугу (2,5).
В строке 5 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (5,2) значение бесконечности чтобы избежать преждевременного замыкания контура. Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца. Г1,2=0, Г1,3=0, Г1,4=4, Г3,1=0, Г3,2=0, Г4,2=2, Г5,1=0, Г5,3=0, Максимальное значение имеет Г1,4=4. Удалим из матрицы стоимости строку 1 и столбец 4. Внесем в текущий ориентированный граф дугу (1,4).
В строке 4 и столбце 1 отсутствует элемент равный ∞. Присвоим элементу (4,1) значение бесконечности, чтобы избежать преждевременного замыкания контура. Текущая нижняя граница=12. Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
|