Традиция

Текст:Задача о рюкзаке:PTAS

Алгоритмы динамического программирования для задачи о рюкзаке дают точное решение за время O(nf*) или O(nB). Если величины f* и B не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными.

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

Если мы отмасштабируем коэффициенты c 1 , … , c n c_1, \ldots, c_n , поделив нацело их на некоторый параметр scale, решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр scale, то очевидно, что мы получим допустимое решение исходной задачи и абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины n ⋅ s c a l e n \cdot scale .

Если потребовать, чтобы эта величина не превосходила ε 1 + ε f ∗ \frac{\varepsilon}{1+\varepsilon}f^* , то получим, что каждое допустимое решение исходной задачи отличается от решения «отмасштабированной» задачи не более, чем на эту же величину.

Обозначая оптимум «отмасштабированной» задачи через f ~ \tilde f , получаем, что f ~ ⩾ f ∗ − ε 1 + ε f ∗ = f ∗ ( 1 + ε ) , \tilde f \geq f^* - \frac{\varepsilon}{1+\varepsilon}f^* = \frac{f^*}{(1+\varepsilon)}, то есть оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в 1 + ε 1+\varepsilon раз.

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

Однако проблема состоит в том, что в момент масштабирования мы не знаем величины оптимума f*, и не можем выбрать коэффициент scale, который, чтобы решение было 1 + ε 1+\varepsilon -оптимальным, не должен превышать ε f ∗ n ( 1 + ε ) \frac{\varepsilon f^*}{n(1+\varepsilon)} , с одной стороны, с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.

Поэтому, важное наблюдение состоит в том, что вместо f* можно рассматривать нижнюю оценку f*, обозначим ее flb, и выбирать параметр масштабирования s c a l e = ε f l b n ( 1 + ε ) scale=\frac{\varepsilon f_{lb}}{n(1+\varepsilon)} тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.

Таким образом, стоит задача выбора нижней оценки flb, которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к f*, так как это даст возможность увеличить коэффициент scale, и тем самым, сильнее уменьшить коэффициенты c 1 , … , c n c_1,\ldots,c_n и время выполнения алгоритма. Таким образом, общая схема алгоритма, представлена как процедура «knapsack_ptas_generic», которой на вход, кроме обычных параметров рюкзака, передают функцию «f_lower_bound», используемую для получения нижней оценки стоимости решения.

Осталось найти такую функцию. Например, можно рассмотреть тривиальную аппроксимацию n c max ⩾ f ∗ ⩾ f l b ≡ c max , n c_{\max} \geq f^* \geq f_{lb} \equiv c_{\max}, , где c max = max i c i c_{\max}=\max_{i} c_i ; и получим функцию «knapsack_ptas_trivial».

Какова сложность этого алгоритма? Она, есть величина O ( n f ~ ) O(n \tilde f) . Учитывая, что f ∗ ⩽ n c m a x f^* \leq nc_{max} , а f ~ ⩽ n c m a x s c a l e \tilde f \leq \frac{nc_{max}}{scale} , получаем оценку сложности алгоритма «knapsack_ptas_trivial»: O ( n f ~ ) = O ( n 2 c m a x s c a l e ) = O ( n 3 ( 1 + ε ) ε ) = O ( n 3 ε ) . O(n \tilde f)=O\left(n^2\frac{c_{max}}{scale}\right) =O\left(\frac{n^3(1+\varepsilon)}{\varepsilon}\right) =O\left(\frac{n^3}{\varepsilon}\right).

Можно ли улучшить эту оценку? Ответ на этот вопрос положителен.

Для этого рассмотрим менее наивную аппроксимацию величины f*, используя задача о рюкзаке:жадный алгоритм, дающий точность не хуже чем в два раза.

Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial» Аналогично получаем оценку сложности для этого алгоритма: O ( n f ~ ) = O ( n f G s c a l e ) = O ( n 2 ( 1 + ε ) ε ) = O ( n 2 ε ) . O(n \tilde f) =O\left(n \frac{f_G}{scale}\right) =O\left(\frac{n^2(1+\varepsilon)}{\varepsilon}\right) =O\left(\frac{n^2}{\varepsilon}\right).

