|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Задача о рюкзаке:PTAS — различия между версиямиМатериал из CustisWiki
Версия 03:44, 24 августа 2005Алгоритмы динамического программирования для задачи о рюкзаке дают точное решение за время O(nf*) или O(nB). Если величины f* и B не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными. Однако, существует общий метод (который условно можно назвать «масштабированием»), позволяющий перейти к задаче с небольшими коэффициентами в целевой функции, оптимум которой не сильно отличается от оптимума исходной задачи. Если мы отмасштабируем коэффициенты , поделив нацело их на некоторый параметр scale, решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр scale, то очевидно, что мы получим допустимое решение исходной задачи и абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины . Если потребовать, чтобы эта величина не превосходила , то получим, что каждое допустимое решение исходной задачи отличается от решения «отмасштабированной» задачи не более, чем на эту же величину. Обозначая оптимум «отмасштабированной» задачи через , получаем, что т. е. оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в раз. При этом величина значение оптимального решения для «отмасштабированной» задачи уменьшается не менее, чем в scale раз по сравнению с исходной. И таким образом, для отмасштабированной задачи, версия алгоритма, ориентированная на отбор «самых легких решений» будет работать существенно меньшее время. Однако проблема состоит в том, что в момент масштабирования мы не знаем величины оптимума f*, и не можем выбрать коэффициент scale, который, чтобы решение было -оптимальным, не должен превышать , с одной стороны, с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче. Поэтому, важное наблюдение состоит в том, что вместо f* можно рассматривать нижнюю оценку f*, обозначим ее flb, и выбирать параметр масштабирования тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу. Таким образом, стоит задача выбора нижней оценки flb, которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к 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
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Задача о рюкзаке:PTAS» |
![]() |
||
![]() |
![]() |