Приближенные алгоритмы для задачи об упаковке в контейнеры

Задача «об упаковке в контейнеры»

Пусть имеется набор предметов с весами: а(1)…а(n); a(i)€ [0,1]. Задача заключается в том, чтобы разместить эти n предметов в контейнеры, так чтобы суммарный вес предметов в одном контейнере не превышал 1 и число контейнеров было минимальным.

Данная задача является NP-полной.

 

1. Первый подходящий.

Последовательность предметов рассматривается по порядку и каждый очередной предмет пытаемся поместить в один их использованных контейнеров. Если предмет поместить нельзя, то используем новый контейнер.

Пример:

А1:

Вес: 0,3 0,5 0,3 0,3 0,3 0,6

К1: 0,3 0,5

К2: 0,3 0,3 0,3

К3: 0,6

Утверждение: для любых х: А1(х)<=1,7opt(x)+2

Следствие: задача об упаковке в контейнеры является NP-полной в слабом смысле.

2.
1. Отсортировать множество весов по убыванию

2. Выполнить алгоритм А1 для получившегося множества весов.

Утверждение: для любых х: А2(х) <=11/9*opt(x)+4

Приближенный алгоритм для евклидовой задачи коммивояжера.

Утверждение: задача коммивояжера в общем виде является NP-полной в сильном смысле.

Задача коммивояжера «на плоскости» (с неравенством треугольника);

Алгоритм Кристофидиса (Ak)

1. выбрать вершину – корень

2. построить минимальное остовное дерево

3. построить прямой обход дерева

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

Утверждение: для любых х: Ak(x)<=2opt(x)

Следствие: задача коммвояжера является NP-полной в слабом смысле.

 

Пример:

 

Разрешимые и неразрешимые проблемы, невычислимые функции. Примеры.

Число задач (функций) больше числа алгоритмов. Существуют задачи для которых нет алгоритмов их решения – алгоритмически неразрешимые.

1. Задача останова.
Дано: МТ, входящие данные Х. Остановится ли МТ на входных данных Х.

2. Задача эквивалентности: МТ1, МТ2. Верно ли что МТ1~МТ2?
Для любых МТ1=МТ2

3. Задача о решении диафантовых уравнений
x^2+y^2=z^2
pdy(x)+pdy(y)=pdy(z).
Существует ли решение уравнения в целых числах?

Придумать для разрешимых.