Все элементы данного столбца вычитаем из max элемента
Нахождение min элемента в i-й
строке
Из каждого элемента строки вычитаем min
элемент
Формируем
матрицу С0
Отмечаем нули звездочкой
Конец
Рис.9: Процедура «Предварительный этап»
Процедура «Первый этап»
1.
k-я итерация уже проведена и в результате получена
матрица Ck;
2.
Перед началом итерации
знаком «+» выделяются столбцы матрицы Ck, которые содержат нули со звездочкой;
3.
Невыделенный нуль отмечают
штрихом и выделяют строку, в которой он содержится, постановкой справа от нее
знака «+», Затем уничтожают знак «+», обводя его кружочком над тем столбцом, на
пересечении которого с данной выделенной строкой содержится нуль со звездочкой;
4.
Далее просматривают этот
столбец, отыскивают в нем выделенный нуль (нули), не отмеченный звездочкой,
отмечают его штрихом и выделяют строку (строки), содержащие такой нуль (нули)4
5.
Затем просматривают эту
строку (строки), отыскивают в них нуль со звездочкой;
6.
Конец.
Процедура первого
этапа представлена на рис. 10
Начало
1
2
3
4
5
6
Формирование матрицы Сk
Выделяем столбцы матрицы Сk
Отмечаем штрихом невыделенный нуль
Находи и отмечаем звездочкой в столбце
невыделенные нули
Выделяем строки содержащие нули со штрихом и звездочкой
Конец
Рис. 10: Процедура «Первый этап»
Процедура «Второй этап»
1.
Строят следующую цепочку
из элементов матрицы Ck: исходный нуль со штрихом, нуль со
звездочкой, расположенный в одном столбце с первым, нуль со штрихом,
расположенный в одной строке с предыдущем нулем со звездочкой, и т.д. Итак,
цепочка образуется передвижением от 0’ к 0* по столбцу, от 0* к 0’ по строке и
т.д.;
2.
Далее над элементами
цепочки, стоящими на нечетных местах (0’), ставим звездочки, уничтожая их над
четными элементами (0*);
3.
Затем уничтожаем все
штрихи над элементами матрицы и знаки «+»;
4.
Количество независимых
нулей будет увеличино на единицу;
5.
Конец;
Процедура второго
этапа представлена на рис. 11
Начало
1
2
3
4
5
Построение цепочки из элементов матрицы Сk
Передвижение элементов по цепочке
Уничтожение всех штрихов над элементами матрицы Ck и
знаков «+»
