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