ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 20.10.2024
Просмотров: 63
Скачиваний: 0
моделирования, так как их рабочие алгоритмы включают две простые операции: арифметическое суммирование и логическую oneрацию определения экстремальной величины.
Для несимметричных графов без контуров (рис. 2, а) можно применить следующий простой алгоритм определения экстремальных путей.
1. Множество узлов сети упорядочивается таким образом, чтобы номер конечного узла каждой ветви был больше номера ее началь ного узла [94] (рис. 2, б).
2.Начальному узлу се ти приписывается число нуль.
3.Выбирается мини
мальная |
(максимальная) |
|
||||
по |
длине |
ветвь, входящая |
а |
|||
во |
второй |
узел, |
а |
число, |
||
соответствующее |
ее длине, |
|
||||
приписывается этому узлу |
|
|||||
и |
прибавляется |
к |
длинам |
б |
||
выходящих из него ветвей. |
||||||
|
||||||
|
4. Выбирается |
мини |
|
|||
мальная |
(максимальная) |
|
||||
по |
длине ветвь, входящая |
|
||||
в третий узел (с учетом |
|
|||||
скорректированных |
на |
|
||||
третьем шаге длин |
ветвей, |
|
||||
выходящих из |
второго уз |
ее длине, приписывается |
этому |
|
ла), |
а число, |
соответствующее |
||
узлу |
и прибавляется к длинам |
выходящих из него ветвей |
и т. д. |
|
Процесс завершается на последнем узле сети. При этом каждому узлу приписывается число, соответствующее длине экстремального пути в нем в соответствии с выражениями
^min (/) === ГПІП [^rnln (0 |
(1-6) |
I |
|
Uv,ах (/) = max [/max if) "І" /</]• |
(В7) |
і |
|
В результате однократного просмотра всех узлов сети таким об разом получается дерево экстремальных путей с вершиной в на чальном узле.
1.3.ПУТИ ЗАДАННОЙ ДЛИНЫ НА ГРАФАХ
Вотличие от экстремальных сетевых, задача о допусти мых по длине путях в сети не была предметом широких исследова ний. Практический интерес к этой задаче возник при рассмотрении
ряда вопросов оперативно-календарного планирования и управле ния [209].
9
Комбинаторный характер, а также отсутствие явно выраженных экстремальных свойств задачи определения путей допустимой дли ны не позволяет организовать достаточно простую и эффективную процедуру, подобно рассмотренной для задач об экстремальных путях.
Путь заданной длины можно описать следующим выражением:
L — A L < L p< L +AL, |
(1.8) |
где L + AL — длина заданного пути.
В работе [212] пути заданных длин на произвольном графе сети определяются с помощью универсальной электронной цифровой вычислительной машины. Используемая для этой цели программа основана на полном переборе всех возможных цепочек графа. Заме тим, однако, что подобный подход к решению задачи может быть ■сопряжен с недопустимо большими затратами времени, так как пол ный перебор возможных вариантов может привести к просчету очень большого числа различных путей даже для сравнительно не больших по объему сетей. Чтобы убедиться в этом, определим число путей N в несимметричном графе, отличающихся хотя бы одной вет вью.
Обозначим тц — число ветвей, которым соответствует общая упорядоченная пара узлов (і, /), а Ntj — число различных путей между і-м и j-м узлами сети. Тогда число различных путей между начальным и конечным узлами сети можно определить как послед ний член последовательности
N \t2 = |
/72],2 |
|
|
|
N\fi = |
N 1,2^12,3 + mi.3. |
|
|
|
N 1 4 = N 1 3/723 4 -f- N 1,2/712,4 + /72і,4, |
|
|
|
|
................................................................................................... |
|
|
|
(1-9) |
Ni ,t — N i'1-іГПі'і-ц + N i,/—2/727—2,7 + |
• • • + |
N 1,2/722,1 + |
n i,i< |
|
N ifn = |
N l , n —\fnn— i , n - f - N l . n — 2/72n— 2 ,n + |
• • * |
+N \fittl2n + |
Ш\-П. |
В случае полного несимметричного графа сети, т. е. графа, каж дая пара вершин которого соединена направленной ветвью, число простых элементарных путей составляет
N* = 2П—2 |
(1.10) |
где п — число узлов сети.
В полном несимметричном графе с кратностью ветвей (числом ветвей, соединяющих общую упорядоченную пару узлов) т число
различных путей |
|
JV** = 772 (m + I)""2. |
(1.11) |
Из приведенных соотношений видно, что число различных пу тей в мультисети резко возрастает с увеличением числа ветвей с
10
общей упорядоченной парой узлов. Например, мультисеть, содер жащая десять узлов, каждая пара которых соединена десятью вет вями, имеет 2,14 • 10° вариантов различных путей из начального узла в конечный.
Наиболее простые и вместе с тем достаточно эффективные алго ритмы определения частного решения задачи о допустимых по длине путях в мультисети можно построить на основе сведения указан ной задачи к задаче определения экстремального пути с ограниче нием (1.4) и использования ее логических и экстремальных свойств. Рассмотрим один из методов, использующих такой алгоритм, ко торый назовем методом подкритических путей. Вычислительная процедура, соответствующая этому методу, состоит в следующей последовательности операций.
1. Определяется путь максимальной длины (критический путь)
Ащах- 2. Длина Атах сравнивается с допустимой длиной искомого пу
ти. При этом могут быть такие случаи:
а) А АА Ашах А -4- ДА;
б) Атах А ДА,
в) Атах А -|- ДА.
В случае а) критический путь представляет искомое частное ре шение задачи, т. е. Amax = Lx. При выполнении условия б) задача не имеет решения. Если справедливо в), то выполняется операция
всоответствии с последующим п. 3.
3.Ветвь максимальной длины, принадлежащая критическому пути, заменяется ветвью нулевой длины и определяется путь мак
симальной длины в измененной указанным образом мультйсети (пер
вый подкритический путь) Атах- 4. Если полученный подкритический путь не содержит введен
ную ветвь нулевой длины, то его длина AmL сравнивается с допу стимой длиной искомого пути. При этом может выполняться:
а) А — ДА Ашах |
А — ДА; |
|
б) Атах < |
А — ДА; |
|
в) Атах |
А -)- ДА. |
|
В случае а) Amâx = |
А*. При справедливости условия б) выпол |
|
няется операция в соответствии с п. 5. Если имеет место условие в), то выполняется операция в соответствии с п. 6.
Если указанный путь содержит введенную ветвь нулевой дли ны, то допустимые значения искомого пути следует уменьшить на первоначальную длину соответствующей ветви и осуществлять сравнение с этими величинами.
5. Восстанавливается первоначально замененная ветвь, осуще ствляется замена другой ветви максимальной длины, принадлежащей
п
критическому пути, и вновь повторяется операция, соответ ствующая п. 4. Если ни одна из замен ветвей критического пути не приведет к выполнению неравенства в), то задача не имеет решения.
6. Ветвь максимальной длины, принадлежащая первому под критическому пути, заменяется ветвью нулевой длины и определя ется путь максимальной длины (второй подкритический путь).
Далее выполняются операции, аналогичные описанным в п. 4, 5, 6 до тех пор, пока некоторый n-й подкритический путь не будет удовлетворять условию
L — AL — 8 L < L ^ l < L + A L - 8 L ,
где бL равно сумме первоначальных длин замененных ветвей, при надлежащих данному пути (если таких ветвей нет, то бL = 0). В полученном таким образом пути длйны ранее замененных ветвей (если такие есть) восстанавливаются. Процедура замены ветвей ветвями нулевой длины вместо их исключения обусловлена необхо димостью сохранения топологической связности мультисети.
Недостатком приведенного метода является то, что решение за
дачи не гарантируется при max | /*/1> 2ДL, так как при выполне-
і.І.Ь
нии операции замены ветвей длина определяемого подкритическо го пути может измениться на близкую к указанной величину. По этому данный метод не пригоден для определения пути заданной длины.
При нахождении пути допустимой длины можно использовать
признак отношения составляющих его |
ветвей |
к заданной зоне, |
||||
определяемой по границе следующими величинами: |
|
|||||
|
7\ = |
[Lmax- ( L - A L ) ] , |
|
|
||
|
r 2 = |
[(L + A L ) - L min]. |
|
(1Л2> |
||
Ветвь 4 принадлежит заданной зоне |
(7\, Т2), |
если |
справедливы |
|||
соотношения |
|
|
|
|
|
|
А т а х |
[ А т а х ( 1 і 0 |
A y " Ь А т а х (У і Ц ) ] |
|
|
||
[Amin (1>0 + J/y' + |
Amin (#. «)] — Amin < т 2, |
(1.13) |
||||
где Атах, Amin — длины максимальных |
и минимальных |
путей меж |
||||
ду начальным 1-м и і-м, у -м и конечным n-м узлами |
мультисети; |
|||||
Іц — длина ветви иц.
Соотношения (1.13) отображают следующие необходимые усло вия принадлежности данной ветви пути допустимой длины:
1)максимальная длина пути, инцидентного данной ветви, не мень ше минимальной допустимой длины искомого пути;
2)минимальная длина пути, инцидентного данной ветви, не больше максимальной допустимой длины искомого пути.
Выделение ветвей, принадлежащих заданной зоне, может поз волить, в ряде случаев, существенно уменьшить объем исходной
мультисети исключением ветвей, заведомо непригодных для по
12