А (s) £ А (), В (s) £ В (), С (s) £ С (),

причем хотя бы одно из них выполняется как строгое неравенство.

Способ конструирования вариантов после- довательностей s и вычисления оценок D(s) для каждого из них состоит в следующем.

Пусть имеется начальная подпоследовательность s. Тогда вычисляются величины:

dC(s) = С(s) +, (1)

dB(s) = В (s) + + min cj , (2)

dA(s) = A (s) + + (3)

где J (s) — множество символов, образующих последовательность s.

За оценку критерия С (s) для варианта s можно принять величину

D(s) = max {dA(s), dB (s), dC (s)}. (4)

Тогда ход решения задачи трех станков можно представить следующей формальной схемой.

Нулевой шаг. Задание множества G(0), образуется всеми возможными последовательностями (s = 0).

Вычисление оценки для множества G0:

где D(0) = max {dA(0), dB (0), бC (0)},

; ; .

Первый шаг.Образование множеств G1(1) U G1(2) U . …G1(n).

Подмножество Gk определяется всеми последовательностями с началом ik(k — 1, .,n ).

Вычисление оценок. Оценку для последовательности sk определяют из соотношения (4), т. е.

D(sk) = max {dA(sk), dB (sk), dC (sk)}; k = 1, n.

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

D(sk(1))=min D(sj(1)).

Ветвление. Выбрав наиболее перспективный вариант последовательности sk(1), развивают его построением всех возможных подпоследовательностей длиной 2 с началом sk(1) вида sk+1(2)= (sk(1), j), где j не входит в sk.

Вычисление оценок производят в соответствии с соотношениями (1), (2), (3).

k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты s1(k), s2(k) ,…,svk(k), а именно подпоследовательности длиной k.

Выбираем самый перспективный вариант sS(k) такой, что

D(ss(k))=min D(sj(k)).

Множество Gs(k) разбиваем на (п — k) подмножеств, каждое из которых образуется добавлением к последовательности ss(k) некоторого элемента ik+1 такого, что ik+1.

Оценка определяется в соответствии с соотношениями (1) — (4).

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G1(1), G2(1) ., Gn(1) соответствуют последовательностям длиной 1, т. е. s1(1) = 1, s2(1) = 2, ., sn(1) = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины п.

Признак оптимальности. Если sv(n) отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то sv(n) — искомый вариант, иначе переходим к продолжению варианта с наименьшей оценкой.

Пример 6. Рассмотрим задачу .трех станков, условия которой приведены в табл. 1:

Таблица 1

Нулевой шаг. s = 0.

dA(s = 0) = A(0) + + = 0 + 14 + 3 = 17;

dB(s = 0) = В(0) + + min cj = 0 + 15 + 2 = 17;

dC(s = 0) = С(0) + =14 .

Тогда

∆ (s = 0) = max {17, 17,14} = 17.

Первый шаг. Конструируем все возможные последовательности длиной 1

s1(1) = 1; s2(1) = 2; s3(1) = 3; s4(1) = 4; s5(1) = 5.

Находим

dA(1) = A1 + + = 14 + 3 = 17;

dB(1)(s = 0) = В1 + + = 5 + 12 + 2 = 19;

dC(1) = С1 + = 9 + 10 = 19 .

Откуда ∆ (1) = max {17, 19, 19} = 19.

Аналогично определяем ∆ (2), ∆ (3), ∆ (4), ∆ (5).

Второй шаг. Среди множества подпоследовательностей длиной 1, s1(1) = 1, s2(1) = 2, ., s5(1) = 5 выбираем наиболее перспективную s = 1, для которой величина оценки-прогноза ∆ (s) оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2), (1.3), (1.4), (1.5).

Для каждого из этих вариантов вновь определяем оценки по формулам (1) — (4).

Процесс вычислений продолжаем аналогично.

Процесс построения дерева вариантов приведен на рис. 1.

Каждой конечной вершине дерева вариантов будет отвечать полная последовательность s = i1,i2,,.in. Если для некоторой такой вершины величина оценки ∆ (s) не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой.

Конечная вершина определяет вариант (последовательность) = 3, 1, 5, 2, 4 с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.