Экстремальные комбинаторные задачи

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

1) Задача коммивояжера: заключается в отыскании самого выгодного маршрута, проходящего через указанные города точно по одному разу с последующим возвратом в исходный город.

2) Задача о рюкзаке. Постановка задачи следующая. Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность, и есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.

3) Задача о назначениях - задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей при условии взаимно однозначного соответствия между множествами работ и исполнителей.

4) Задачи теории расписаний. В этих задачах требования обслуживаются приборами и нужно составить такие перестановки обслуживания требований, которые были бы оптимальными по тому или иному критерию.

Для некоторых задач существуют полиномиальные алгоритмы.

Пример.

Рассмотрим следующую задачу теории расписаний. Пусть на приборе нужно обслужить n требований, для каждого из которых известны время обслуживания его на этом приборе и приоритет (вес) этого требования и нужно построить перестановку, в которой значение функции принимает минимальное значение (­ – момент завершения обслуживания требования i). Искомую перестановку можно получить сортировкой требований по невозрастанию отношения веса к длительности обслуживания, т.е. в ней выполняются неравенства .

Большинство задач являются NP-трудными. Для их решения используются эвристические, приближенные алгоритмы и алгоритмы сокращенного перебора.

Рассмотрим эвристический (жадный) алгоритм решения задачи о рюкзаке.

Пример.

Этот алгоритм не всегда дает точное решение.

Пример.

Грузоподъемность 9

Веса 6, 5, 4

Стоимости 24, 19, 14

24/6 > 19/5 > 14/4

Согласно алгоритму в рюкзак нужно положить предмет в весом 6. Однако очевидно, что в этом случае нужно положить в рюкзак предметы с весами 5 и 4.

Дата добавления: 2014-01-15