Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

10. Приложение

Ниже излагается алгоритм вычисления верхней границы В минимального числа перенастроек аппаратуры, требующихся в задаче планирования из разд. 4 данной главы, который можно использовать в качестве начального алгоритма этого раздела.

Шаг 0. Индекс

Шаг 1. Взять метки Положить

Шаг выбрать любое положить

Шаг 3. Если индекс образовать в противном случае Здесь и а также

Шаг 4. Если то перейти к шагу 5; в противном случае и вернуться к шагу 3.

Шаг 5. Найти

Шаг 6. Если индекс найти в противном случае найти

Шаг 7.

Если то и перейти к шагу 12; в противном случае перейти к шагу 8.

Шаг Если перейти к шагу 9; в противном случае перейти к шагу 5.

Шаг 9. Если индекс индекс и перейти к шагу 1; в противном случае перейти к шагу 10.

Шаг 10. Если то и перейти к шагу 12; в противном случае перейти к шагу 11.

Шаг 11. Индекс

Шаг 12. Стоп. В является требуемой верхней границей.

Алгоритм требует некоторых пояснений. Если индекс то прослеживаются прямые цепи, проходящие по вершинам графа начиная с вершины Эти цепи прослеживаются с присвоением метки тем вершинам из которые могут быть достигнуты из через дуг (шаги 1, 2, 3 и 4). Если ни одна из этих цепей не может быть продолжена, то алгоритм переходит к шагам 5, 6 и 7, в которых самая длинная из этих цепей прослеживается назад к вершине при этом убираются из графа вершины (и ассоциированные с ними дуги), лежащие на этой самой длинной цепи. Шаг 8 прекращает процесс удаления вершин. Шаг 9 возвращает к началу алгоритма со значением индекса чтобы начать формирование обратных цепей, т. е. цепей, оканчивающихся в Снова находится и удаляется самая длинная из этих цепей.

Самая длинная из прямых и обратных цепей (в или из может рассматриваться как одна длинная цепь, содержащая Число В (необходимых последовательностей цепей) увеличивается тогда на единицу на шаге 11, и после выбора другой вершины из оставшегося графа процесс продолжается (формируются новые длиннейшие прямые и обратные цепи и т. д.), пока не будет исчерпан весь граф.

Конечное значение В, которое равно числу последовательностей цепей, необходимых для «стирания» всего графа (т. е. для покрытия всех вершин), является тогда, очевидно, верхней границей для требуемого минимального числа таких покрывающих последовательностей (т. е. минимального числа перенастроек аппаратуры).

<< Предыдущий параграф Следующий параграф >>
Оглавление