<code-python>

  1. Динамическое программирования для рюкзака,
  2. с отбором «наиболее легких» частичных решений.

def knapsack_dylp_lightest(A,B,C): 

   T={0:0} #Хэш: самый малый вес для стоимости - {стоимость:минимальный вес}
   Solution={0:[]}
   #Цикл по всем предметам $\frac{c_i}{a_i}$
   for i in range(0,len(A)):
       T_old=dict(T)  #Копируем $T_{k-1}$ в $T_{old}$
       for x in T_old:
           if (T_old[x]+A[i])<=B:
               if (not T.has_key(x+C[i])) or (T_old[x]+A[i]<T_old[x+C[i]]):
                   T[x+C[i]]=T_old[x]+A[i]
                   Solution[x+C[i]]=Solution[x]+[i]

   ResultCost = max(T.keys())
   Result = Solution[ResultCost]
   return Result
  1. PTAS для рюкзака. Общая схема.

def knapsack_ptas_generic(A,B,C,epsilon, f_lower_bound): 

   print "A=",A
   print "B=",B
   print "C=",C
   print "epsilon=",epsilon

   #Вычисляем нижнюю оценку стоимости и параметр округления $scale$
   F_lb=f_lower_bound(A,B,C)
   print "F_lb=",F_lb

   scale=floor(epsilon*F_lb/len(C)/(1+epsilon))
   print "scale=",scale

   #Округляем коэффициенты 
   C_=[]
   for i in range(0,len(A)):
       C_.insert(i, int(floor(C[i] / scale)))
   print "C_=",C_

   ApproxResult=knapsack_dylp_lightest(A,B,C_)

   ApproxCost=0
   for i in ApproxResult:
           ApproxCost=ApproxCost+C[i]
           
   return (ApproxResult,ApproxCost)

def knapsack_lower_bound_trivial(A,B,C): 

   #Простая оценка нижней границы стоимости решения.
   return max(C)

def knapsack_lower_bound_greedy(A,B,C): 

   #Оценка нижней границы через жадный алгоритм.
   return knapsack_greedy(A,B,C)
  1. PTAS для рюкзака, сложности $O(\frac{n³}{\varepsilon})$

def knapsack_ptas_trivial(A,B,C,epsilon): 

   return knapsack_ptas_generic(A,B,C,epsilon,knapsack_lower_bound_trivial)
  1. PTAS для рюкзака, сложности $O(\frac{n²}{\varepsilon})$

def knapsack_ptas_nontrivial(A,B,C,epsilon): 

   return knapsack_ptas_generic(A,B,C,epsilon,knapsack_lower_bound_greedy)

</code-python> 


knapsack_ptas_trivial:
A= [16, 900, 440, 250, 667, 43, 333, 857, 474]
B= 1000
C= [134, 1354, 567, 789, 987, 56, 345, 4567, 5555]
epsilon= 0.1
F_lb= 5555
scale= 56.0
C_= [2, 24, 10, 14, 17, 1, 6, 81, 99]
Cost= 6534

knapsack_ptas_nontrivial:
A= [16, 900, 440, 250, 667, 43, 333, 857, 474]
B= 1000
C= [134, 1354, 567, 789, 987, 56, 345, 4567, 5555]
epsilon= 0.1
F_lb= 6534
scale= 66.0
C_= [2, 20, 8, 11, 14, 0, 5, 69, 84]
Cost= 6478

knapsack_ptas_nontrivial:
A= [16, 900, 440, 250, 667, 43, 333, 857, 474]
B= 1000
C= [134, 1354, 567, 789, 987, 56, 345, 4567, 5555]
epsilon= 0.08
F_lb= 6534
scale= 53.0
C_= [2, 25, 10, 14, 18, 1, 6, 86, 104]
Cost= 6534


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.

Источник — https://traditio.wiki/w/index.php?title=Текст:Задача_о_рюкзаке:PTAS&oldid=702528