ВУЗ:
Составители:
Рубрика:
показано на рисунке 3.9. Алгоритм АЧП формирует множество схем маршрутов,
реализуя разбиение исходной задачи на взаимно независимые подзадачи в соответствии
со стратегией И/ИЛИ-графов [4]. Построим мультиграф с двумя типами вершин.
Вершины типа “И” помечаются номерами вершин исходного графа, вершины типа
“ИЛИ"
помечаются списками вершин, достижимых (смежных) и недостижимых из
соответствующей “И”-вершины графа. Правила алгоритма АЧП позволяют на каждом
шаге алгоритма множество свободных вершин разбить на две части: достижимое и
недостижимое подмножества. Причем достижимость понимается либо как
непосредственный переход по дуге графа, либо, опосредованно, через вершины
предшествующего уровня иерархии, т.е. в
соответствии со схемой маршрута.
На рисунке 3.10 а) показан И/ИЛИ-граф алгоритма АЧП для графа G1. Решением
задачи перечисления схем маршрутов является подграф И/ИЛИ-графа, из которого
исключены ИЛИ вершины (см. рис. 3.10 б)).
3.5. Эффективность алгоритма АЧП
Эффективность зависит от связности графа. Для полносвязанного графа
реализуется полный просмотр всех схем маршрутов. В остальных случаях число
проверок реализуемости маршрутов на графе
ξ
G
равно сумме мощностей множеств
достижимости и недостижимости. Для случая, рассмотренного в примере, таких
проверок было произведено 25 и обнаружено 4 схемы, в то время как общее число
проверок 5!=120.
ξ
G
для некоторого графа G, можно оценить по формуле:
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
