Задача о рюкзаке:PTAS - История изменений

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:43:53Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

Внесённые изменения

WikiSysop: 1 версия

2008-10-23T16:48:04Z

1 версия

StasFomin: обновление данных

2008-10-22T15:33:25Z

обновление данных

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2005-08-24T00:44:30Z

реплицировано из внутренней CustisWiki

Новая страница

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

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

Если мы отмасштабируем коэффициенты <math>c_1, \ldots, c_n</math>,
поделив нацело их на некоторый параметр ''scale'',
решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр ''scale'', то
очевидно, что мы получим допустимое решение исходной задачи и
абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины
<math>n \cdot scale</math>.

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

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

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

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

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

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

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

Какова сложность этого алгоритма? Она, есть величина <math>O(n \tilde f)</math>.
Учитывая, что <math>f^* \leq nc_{max}</math>, а <math>\tilde f \leq \frac{nc_{max}}{scale}</math>, получаем оценку сложности алгоритма «knapsack_ptas_trivial»:
<math>
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).
</math>

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

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

Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial»
Аналогично получаем оценку сложности для этого алгоритма:
<math>
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).
</math>

<code-python>
# Динамическое программирования для рюкзака,
# с отбором «наиболее легких» частичных решений.
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

# 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)

# PTAS для рюкзака, сложности $O(\frac{n^3}{\varepsilon})$
def knapsack_ptas_trivial(A,B,C,epsilon):
return knapsack_ptas_generic(A,B,C,epsilon,knapsack_lower_bound_trivial)

# PTAS для рюкзака, сложности $O(\frac{n^2}{\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

[[Category:Алгоритмы]]
{{replicate-from-custiswiki-to-lib}}

StasFomin: начал первую версию из лекций.

2005-08-23T16:08:48Z

начал первую версию из лекций.

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

← Предыдущая	Версия 16:48, 23 октября 2008
(нет различий)

@@ Строка 4: / Строка 4: @@
 отличается от оптимума исходной задачи.
-Если мы отмасштабируем коэффициенты <math>c_1, \ldots, c_n</math>,
+Если мы отмасштабируем коэффициенты <m>c_1, \ldots, c_n</m>,
 поделив нацело их на некоторый параметр ''scale'',
 решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр ''scale'', то
 очевидно, что мы получим допустимое решение исходной задачи и
 абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины
-<math>n \cdot scale</math>.
+<m>n \cdot scale</m>.
 Если потребовать, чтобы эта величина не превосходила
-<math>\frac{\varepsilon}{1+\varepsilon}f^*</math>, то получим,
+<m>\frac{\varepsilon}{1+\varepsilon}f^*</m>, то получим,
 что каждое допустимое решение исходной задачи
 отличается от решения «отмасштабированной» задачи не более, чем на эту же величину.
-Обозначая оптимум «отмасштабированной» задачи через <math>\tilde f</math>, получаем, что
+Обозначая оптимум «отмасштабированной» задачи через <m>\tilde f</m>, получаем, что
-<math>
+<m>
   \tilde f \geq f^* - \frac{\varepsilon}{1+\varepsilon}f^* = \frac{f^*}{(1+\varepsilon)},
-</math>
+</m>
 т. е. оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в
-<math>1+\varepsilon</math> раз.
+<m>1+\varepsilon</m> раз.
 При этом величина значение оптимального решения для «отмасштабированной» задачи уменьшается не менее, чем в ''scale'' раз по сравнению с исходной.
@@ Строка 28: / Строка 28: @@
 Однако проблема состоит в том, что в момент масштабирования
 мы не знаем величины оптимума ''f<sup>*</sup>'', и не можем выбрать
-коэффициент ''scale'', который, чтобы решение было <math>1+\varepsilon</math>-оптимальным, не должен превышать <math>\frac{\varepsilon f^*}{n(1+\varepsilon)}</math>, с одной стороны,
+коэффициент ''scale'', который, чтобы решение было <m>1+\varepsilon</m>-оптимальным, не должен превышать <m>\frac{\varepsilon f^*}{n(1+\varepsilon)}</m>, с одной стороны,
 с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.
 Поэтому, важное наблюдение состоит в том, что вместо ''f<sup>*</sup>'' можно
 рассматривать нижнюю оценку ''f<sup>*</sup>'', обозначим ее ''f<sub>lb</sub>'',
-и выбирать параметр масштабирования <math>scale=\frac{\varepsilon f_{lb}}{n(1+\varepsilon)}</math>
+и выбирать параметр масштабирования <m>scale=\frac{\varepsilon f_{lb}}{n(1+\varepsilon)}</m>
 тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.
-Таким образом, стоит задача выбора нижней оценки ''f<sub>lb</sub>'', которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к ''f<sup>*</sup>'', т. к. это даст возможность увеличить коэффициент ''scale'', и тем самым, сильнее уменьшить коэффициенты <math>c_1,\ldots,c_n</math> и время выполнения алгоритма.
+Таким образом, стоит задача выбора нижней оценки ''f<sub>lb</sub>'', которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к ''f<sup>*</sup>'', т. к. это даст возможность увеличить коэффициент ''scale'', и тем самым, сильнее уменьшить коэффициенты <m>c_1,\ldots,c_n</m> и время выполнения алгоритма.
 Таким образом, общая схема алгоритма,
 представлена как процедура «knapsack_ptas_generic»,
@@ Строка 43: / Строка 43: @@
 Осталось найти такую функцию. Например, можно рассмотреть тривиальную аппроксимацию
-<math>
+<m>
      n c_{\max} \geq f^* \geq f_{lb} \equiv c_{\max},
-</math>, где <math>c_{\max}=\max_{i} c_i</math>; и получим функцию «knapsack_ptas_trivial».
+</m>, где <m>c_{\max}=\max_{i} c_i</m>; и получим функцию «knapsack_ptas_trivial».
-Какова сложность этого алгоритма? Она, есть величина <math>O(n \tilde f)</math>.
+Какова сложность этого алгоритма? Она, есть величина <m>O(n \tilde f)</m>.
-Учитывая, что <math>f^* \leq nc_{max}</math>, а <math>\tilde f \leq \frac{nc_{max}}{scale}</math>, получаем оценку сложности алгоритма «knapsack_ptas_trivial»:
+Учитывая, что <m>f^* \leq nc_{max}</m>, а <m>\tilde f \leq \frac{nc_{max}}{scale}</m>, получаем оценку сложности алгоритма «knapsack_ptas_trivial»:
-<math>
+<m>
   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).
-</math>
+</m>
 Можно ли улучшить эту оценку? Ответ на этот вопрос положителен.
@@ Строка 62: / Строка 62: @@
 Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial»
 Аналогично получаем оценку сложности для этого алгоритма:
-<math>
+<m>
   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).
-</math>
+</m>
 <code-python>

← Предыдущая	Версия 16:08, 23 августа 2005
(нет различий)