Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Алгоритм 3





Алгоритм 1.

begin

while (|E| >1) do

begin

for (iÎE) do

if (|V ' +(i)| + |V ' -(i)| = 1) then { т.е.вершина i – концевая на

дереве G}

begin

if (|V' +(i)| = 1) then

for (vÎV' +(i)) do

begin

x(v):=b(i);

b(h1(v)):=b(h1(v))+x(v);

end;

if (|V' -(i)| = 1) then

for vÎV' -(i) do

begin

x(v):= -b(i);

b(h2(v)):=b(h2(v))-x(v);

end;

удаляем из графа G'=<E, V', H> вершину i и инцидентную ей дугу.

end;

end;

end.

Замечание 6.1.

В результате работы алгоритма может получиться недопустимое решение, т.е. для некоторых vÎV x(v)<0. В этом случае следует сменить исходное базисное дерево. Однако это не гарантирует, что на нем будет получено допустимое решение.

Далее будет описан алгоритм, позволяющий либо определить базисное дерево допустимым решением, либо доказать, что его не существует.

Будем считать, что исходное базисное дерево G’ найдено, и для vÎV' определены x(v)>0.

Для того чтобы определить, является ли полученное решение оптимальным, воспользуемся следующим критерием оптимальности.

 

6.2. Критерий оптимальности

 

Пусть x(v), vÎV - такое решение задачи (6.1 – 6.3), что для vÎV\V' x(v)=0 и для vÎV' x (v)³ 0. Это решение оптимально тогда и только тогда, когда существуют числа u(i), iÎE называемые потенциалами такие что

u(h2 (v))=u(h1 (v))+c (v) vÎV' (6.4)

u(h2 (v))£ u(h1 (v))+c(v) v Î V\V' (6.5)

Для определения потенциалов применяется следующий алгоритм:

 

Алгоритм 2.

begin

для произвольной (только одной) вершины iÎE u(i):= 0;

M1:

найти дугу vÎV' для которой известен

потенциал только одной из ее вершин

если такой дуги нет то конец работы

алгоритма иначе

begin

определяем неизвестный потенциал

вершины дуги v из уравнения

u(h2))=u(h1(v))+c(v);

goto M1

end;

end;

Для проверки критерия оптимальности найденного решения используется алгоритм:

Алгоритм 3.

1. Среди всех дуг vÎV\V' ищем дугу v0 такую, что u(h2(v0)) > u(h1(v0)) +(v0).

2. Если такой дуги нет, то исходная задача (6.1-6.3) решена, иначе следует выполнить алгоритм 4 перехода к новому базисному дереву.

 

Date: 2015-05-09; view: 419; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию