§ 57. Понятие k-оптимальности

Пусть конечное множество решений комбинаторной задачи. Связывая с каждым решением число приходим к разбиению на классы эквивалентности, каждый из которых состоит из решений с одним и тем же Эти классы можно упорядочить, и мы изложим алгоритм получения первых классов для последовательного графа (§ 53) со значением на дугах.

Предварительно введем определения.

Пусть

— конечное множество, упорядоченное числовой функцией

Назовем подмножество -максимальным подмножеством, или -максимальным классом, если

подмножество назовем -максимальным, или -максимальным классом, если

подмножество назовем -максимальным, или -максимальным классом, если

Элемент называют -максимальным.

Очевидно, что при некотором подмножества дают разбиение

Аналогично можно определить -минимальные подмножества.

Называют -оптимумом -максимумом или -минимумом) множества действительных чисел такое число что

(число является по величине среди всех и записывают

Полагают

если (знак «плюс» относится к opt = min, знак «минус» — к opt = max).

Рассмотрим числовую функцию от действительных переменных и параметра

где

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

Для каждого зададимся областью Для получения -оптимального подмножества в нужно вычислить -оптимум функции (57.9):

и найти -выборки , для которых совпадает с (57.11).

-выборка совместимая с (57.10), представляет путь в последовательном графе, -выборка совместимая с (57.10), представляет подпуть в последовательном графе.

Подпуть называют -оптимальным путем из до вершин уровня, если он принадлежит -оптимальному подмножеству множества путей, выходящих из

Беллман и Калаба дали метод, состоящий в последовательном вычислении

Этот метод основан на следующей теореме.

Теорема о -оптимальности. Подпуть образованный последними компонентами -оптимального пути является -оптимальным путем из до вершин уровня для некоторого

Доказательство проведем от противного. Пусть -оптимальный путь с Тогда найдутся подпутей из до вершин уровня, все значения которых различны и «лучше», чем Добавляя каждый из этих подпутей к первым компонентам пути (что можно сделать, так как граф последовательный), получаем путей, все значения которых различны и «лучше», чем Это противоречит -оптимальности

Чтобы получить -оптимальные пути от до вершин уровня, по доказанной теореме достаточно рассмотреть -оптимальные подпути из до вершин уровня. Если при некотором множество -оптимальных подпутей пусто, то формулы (57.12) и (57.13) остаются справедливыми в силу (57.8).

Из рассмотрения формулы (57.13) следует, что для отыскания -оптимума достаточно рассмотреть множество А мощности где — мощность Однако заметим, что элементов из А, отвечающих заданному (полагая последовательно в (57.13)), можно упорядочить. В силу этого достаточно разыскивать -оптимум в некотором множестве мощности

Положим

Последовательно вычисляем при , при всех и при

где

и

Итак, для каждого и для получаем: значение -оптимального пути от до вершин уровня, равное

множество -оптимальных путей от до вершин уровня (с помощью (57.20)).

Справедливость формул (57.17) — (57.20) следует из сравнения с (57.12) и (57.13); отличие следующее:

а) вместо -оптимума ищем -оптимум, предварительно исключая -оптимумы

б) для отыскания -оптимума можно использовать лишь один элемент А для каждого (выбрасывая заведомо неоптимальные).

Этот алгоритм легко запрограммировать для ЭВМ. Полезно отметить, что:

а) для более простого описания графа иногда бывает удобно добавить фиктивные вершины и приписать всем дугам, не фигурирующим в первоначальном графе, значение

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

Рис. 377.

Пример. Рассмотрим последовательный граф на рис. 377 (из А исходит 24 пути, а из путь). Найдем -минимальные пути с . Имеем

Удобно составить матрицу значений подпутей из до вершин уровня (см. столбец (6) в таблице В столбцах (3) и (5) приведены соответственно окончательные и промежуточные результаты вычислений по данному методу. Пр и вычислениях вручную к индикатору можно не обращаться.

На рис. 378 представлены -минимальные пути . Для большей наглядности некоторые вершины заменены вершинами Множество определяет тогда дуги -минимального пути из На рис. 379 некоторые -минимальные пути выделены.

Заметим также, что:

1) если ищут -оптимальные пути из в фиксированную вершину уровня, то при использовании изложенного метода не учитывают дуги

(кликните для просмотра скана)

(кликните для просмотра скана)

Продолжение (см. скан)

2) если уровень содержит единственную вершину, то переходят к графу, получающемуся из исходного изменением направления всех дуг;

3) при отыскании -оптимальных путей из вершин нулевого до вершин уровня можно к исходному графу добавить вершину соединить ее со всеми вершинами нулевого уровня дугами со значением 0 и найти -оптимальные пути от до вершин уровня.

Задачу об отыскании -оптимальных путей в произвольном графе во многих случаях можно свести к аналогичной задаче для последовательного графа, хотя это сведение не всегда легко осуществить.

УПРАЖНЕНИЯ

(см. скан)