Cтраница 3
Это означает, что предложенный для решения первой задачи жадный алгоритм применим и здесь. Удельная стоимость каждого предмета равна 1, поэтому на этапе сортировки предметы упорядочиваются по убыванию их размеров. [31]
Из приведенных данных следует, что применение гибкого алгоритма позволяет варьировать в широких пределах время решения задачи при относительно невысоких отклонениях от оптимальных решений. Кроме того, видно, что предложенный гибкий алгоритм действительно является жадным алгоритмом и обеспечивает равномерно убывающее приращение точности вычислений в зависимости от числа итераций. Из сказанного следует, что разработанный метод и алгоритм решения удовлетворяют всем требованиям, предъявляемым к методам и алгоритмам принятия оперативных решений. [32]
Процесс включения ребер продолжаем до тех пор, пока все вершины исходного графа Г не будут включены в дерево Г о - Построенное дерево будет минимальным остовным. Доказательство того, что последовательность шагов 1 - 4 приводит к построению минимального остовного дерева, аналогично доказательству для жадного алгоритма. Реализация схемы ближайшего соседа формирования остовного дерева выполнена в алгоритме 6.9, где исходный граф Г ( X, U, Ф) представляется матрицей весов We [ w - ], веса несуществующих ребер полагаются равными - и. Под весами ребер понимаются их длины. Обновление значений векторов dist [ x ] и prev [ x ] выполняется на каждом шаге алгоритма при пополнении Х0 новой вершиной. [33]
Такая, кажущаяся на первый взгляд надуманной, задача чрезвычайно полезна в определенных комбинаторных алгоритмах; пример ее полезности мы увидим в жадном алгоритме разд. [34]
Во всех случаях мы получим оценку сложности алгоритма в виде многочлена относительно размерности задачи, что отнюдь не является типичной ситуацией для оптимизационных задач. В большой степени эффективность жадных алгоритмов вызывается тем, что элемент, один раз включенный в оптимальное решение, остается в нем до конца. [35]
Для решения многих задач ( в том числе и из класса Р) пригодны так называемые жадные алгоритмы. Эти алгоритмы пытаются сделать наилучший выбор на основе доступной информации. Напомним, что алгоритмы построения минимального остовного дерева и кратчайшего пути являются примерами жадных алгоритмов. [36]
Какое все это имеет отношение к алгоритмам о паросочетаниях. Мы видели в разд. Эта задача, в свою очередь, может быть сведена к минимизации без ограничений субмодулярной функции множества с применением алгоритма, аналогичного жадному алгоритму. [37]
Следует обратить внимание на один довольно удивительный факт. Однако же эта зависимость очень слаба: множество S зависит только от упорядочения весов отдельных элементов. В жадном алгоритме после сортировки элементов веса совершенно перестают нас интересовать. [38]
Минимум остовных деревьев графа Г ( X, U, Ф) можно найти, применяя процедуру исследования ребер в порядке возрастания их весов. Другими словами, на каждом шаге выбирается новое ребро с наименьшим весом, не образующее циклов с уже выбранными ребрами. Процесс продолжается до тех пор, пока не будет выбрано Х - 1 ребро. Рассмотренная процедура называется жадным алгоритмом. [39]
О нетривиальности этой задачи на практике уже упоминалось в § 5.1, а для разнородных, программных и аппаратных компонентов вычислительной системы проблема еще больше усложняется. Здесь важно, чтобы вес w ( e) элемента ( архитектурного признака) был инвариантен относительно будущей технической реализации. Разумеется, подобные допущения оправданы лишь при определенных условиях и на ранних стадиях выбора целевой архитектуры. Задача заключается в нахождении наибольшей по весу частичной трансверса-ли семейства X, а поскольку М ( Е, J) - матроид, то для этого можно применить жадный алгоритм. [40]
Действительно, пусть Г ( X) - множество вершин, смежных с вершинами из подмножества X С X. Рассмотрим пару М ( У, /), где / - семейство частичных трансверсалей семейства ( Vi... Следовательно, может быть применен жадный алгоритм для матроида трансверсалей. [41]
Сначала мы рассмотрим минимальные множества ребер, которые встречают не только все Т - разрезы ( так это обстоит с Т - соединения-ми), но и все разрезы. Эти множества, очевидно, являются остовными деревьями. Поскольку все остовные деревья в графе имеют одинаковое число ребер, нас будет интересовать только задача с весами. Решение получается с помощью последовательного выбора такого ребра с наименьшим весом, которое не образует цикл, если его добавить к уже выбранным ребрам. Этот алгоритм называется жадным ( см. Вставку 1C), и очень важно то, что всегда получается оптимальное остовное дерево. Оказывается, это происходит потому, что остовные деревья графа образуют базис некоторого матроида. Мы могли бы также сформулировать минимаксную теорему, но она не будет столь прозрачной, как описанный выше жадный алгоритм. [42]