Конец алгоритма

Примечание. Пункт 6 используется для нетреугольной матрицы S.

Алгоритм. Получение поздних сроков окончания выполне­ния операторов.

1. Положим где ..

2. Просмотрим столбцы матрицы S справа налево, выберем пер­вый необработанный столбец матрицы и произведем переход к сле­дующему шагу. Если обработаны все столбцы, то конец алгоритма.

3. Пусть j — номер очередного необработанного столбца. Если он не содержит единичных элементов, то вычислим (Т)= Т, где Т — время решения задачи, и перейдем к шагу 5.

4. Если столбец j содержит единичные элементы, то вычислим ,т.е. минимум определим по всем j_v еди­ничным элементам j-гo столбца. Если , то выполним шаг 6.

5. Обработанный j-й столбец исключим из рассмотрения, затем выполним шаг 2.

6. Если найден столбец j_v, для которого , то проведем поиск необработанного столбца j _v, вычислим j = j _v и выполним переход к шагу 3.