Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

([pic]),

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

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

(C(() = С(() +[pic], (1)

(B(() = В (() +[pic] + min cj , (2)

(A(() = A (() +[pic] + [pic] (3) где J (() — множество символов, образующих последовательность (.

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

((() = max {(A((), (B ((), (C (()}. (4)
Тогда ход решения задачи трех станков можно представить следующей формальной схемой.

Нулевой шаг. Задание множества G(0), образуется всеми возможными последовательностями (( = 0).
Вычисление оценки для множества G0: где ((0) = max {(A(0), (B (0), бC (0)},

[pic]; [pic]; [pic].

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

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

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

(((k) = max {(A((k), (B ((k), (C ((k)}; k = 1, n.

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

(((k(1))=min (((j(1)).

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

Вычисление оценок производят в соответствии с соотношениями (1), (2),
(3). k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты (1(k), (2(k) ,…,(vk(k), а именно подпоследовательности длиной k.

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

(((s(k))=min (((j(k)).

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

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

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

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

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

Рекомендуем скачать другие рефераты по теме: реферат на тему русские, реферат охрана.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата