Персональные инструменты
 

Задача о рюкзаке:PTAS — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
[[Задача о рюкзаке:динамическое программирование|Алгоритмы динамического программирования для задачи]] о рюкзаке дают точное решение за время ''O(nf<sup>*</sup>)'' или ''O(nB)''. Если величины ''f<sup>*</sup>'' и ''B'' не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными.
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
Однако, существует общий метод (который условно можно назвать «масштабированием»), позволяющий перейти к задаче с небольшими коэффициентами в целевой функции, оптимум которой не сильно
+
отличается от оптимума исходной задачи.
+
 
+
Если мы отмасштабируем коэффициенты <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<sup>*</sup>'', и не можем выбрать
+
коэффициент ''scale'', который, чтобы решение было <math>1+\varepsilon</math>-оптимальным, не должен превышать <math>\frac{\varepsilon f^*}{n(1+\varepsilon)}</math>, с одной стороны,
+
с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.
+
 
+
Поэтому, важное наблюдение состоит в том, что вместо ''f<sup>*</sup>'' можно
+
рассматривать нижнюю оценку ''f<sup>*</sup>'', обозначим ее ''f<sub>lb</sub>'',
+
и выбирать параметр масштабирования <math>scale=\frac{\varepsilon f_{lb}}{n(1+\varepsilon)}</math>
+
тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.
+
 
+
Таким образом, стоит задача выбора нижней оценки ''f<sub>lb</sub>'', которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к ''f<sup>*</sup>'', т. к. это даст возможность увеличить коэффициент ''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<sup>*</sup>'', используя [[задача о рюкзаке:жадный алгоритм]], дающий точность не хуже чем в два раза.
+
 
+
Используя эту оценку, получаем функцию «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}}
+

Текущая версия на 20:43, 13 июня 2011

  1. REDIRECT discopal:Задача о рюкзаке:PTAS