Последовательный анализ

При достаточно большом количестве вариантов решения выбор оптимального простым перебором затруднителен, а в ряде случаев практически невозможен. Для сокращения перебора количества проекти­руемых вариантов применяются следующие методы: отсечения (последо­вательный анализ), Порето, ветвей и границ.

Отсечение бесперспективных вариантов в процессе их последова­тельной генерации выполняется методом последовательного анализа, основанном на правиле доминирования. При этом i -й вариант решения предпочтительней j -ого, если взвешенная сумма показателей i -го варианта больше суммы показателей j -го. В результате бесперспективным оказывается построение новых вариантов решения на основе пока­зателей j -го варианта.

Схема решения такова. Пусть на (K-I) шаге поиска решений опре­делено множество перспективных вариантов , каждый из которых характеризуется К параметрами. На очередном К-м шаге поиска каждый из полученных ранее перспективных вариантов x_i ^{( K- 1)} используется для построения новых вариантов решения, число которых составит n - K, где n - число вершин древовидного графа.

Построение выполняется добавлением к x_i ^{( K- 1)} одного из еще не вошедших в этот вариант номеров вершин, при этом новые варианты характеризуются (К+1)-ми параметрами. В результате получаем расширенное
множество вариантов

x_K = { x₁ ^{( K )}, x₂ ^{( K )}, …, x_{l ( n-K )}^{( K )} }.

Сгруппируем варианты из x_K, заканчивающиеся одним и тем же номером вершины древовидного графа и с одинаковым множеством входящих в последовательность номеров. Используя правило доминирования, выделим в каждой такой группе по одному наиболее предпочтительному варианту. Выбранные варианты образуют множество перспективных вариантов после К-го шага поиска. В дальнейшем процедура повторяется до тех пор, пока на n -м шаге из множества вариантов не будет выделен единственный оптимальный.

Использование метода последовательного анализа показано на примере ярусного графа (рис.5.1), что соответствует выбору кратчайшего замкнутого маршрута от первой вершины к этой же вершине.

Рис.5.1. Древовидный граф решений задачи о кратчайшем замкнутом маршруте

Для параметров ветвей перехода выбираем значения:

C_I2 = C_2I = 9; C_I3 = C_3I = I0; C_I4 = C_4I = 4;

С₂₃ = С₃₂ = 6; С₂₄ = С₄₂ = 8; С₃₄ = С₄₃ = 7;

Применяя метод последовательного анализа после 2-го шага поиска, когда три начальных варианта решения принимаются перспективными, получаем решение задачи, сведенное в таблицу. Данные таблицы говорят о том, что вариант 1, 4, 3, 2, 1 является оптимальным.

Таблица 9.1.

Решение задачи о кратчайшем маршруте методом

последовательного анализа

Реализация метода позволяет сократить количество просматриваемых вариантов по сравнению с полным перебором примерно в ! раз.