10.5. “Жадные” алгоритмы

Для решения оптимизационных задач можно использовать класс алгоритмов, называемых “жадными”. В таком алгоритме на каждом шаге делается локально оптимальный выбор, в предположении, что итоговое решение окажется оптимальным. В общем виде, это не верно, но для многих оптимизационных задач такие алгоритмы позволяют получить локальный оптимум, а в частном случае - глобальный оптимум.

Рассмотрим стандартную задачу (Кормен, Лейзерсон, Ривест) о выборе заявок. Пусть даны n заявок на проведение занятий в одной и той же аудитории. Два разных занятия не могут проводиться в одно время. В каждой заявке указаны начало и конец занятия (s_i и f_i для i-той заявки). Разные заявки могут пересекаться, и тогда можно реализовать только одну из них. Каждая заявка отождествляется с промежутком [s_i, f_i], так что конец одного занятия может совпадать с началом другого, и это не считается пересечением. Целевая функция задачи заключается в наборе максимального количества совместных друг с другом заявок при временных ограничениях и граничных условиях. Жадный алгоритм работает следующим образом. Предполагаем, что заявки упорядочены в порядке возрастания времени окончания, т.е., f₁ ≤ f₂ ≤ …  f_n. Заявки с одинаковым временем конца располагаем в произвольном порядке. Тогда запишем псевдокод алгоритма, приведенный в учебнике (Кормен, Лейзерсон, Ривест):

ВЫБОР ЗАЯВОК (s, f - массивы)

1 n ← length [s]

2 А ← {1}

3 j ← 1

4 for i ← 2 to n

5 do if s_i ≥ f_j

6 then A ← A  {i}

7 j ← i

8 return A

Множество А состоит из номеров выбранных заявок, j – номер последней из них; при этом f_j = mах{f_k : kA}, поскольку заявки отсортированы по возрастанию времени окончания. Вначале А содержит заявку номер 1, и j = 1 (строки 2 - 3). Далее (цикл в строках 4 - 7) ищется заявка, начинающаяся не раньше окончания заявки номер j. Если таковая найдена, она включается в множество А и переменной j присваивается ее номер (строки 6 - 7). Описанный алгоритм выбора заявок требует всего лишь O(n) шагов (не считая предварительной сортировки). Как и подобает жадному алгоритму, на каждом шаге он делает выбор так, чтобы остающееся свободным время было максимально.

Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение.

Отметим, что задачи, решаемые с помощью жадных алгоритмов, должны обладать свойством оптимальности для подзадач. А именно, оптимальное решение всей задачи содержит в себе оптимальные решения подзадач.

10.6. Нечеткие (расплывчатые) алгоритмы

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

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

1-я группа — назначающие инструкции. Например, х = “большой” или х = “вкусный”.

2-я группа — расплывчатые высказывания. Например, если х — “очень дорогой”, то перейти к y, или если х “не помещается в комнате”, то “увеличить размер комнаты”.

3-я группа — безусловные активные предложения. Например, “немного увеличить” х, или “сильно увеличить” х, или перейти к другому значению параметра x.

Отметим, что все инструкции могут быть нечеткими или четкими.

Нечеткие алгоритмы определения — это конечное множество инструкций, определяющих расплывчатое множество в терминах других расплывчатых множеств или дающих метод для определения степени принадлежности каждого элемента для определяемого множества. Алгоритмы идентификации устанавливают степень принадлежности элементов множеству. Алгоритмы порождения используются для порождения новых, а не для определения данных расплывчатых множеств. Примерами таких алгоритмов могут служить алгоритмы сочинения стихов, конструирования ЭВА, разработки технических заданий на изделие. Нечеткие алгоритмы, используемые для описания поведения произвольной системы, называются бихевиористическими.

Расплывчатой переменной считают кортеж П = <, X, >, где  — наименование расплывчатой переменной; X = {x₁, х₂, ..., х_n} — область ее определения; A = { (x_i) | x_i} x_i  X — расплывчатое множество в X, определяющее ограничения на возможные значения П. Лингвистической переменной называют кортеж Л = <, Т, X>, где  — наименование Л; Т — множество ее значений, представляющих наименования П, областью определения которых является X.

