Содержание
- 2. Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {Aε}ε называется полиномиальной приближенной схемой, если
- 3. Вполне полиномиальная приближенная схема (FPTAS) Семейство приближенных алгоритмов для задачи Π, {Aε}ε называется вполне полиномиальной приближенной
- 4. Как построить PTAS Упрощение примера I. Разбиение пространства решений. Структурирование работы алгоритма A. Пример I Алгоритм
- 5. Упрощение примера I. Первая идея превратить трудный пример в более простой в котором легче найти оптимальное
- 6. P2||Cmax J={1,..., n} – работы. {M1, M2} – одинаковые машины. j : pj > 0 (i=1,…,
- 7. Нижняя оценка
- 8. Как упростить пример? ( I→ I# ) Big = { j ∈ J| pj ≥ εL}
- 9. Оценка на оптимум Лемма 6.1 OPT(I#) ≤ (1+ ε)OPT(I).
- 10. Доказательство Xi – размер всех маленьких работ, выполняемых на машине Mi в оптимальном расписании для I.
- 11. Как решить упрощенный пример? Как много работ в I#? pj ≥ εL для всех работ в
- 12. Как вернуться к исходной задаче? Пусть σ# – оптимальное расписание для I#. Li# – нагрузка машины
- 13. Процедура ( σ#(I#)→ σ(I) ) Большие работы выполняются на той же машине, что и в σ#.
- 14. Оценка качества
- 15. Алгоритм PTAS-1 Input ( J={1,..., n}, p: J → Z+) Определим Big = { j ∈
- 16. Точность алгоритма PTAS-1 Теорема 6.2 Алгоритма PTAS-1 – (1+ε)-приближенный алгоритм для задачи P2||Cmax.
- 17. Разбиение пространства решений Вторая идея разбить пространство решений на несколько меньших областей, в которых проще найти
- 18. Общая схема Разбиение на области. Выбор «хорошего» представителя в каждой области. Выбор из множества хороших представителей
- 19. P2||Cmax J={1,..., n} – работы. {M1, M2} – одинаковые машины. j : pj > 0 (i=1,…,
- 20. Как разбить на области Big = { j ∈ J| pj ≥ εL} Small = {
- 21. Сколько получилось областей? Число больших работ ≤ 2L/εL= 2/ε. Число способов разместить большие работы по двум
- 22. Как выбрать «хорошего» представителя? Назначение больших работ зафиксировано в Φ(l). OPT(l) – длина оптимального расписания в
- 23. А хорош ли представитель? Если A(l) =T, то A(l) = OPT(l). Пусть A(l) >T. Рассмотрим машину
- 24. Алгоритм PTAS-2 Input ( J={1,..., n}, p: J → Z+) Определим Big = { j ∈
- 25. Точность алгоритма PTAS-2 Теорема 6.3 Алгоритма PTAS-2 – (1+ε)-приближенный алгоритм для задачи P2||Cmax.
- 26. Структурирование работы алгоритма Основная идея рассмотреть точный, но медленный алгоритм. Если алгоритм получает и перерабатывает огромное
- 27. P2||Cmax J={1,..., n} – работы. {M1, M2} – одинаковые машины. j : pj > 0 (i=1,…,
- 28. Краткая запись решения Обозначим через σk допустимое расписание k первых работ {1,..., k}. Закодируем расписание σk
- 29. Алгоритм «Динамическое программирование» Input ( J={1,..., n}, p: J → Z+) Положим V0={[0,0]}, i=0. While i
- 30. Трудоемкость алгоритма Координаты всех векторов целые числа от 0 до psum. Число различных векторов в Vi
- 31. Как упростить множество векторов? Все вектора соответствуют точкам плоскости в квадрате [0, psum]×[0, psum]. Разделим этот
- 32. Отсев векторов Пусть два вектора [x1,y1] и [x2,y2] попали в одну клетку. x1/Δ ≤ x2 ≤
- 33. Алгоритм FPTAS Input ( J={1,..., n}, p: J → Z+) Положим V0#={[0,0]}, i=0. While i ≠
- 34. Трудоемкость алгоритма FPTAS Множество векторов в Vi# содержит не более одного вектора из каждой клетки. Всего
- 35. Оценка на вектора в Vi и Vi# Лемма 6.4 Для каждого вектора [x,y]∈ Vi существует вектор
- 36. Доказательство (по индукции) i =1: (x1/Δ ≤ x2 ≤ x1Δ и y1/Δ ≤ y2 ≤ y1Δ
- 37. Точность алгоритма FPTAS Теорема 6.5 Алгоритма FPTAS – (1+ε)-приближенный алгоритм для задачи P2||Cmax.
- 38. Доказательство
- 40. Скачать презентацию