Жадные» алгоритмы решения задачи о ранце

Среди приближенных методов решения задач ДО выделяются так называемые «жадные» алгоритмы (greedy algorithms), которые можно трактовать как дискретные аналоги градиентных методов. В жадном алгоритме всегда делается выбор, который кажется самым лучшим в данный момент — т.е. производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи.

Рассмотрим задачу о ранце (см. главу 1) вида:

при ограничениях

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

.

Идея жадного алгоритма для задачи о ранце состоит в последовательном отборе предметов с наибольшей удельной полезностью до тех пор, пока позволяет вместимость ранца. Формально, алгоритм начинает работу с допустимого решения x = (0, …, 0) и последовательно заменяет нули единицами в порядке невозрастания отношений (т. е. слева направо); при этом каждый раз проверяется допустимость текущего частичного решения, в результате получим «жадное» решение и

Пример.

при ограничениях

Поскольку то жадное решение имеет вид

Примерами жадных алгоритмов могут также служить алгоритмы поиска минимальных остовных деревьев (см. главу 4), алгоритм Дейкстры (Dijkstra) для определения кратчайших путей из одного источника и эвристический жадный подход (Chvatal) к задаче о покрытии множества.

[1] Дробной частью некоторого числа а, называется наименьшее неотрицательное число b такое, что разность между а и b есть целое число.