Например, пусть оценивается качество технологического процесса выхода годных с помощью понятий “плохой”, “средний”, “хороший”. Максимальный выход годных 80%. Тогда Л = <качество, Т, [0; 80]>, где Т = {“плохой”, “средний”, “хороший”}. Значения Л описываются расплывчатыми переменными. Например, значение “плохой” описывается расплывчатой переменной < плохой, [0; 80], >, где может иметь вид = {< 1 / 0 >, < 0,8 / 5 >,< 0,6 / 7 >,< 0,2 / 20 >}. Значение “хороший” можно, например, описать так: < хороший, [0; 80], >, где = {< 1 / 80 >, < 0,8 / 75 >, <0,6 / 70 >,< 0,2 / 40 >}.

Функцию принадлежности при наличии k экспертов упрощенно определяют так. Пусть k₁ экспертов на вопрос о принадлежности х  Х к отвечают положительно, а k₂ = k — k₁ экспертов на этот же вопрос отвечают отрицательно. Тогда устанавливают следующее значение функции принадлежности: (x_i) = k₁ / {k₁ + k₂). Для точных оценок приводят парные сравнения функций принадлежности и др. Лингвистические переменные используют для построения расплывчатых моделей и алгоритмов.

Например, приведем нечеткий алгоритм. Пусть у — быстродействие системы, состоящей из двух ЭВМ, а х — быстродействие одной ЭВМ в системе.

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

1°. Если х “мало” и х “незначительно увеличить”, то у “незначительно увеличится”.

2°. Если х “мало” и х “значительно увеличить”, то у “увеличится значительно”.

3°. Если х “велико” и х “увеличить значительно”, то у “увеличится очень значительно”.

Заметим, что значения расплывчатых условных предложений в этом алгоритме можно определить, если даны значения первичных терминов «большой», «маленький» и расплывчатых терминов «незначительно», «значительно», «очень значительно». Значения указанных терминов субъективны и зависят от носителя нечеткого множества. Например, если четкое множество X = {1, 2, 3, …, 10}, то при x = 9 мы имеем, скорее всего, термин «большой». Если четкое множество X = {1, 2, 3, …, 1000}, то при x = 9 мы имеем, скорее всего, термин «маленький».

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

Рис. 10.18. Структурная схема нечеткого алгоритма «Трассировка»

Эту структурную схему (рис. 10.18) можно представить в виде следующих нечетких инструкций:

1°. Сделать шаг трассировки. Если не трассируется “большое” число связей, то перейти к 1°.

2°. Если не трассируется “небольшое” число связей, то сделать “малый” шаг и перейти к 2°.

3°. Если не трассируется “очень маленькое” число связей, то сделать “очень маленький шаг” и перейти к 3°.

4°. Конец работы алгоритма.

Рассмотрим пример размещения БИС на подложке. Структурная схема одного из возможных алгоритмов такого типа показана на рис. 10.19. В терминах нечетких высказываний структурная схема алгоритма может быть переведена в расплывчатые инструкции.

Рис. 10.19. Структурная схема расплывчатого алгоритма размещения

Следует отметить, что конструктор хорошо оперирует расплывчатыми понятиями «большое», «маленькое», «очень маленькое» и эффективно реализует данный алгоритм в интерактивном режиме связи с ЭВМ. При определении степени принадлежности можно формализовать алгоритм и реализовать его на ЭВМ. Отметим, что операция «сделать шаг» в алгоритме (рис. 10.18) может быть сложным алгоритмом перетрассировки всего кристалла или небольшой его области, или простого удаления нескольких трасс и т.п. Реальные варианты нечетких алгоритмов представляют сложную структуру и необходимо разбиение его на части меньшей размерности. Важным в разработке и применении таких алгоритмов является то, что они могут служить эффективным средством распространения и изучения опыта пользователя.