Наивный/жадный/перечисляющий алгоритм

Наивный алгоритм

А алгоритм naif стремится обеспечить базовый результат проблемы. Наивный метод не делает никаких предварительных расчетов и использует только исходные данные задачи.

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

за я из 1 в нет
   если w[i] + w_conso ≤ W тогда
      х[i]:= 1 w_conso:= w_conso + w[i]
   в противном случае
      х[я] := 0
   конец, если
конец для 

Жадный алгоритм (интуитивный метод)

Как и наивный алгоритм, так называемый жадный алгоритм построен по простому принципу: во время итерации алгоритм всегда принимает решение о «наилучшем выборе». Поэтому нам нужен локально оптимальный выбор с целью, чтобы этот выбор привел к глобальному оптимальному решению. Однако алгоритм не дает гарантии, что последнее решение является оптимальным.

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

Для этого рассмотрим Икс и ж векторы выбора объекта и его веса, отсортированные по убыванию эффективности (эффективность = полезность/вес). Тогда алгоритм работает как наивный метод.

Простой пример позволяет понять, что этот выбор не всегда оптимален: возьмем объект размером 1 и полезность 2, а также объект размером и полезностью, равным размеру сумки. В этих условиях первым будет выбран первый объект с наибольшей полезностью. Больше нет места для размещения второго объекта. Оптимальным решением будет выбрать только второй предмет в мешке.

Перебор или перечисление

В отличие от наивного алгоритма, этот метод гарантирует глобальный оптимум, но время его выполнения и потребление памяти могут быстро выйти за пределы ПК. Принцип прост, вы должны перечислить все возможные решения проблемы и выбрать лучшее решение.

Как правило, дерево решений представлено, как следует из названия, в виде дерева. Рассмотрим пример задачи о рюкзаке с четырьмя объектами со следующими параметрами и размером сумки 30:

объект
1
2
3
4
у_и
7
3
4
3
w_i
13
8
12
10

Дерево строится по итерации: на каждой итерации новые листья показывают, брать ли следующий объект или нет. Получаем следующее бинарное дерево:

наивный алгоритм жадный алгоритм перебор грубой силы

Топы красного цвета превышают максимальный размер сумки, топ фиолетового цвета — оптимальное решение. Как вы можете заметить, количество листов равно 2(n-1) для объекта нет. Таким образом, количество узлов, сгенерированных до объекта n, равно 2.нет -1.

Делиться
ru_RURU
%d такие блоггеры, как: