|
путь в сети, соединяющ ей начальную верш ину с одной из конечны х. Значение координаты по второй оси равно сум марном у весу предметов. П рим ем длины горизонтальных д уг равными О, а длины наклонны х равны ми ценности соответствующ его предмета. В этом случае длина пути, соединяю щ его начальную верш ину с одной из конечны х, равна суммарной ценности соответствую щ его набора предметов. Таким образом, задача свелась к определению пути, им ею щ его максимальную длину. П уть максимальной длины выделен на Рис. 1.7 толстыми дугами. М етод динамического программирования м ож но представить в д р уго й э квивалентной форме, удобной для сравнения его с методом дихотом ического программирования. Эта форма не требует построения сети, а использует матричный способ вычислений рис. 1.8. Первая матрица соответствует второму слою сети рис. 1.7. В верхней половине каж дой клетки указана величина веса для различных вариантов из двух первых предметов, а в ниж ней соответствующая ценность. Вторая матрица соответствует третьему слою, а третья —четвертому. Если в матрице имеется несколько клеток с одинаковы ми весами, то в следую щ ую матрицу для этого значения веса берется максимальное значение ценности. Это и есть принцип оптимальности Беллмана для м атричного представления метода динамического программирования. В последнем столбике рис. 1 .8 приведены оптимальные значения суммарной ценности предметов при лю бы х ограничениях на вес ранца. М етод динамического программирования является эфф ективным методом решения некоторы х задач дискретной оптимизации, сущ ественно сокращая перебор. Так, например, для рассмотренной задачи о ранце при целочисленных значениях весов предметов объем вы числений пропорционален числу верш ин сети, то есть не более чем R^n. П ри заданном R объем вы числений растет пропорционально п, что свидетельствует о вы сокой эф ф ективности метода. К сожалению, метод динамического программирования применим к ограниченному классу задач. 59 |
щие четырем возможным вариантам для двух предметов. Продолжая таким образом, получим сеть, приведенную на Рис. 1.7. Рис. 1.7. Очевидно, что любой путь в сети, из начальной вершины О в одну из конечных вершин соответствует некоторому набору предметов. И наоборот, любому набору предметов, суммарным весом не более 6 однозначно соответствует путь в сети, соединяющей начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному весу предметов. Примем длины горизонтальных дуг равными О, а длины наклонных равными ценности соответствующего предмета. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, равна суммарной ценности соответствующего набора предметов. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на Рис. 1.7 толстыми дугами. Метод динамического программирования можно представить в другой эквивалентной форме, удобной для сравнения его с методом дихотомического программирования. Эта форма не требует построения сети, а использует матричный способ вычислений рис. 1.8. Первая матрица соответствует второму слою сети рис. 1.7. В верхней половине каждой клетки указана величина веса для различных вариантов из двух первых предметов, а в нижней соответствующая ценность. Вторая матрица соответствует третьему слою, а третья —четвертому. Если в матрице имеется несколько 51 клеток с одинаковыми весами, то в следующую матрицу для этого значения веса берется максимальное значение ценности. Это и есть принцип оптимальности Беллмана для матричного представления метода динамического программирования. В последнем столбике рис. 1.8 приведены оптимальные значения суммарной ценности предметов при любых ограничениях на вес ранца. Метод динамического программирования является эффективным методом решения некоторых задач дискретной оптимизации, существенно сокращая перебор. Так, например, для рассмотренной задачи о ранце при целочисленных значениях весов предметов объем вычислений пропорционален числу вершин сети, то есть не более чем R^n. При заданном R объем вычислений растет пропорционально п, что свидетельствует о высокой эффективности метода. К сожалению, метод динамического программирования применим к ограниченному классу задач. У2 6 / / 9 10Х / 1 4 X X 9 / / 1 2 А / / ь 4 / / 6 8 Х / И %X 7 / / 1 0 X X 6 / / 8 X 1/ / / 2 5 / / 7 0 / X 0 0 / / о 4 / / 5 у / ХХ4 0 / Х О X 12 1о Рис. 1.8. Подводя итоги краткого обзора основных методов решения задач дискретной оптимизации отметим, что к точным методам решения (или к 52 |