vm принадлежит выбранному маршруту. Тогда задача может ставиться так. Найти путь в графе достижимости, требующий наименьших затрат памяти:
J1* = min J1
минимум ищется по всем возможным путям.
По критерию быстродействие:
J2 = TIM(ui) , i=1,2,...,k
ui принадлежит выбранному маршруту. Тогда задача формулируется так. Найти путь в графе достижимости, требующий наименьших затрат времени.
J2* = min J2
минимум ищется по всем возможным путям.
По критерию память:
J3 =!!Е!!x
Здесь требуется найти путь в графе достижимости, дающий наименьшую ошибку:
J3*= min J3
минимум ищется по всем возможным путям.
Если рассматривать интегральный критерий, объединяющий все три критерия, то задача имеет следующую постановку. Пусть С1,С2,
С3 - веса соответствующих критериев, указанные экспертом. Тогда требуется минимизировать по всем возможным путям:
-J1¬
I = (C,J) = (C1,C2,C3) ¦J2¦ = C1J1 + C2J2 + C3J3
LJ3I* = min I, минимум ищется по всем возможным маршрутам.
3.3.3. Решение оптимизационной задачи.
Решение задачи оптимизации начинается с вычисления весов дуг и вершин выделенного подграфа сокращенного графа достижимости. Если выбран интегральный критерий, то рассчитываются все веса дуг и вершин для составляющих этого критерия с учетом веса. Расчет происходит также с учетом размерности задачи, о чем упоминалось ранее. Вес вершины считается как
С1 * MEM(Vm).
Вес дуг считается как:
C2 TIM(um) + C3 Em.
Если С1 = 0 и при этом С2*C3 = 0, то вершины расщепляются следующим образом:
вершине vm ставится в соответствие две вершины vm' и vm" и дуга um'. При этом множество входящих дуг в vm становится входящими в vm'; множество выходящих - выходящими в vm". Дуга
um' является единственной выходящей дугой из vm' и единственной входящей дугой в vm". Вес вершин vm' и vm" равен нулю, а вес дуги um' равен весу вершины vm (рис. 3.3). Таким образом, задача оптимизации на графе сводится к задаче отыскания кратчайшего пути в графе достижимости между двумя классами вершин: классом вершин графа с весами, покрываемыми начальной маркировкой Мо и классом вершин с весами, покрывающими конечную маркировку Мt.
Введем в сокращенный граф достижимости две вершины vs и vt
с (рис. 3.4). Соединим вершины с весами, покрываемыми начальной маркировкой Мо с vs, а с весами, покрывающими конечную маркировку Мt с vt дугами. Вес каждой дуги
u также . Задача становится задачей нахождения кратчайшего пути между двумя вершинами (vs-vt) в ориентированном графе с весами. Решение этой задачи известно и рассмотрено в
[32] и [37]. Этот алгоритм предложен Дейкстрой в конце 50-х годов. В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от s к этой вершине. Эти пометки (их величины) постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине. Опишем этот метод подробно. Алгоритм Дейкстры (сij > 0):
пусть l(xi) - пометка вершины xi
Присвоение начальных значений.
Шаг 1. Положить l(s)=0 и считать эту пометку постоянной.
Положить для всех и считать эти пометки временными. Положить p=s.
Обновление пометок.
Шаг 2. Для всех , пометки которых временные, изменить пометки в соответствии со следующим выражением:
l(xi) <-- min [l(xi),l(p) + c(p,xi)].
Превращение пометки в постоянную.
Шаг 3. Среди всех вершин с временными пометками найти такую, для которой l(x*i) = min [l(xi)].
Шаг 4. Считать пометку вершины x*i постоянной и положить
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.