Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 57 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

59
Так как минимальным является элемент
5,13)2(
1
1
=
ε
, то
соответствующий ему цикл является
начальным для второго шага
процесса
. Не включенными в цикл остаются номера:
{}
{
}
{
}
{
}
.5;34;2\5,4,3,24;2\
12
=== GG
После двух последующих шагов процесса к шагу 4=
t
получено
одно из решений (4.14). Поскольку все n активных элементов вошли в
цикл =
4
(G ∅), то процесс оканчивается, однако при этом одно из
решений (4.14) было утеряно.
Чтобы найти утерянное решение, необходимо попытаться улучшить
полученные на шаге 3=
t
пробные циклы. Для их улучшения на основе
анализа вычислительной схемы модифицированного метода расширения
цикла (табл. 21) проверим второе необходимое условие оптимальности
и его выполнение.
Ранее полученное условие – любая пара смежных индексов
полученного решения должна являться кратчайшим маршрутом
(см. раздел 2, вывод 1) – автоматически выполняется при
модифицированном методе расширения цикла. При улучшении решения
на основе указанного требования пришлось отказаться от жесткого
условия об однократном включении в решение каждого из n элементов.
Однако принудительное включение
элементов в текущий цикл, как
правило, нарушает оптимальность текущего цикла
в местах стыковки
кратчайших маршрутов
[см. формулу (4.18)]. Восстановить
оптимальность или, по крайней мере, улучшить решение можно в ряде
случаев путём
изъятия некоторых элементов из цикла. Таким образом,
появляется
новое необходимое условие оптимальности решения
обобщенной задачи: если изъятие элемента из решения не уменьшает
энергозатраты, то оно необходимо
.
Проверка этого условия поочередным пробным удалением каждого
элемента – довольно громоздкая процедура, однако количество
вычислений уменьшается, если наложить два дополнительных условия:
- удаление элемента
не должно уменьшать количество
активных
элементов в цикле;
- удаление элемента
не должно увеличивать длину цикла (а
значит, и энергозатраты).
Из первого условия следует, что проверке подвергаются только
транзитные элементы и совпадающие с ними номера активных
элементов. Из второго условия следует, что если проверяемый элемент
не нарушает структуру кратчайшего маршрута, то его не следует удалять
из цикла. Проиллюстрируем сказанное на примере.
Первый транзитный элемент появился на
шаге 1
=
t

Страницы