Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
§ 57. Понятие k-оптимальностиПусть Предварительно введем определения. Пусть
— конечное множество, упорядоченное числовой функцией
Назовем подмножество
подмножество
подмножество
Элемент Очевидно, что при некотором Аналогично можно определить Называют
(число
Полагают
если Рассмотрим числовую функцию от
где
Для каждого
и найти
Подпуть Беллман и Калаба дали метод, состоящий в последовательном вычислении
Этот метод основан на следующей теореме. Теорема о Доказательство проведем от противного. Пусть Чтобы получить Из рассмотрения формулы (57.13) следует, что для отыскания Положим
Последовательно вычисляем при
где
и
Итак, для каждого множество Справедливость формул (57.17) — (57.20) следует из сравнения с (57.12) и (57.13); отличие следующее: а) вместо б) для отыскания Этот алгоритм легко запрограммировать для ЭВМ. Полезно отметить, что: а) для более простого описания графа иногда бывает удобно добавить фиктивные вершины и приписать всем дугам, не фигурирующим в первоначальном графе, значение б) изложенный алгоритм практически столь же эффективен, что и алгоритм Беллмана
Рис. 377. Пример. Рассмотрим последовательный граф на рис. 377 (из А исходит 24 пути, а из
Удобно составить матрицу значений подпутей из На рис. 378 представлены Заметим также, что: 1) если ищут (кликните для просмотра скана) (кликните для просмотра скана) Продолжение (см. скан) 2) если 3) при отыскании Задачу об отыскании УПРАЖНЕНИЯ(см. скан)
|
1 |
Оглавление
|