ВУЗ:
Составители:
Рубрика:
A
B
G
E
F D
C
G2:
Рис. 3.8
0
1
3
2
5
G1 :
4
Рис. 3.9
Введем понятие схемы маршрута, как списка вершин маршрута без повторений. С
точки зрения классификации данных агрегата
схемы маршрутов определяют дизъюнкты
алгебры 3-х значной логики. С другой стороны, введенное понятие удобно для
организации алгоритма перечисления маршрутов орграфов, поскольку именно на схемах
маршрутов появляется возможность реализации возврата к ранее рассмотренным
вариантам и осуществления поиска новых вариантов развития вычислительного процесса
на орграфе.
Свободными вершинами графа G относительно схемы маршрута S будем называть
вершины графа, не содержащиеся в схеме маршрута
S, т.е.
L
S
V
G
V
S
() ( )
\
()
=
, где V(G) и
V(S) - соответственно вершины графа и схемы маршрута.
Алгоритм частичного перебора (АЧП) использует следующие правила:
1. Вершины графа кодируются символами упорядоченного множества любым
способом, но так, чтобы корневая вершина имела наименьший код, а концевые -
наибольшие значения.
2. На каждом шаге работы алгоритма для текущего состояния схемы маршрута S
i
ищется путь на орграфе перехода из последней вершины S
i
в любую свободную вершину
схемы S
i
.
3. Если переход возможен, то схема маршрута “расширяется” на один символ.
4. Если переход невозможен, то рассматривается следующая вершина списка
свободных вершин и так до тех пор, пока не кончится список вершин.
5. Если переход из текущей вершины в любую из свободных вершин (не
содержащихся в схеме маршрута) невозможен, то происходит “откат
” по схеме
маршрута на один символ назад.
6. При достижении концевой вершины алгоритм “откатывает” на один символ
назад.
7. Алгоритм завершает свою работу, если список свободных вершин корневой
вершины исчерпан.
Схема маршрута Lvv v
m
=
{ , ,..., }
01
реализует сжимающее кодирование маршрутов
на орграфах, поскольку описывает путь из корневой вершины в концевую
vv
m0
→
через
любое количество повторений, предшествующих v
m
вершин. Схема маршрута позволяет
закодировать любые маршруты орграфа: простые, сложные и составные.
Таким образом, введения понятия схем маршрутов позволяет осуществить
отображение из потенциально бесконечного множества маршрутов на конечное
множество их схем.
Покажем, что алгоритм АЧП реализует частичный перебор схем маршрутов. В
качестве примера рассмотрим граф G1, вершины которого пронумеруем так,
как это
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
