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