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

Версия 18:33, 22 октября 2008

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

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

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

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

Обозначая оптимум «отмасштабированной» задачи через , получаем, что т. е. оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в раз.

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

Однако проблема состоит в том, что в момент масштабирования мы не знаем величины оптимума f^*, и не можем выбрать коэффициент scale, который, чтобы решение было -оптимальным, не должен превышать , с одной стороны, с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.

Поэтому, важное наблюдение состоит в том, что вместо f^* можно рассматривать нижнюю оценку f^*, обозначим ее f_lb, и выбирать параметр масштабирования тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.

Таким образом, стоит задача выбора нижней оценки f_lb, которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к f^*, т. к. это даст возможность увеличить коэффициент scale, и тем самым, сильнее уменьшить коэффициенты и время выполнения алгоритма. Таким образом, общая схема алгоритма, представлена как процедура «knapsack_ptas_generic», которой на вход, кроме обычных параметров рюкзака, передают функцию «f_lower_bound», используемую для получения нижней оценки стоимости решения.

Осталось найти такую функцию. Например, можно рассмотреть тривиальную аппроксимацию , где ; и получим функцию «knapsack_ptas_trivial».

Какова сложность этого алгоритма? Она, есть величина . Учитывая, что , а , получаем оценку сложности алгоритма «knapsack_ptas_trivial»:

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

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

Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial» Аналогично получаем оценку сложности для этого алгоритма:

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

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