Приближенные алгоритмы Комбинаторные алгоритмы




НазваниеПриближенные алгоритмы Комбинаторные алгоритмы
Дата конвертации18.07.2013
Размер445 b.
ТипЗадача


Приближенные алгоритмы

  • Комбинаторные алгоритмы


Объект исследования

  • NP-трудные задачи оптимизации



Оптимизационная задача

  • Оптимизационная задача Π есть либо задача минимизации, либо задача максимизации и состоит из

  • множества ΩΠ индивидуальных задач;

  • для каждой I ΩΠ конечного множества SolΠ допустимых решений индивидуальной задачи I ;

  • функции hΠ , сопоставляющей каждой индивидуальной задаче I ΩΠ и каждому допустимому решению σ SolΠ некоторое рациональное число y(I, σ), называемое величиной решения σ.



Оптимальное решение

  • Если Π ― задача минимизации, то оптимальным решением индивидуальной задачи I ΩΠ является такое допустимое решение σ* SolΠ , что для всех σ SolΠ выполнено неравенство y(I, σ*) ≤ y(I, σ).

  • Для обозначения величины y(I, σ*) оптимального решения индивидуальной задачи I будет использоваться символ OPT(I).



NP-трудная задача

  • Задача Π является NP-трудной, если к ней сводится некоторая NP-полная задача.

  • Существование точного полиномиального алгоритма для NP-трудной задачи влечет P = NP.

  • Почти все интересные дискретные оптимизационные задачи ― NP-трудны.



Что делать с NP-трудными задачами?

  • Решать точно «переборными» алгоритмами

  • Решать приближенно

    • с апостериорной оценкой точности
    • с априорной оценкой точности
  • Мы будем строить приближенные полиномиальные алгоритмы с априорной оценкой точности.



Приближенный алгоритм

  • Полиномиальный алгоритм A называется ρ-приближенным алгоритмом для задачи минимизации Π, если для каждой индивидуальной задачи I ΩΠ ,

  • A(I) ≤ ρOPT(I).



Полиномиальная приближенная схема (PTAS)

  • Семейство приближенных алгоритмов для задачи Π, {Aε}ε называется полиномиальной приближенной схемой, если алгоритм Aε ― (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа при фиксированном ε.



Вполне полиномиальная приближенная схема (FPTAS)

  • Семейство приближенных алгоритмов для задачи Π, {Aε}ε называется вполне полиномиальной приближенной схемой, если алгоритм Aε ― (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа и 1/ε.



Алгоритм

  • Как построить приближенный алгоритм?

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



Задача линейного программирования



Полиномиально разрешимые задачи

  • Задача об остовном дереве минимального веса

  • Задача о максимальном потоке

  • Задача о максимальном паросочетании

  • Задача о k-факторе минимального веса

  • ●●●



Вопрос о качестве алгоритма

  • Как оценить качество алгоритма?

  • Сравнить стоимость получаемых решений со стоимостью оптимального решения.

  • Найти стоимость оптимального решения также сложно, как и само оптимальное решение.



Как оценить качество алгоритма?

  • Найти «хорошую» полиномиально вычислимую нижнюю оценку на стоимость оптимального решения.



Задача «Вершинное покрытие наименьшей мощности»

  • Дано: Связный граф G = (V, E).

  • Найти вершинное покрытие наименьшей мощности.



Максимальное паросочетание

  • Дан граф G = (V, E), подмножество ребер ME называется паросочетанием, если никакие два ребра из M не смежны, то есть не имеют общей граничной точки.

  • Паросочетание максимальное по включению.

  • Паросочетание максимальное по мощности.

  • Размер паросочетания максимального по включению является нижней границей на стоимость оптимального решения задачи «Вершинное покрытие наименьшей мощности».



Алгоритм «Простой»

  • Найти в графе G произвольное паросочетание M максимальное по включению.

  • Выдать множество вершин, попавших в паросочетание M.



Оценка качества алгоритма «Простой»

  • Теорема 4.1

  • Алгоритм «Простой» является 2-приближенным алгоритмом для задачи «Вершинное покрытие наименьшей мощности».



Качество анализа, нижней оценки, …

  • Можно ли за полиномиальное время получать решение с гарантированной оценкой лучше чем 2?

    • Можно ли улучшить анализ качества алгоритма «Простой»?
    • Можно ли построить алгоритм, который всегда находит решение с оценкой лучше чем 2 от предложенной нижней границы?
    • Существует ли другой алгоритм с гарантированной оценкой лучше чем 2?


Точность оценки



Качество анализа, нижней оценки, …

  • Можно ли за полиномиальное время получать решение с гарантированной оценкой лучше чем 2?

    • Можно ли улучшить анализ качества алгоритма «Простой»? Ответ нет.
    • Можно ли построить алгоритм, который всегда находит решение с оценкой лучше чем 2 от предложенной нижней границы?
    • Существует ли другой алгоритм с гарантированной оценкой лучше чем 2?


Сравнение нижней оценки и оптимального решения



Качество анализа, нижней оценки, …

  • Можно ли за полиномиальное время получать решение с гарантированной оценкой лучше чем 2?

    • Можно ли улучшить анализ качества алгоритма «Простой»? Ответ нет.
    • Можно ли построить алгоритм, который всегда находит решение с оценкой лучше чем 2 от предложенной нижней границы? Ответ нет.
    • Существует ли другой алгоритм с гарантированной оценкой лучше чем 2?


Задача «Покрытие»

  • Дано: Совокупность U из n элементов, и набор подмножеств U, S = {S1,…, Sk}, и веса(стоимости) подмножеств c: SQ+.

  • Найти покрытие наименьшего веса.

  • S' S является покрытием, если любой элемент из U принадлежит хотя бы одному элементу из S' .



Кратность

  • Пусть fi – кратность элемента ei, то есть число множеств из S, в которые он входит.

  • Пусть f = maxi=1,…,n fi.



Жадная стратегия

  • Пусть C будет множество элементов уже покрытое на предыдущих итерациях. Тогда αi = c(Si)/|Si – C| называется эффективностью множества Si и равна средней стоимости, с которой покрывается новый элемент.

  • Назовем ценой элемента e среднюю стоимость с которой он был покрыт.

  • Эквивалентно, когда множество S выбрано, мы можем понимать, что его стоимость равномерно распределена среди вновь покрытых элементов.



Алгоритм Хватала

  • 0) Input (U, S, c: SQ+)

  • C , Sol

  • While CU do:

  • Найти SiS – Sol, у которого

  • αi=c(Si)/|Si – C| минимально.

  • Sol Sol {Si}

  • C С Si (Si – самое эффективное)

  • price(e) = αi для всех eSi – C

  • 3) Output (Sol)



Анализ алгоритма Хватала

  • Упорядочим элементы из U в порядке, в котором они были покрыты алгоритмом.

  • Пусть это будет e1,…,en.

  • Лемма 4.2

  • Для каждого k {1,…,n},

  • price(ek)  OPT/(n–k+1).



Доказательство леммы 2.1



Доказательство леммы 2.1



Оценка качества алгоритма Хватала

  • Теорема 4.3

  • Алгоритм Хватала является Hn-приближенным алгоритмом для задачи «Покрытие множествами», где Hn=1+1/2+1/3+…+1/n.

  • Доказательство:



Точность оценки



Задача «Вершинное покрытие»

  • Дано: Граф G = (V, E), веса вершин w: VQ+.

  • Найти вершинное покрытие наименьшего веса.



Пропорционально-степенная функция

  • Назовем функцию, соответствующую весам вершин, пропорционально-степенной, если существует константа с > 0, такая что вес каждой вершины vV равен с deg(v).



Нижняя оценка

  • Лемма 4.4

  • Пусть w: VQ+ пропорционально-степенная функция. Тогда w(V)  2 OPT.



Доказательство

  • Пусть с > 0: w(v) = с deg(v).

  • Пусть U ― оптимальное вершинное покрытие.



Наибольшая пропорционально-степенная функция

  • Пусть w: VQ+ произвольная функция.

  • Определим наибольшую пропорционально-степенную функцию относительно w в графе G следующим образом:

    • Удалим из графа все вершины степени 0. Среди оставшихся вершин вычислим c= min{w(v)/deg(v)}.
    • Тогда t(v) = c deg(v) есть искомая функция
  • Определим через w′(v) = w(v) – t(v) остаточную функцию весов.



Алгоритм «Уровневый»

  • 0) Input (G = (V, E), w: VQ+)

  • Sol , i  0, w′(v)  w(v),

  • V0  V – D0 (D0 ={v V |deg(v)=0}) (удаляем вершины степени 0)

  • While Vi   do:

  • c min{w(v)/deg(v)}

  • t(v)  c deg(v) (находим наибольшую пропорционально-степенную функцию относительно w′)

  • w′(v)  w′(v) – ti(v) (вычисляем остаточную функцию весов)

  • Sol Sol Wi (Wi ={v Vi |w′(v)=0}) (пополняем решение)

  • Vi+1  Vi – Wi (удаляем вершины, вошедшие в решение)

  • i i+1

  • ViVi – Di (Di ={v Gi |deg(v)=0}) (удаляем вершины степени 0)

  • Output (Sol)



Пример



Пример



Пример



Пример



Пример



Пример



Оценка качества алгоритма «Уровневый»

  • Теорема 4.5

  • Алгоритм «Уровневый» является 2-приближенным алгоритмом для задачи «Вершинное покрытие».



Схема работы алгоритма



Доказательство

  • Пусть C ― полученное вершинное покрытие.

  • Пусть C* ― оптимальное вершинное покрытие.



Точность оценки



Задача «Кратчайшая суперстрока»

  • Дано: Конечный алфавит Σ и множество из n строк S = {s1,…,sn}  Σ+.

  • Найти кратчайшую суперстроку s, которая содержит каждую строку si, как подстроку.

  • Без ограничения общности будем считать, что никакая строка si не содержит другую строку sj, i j, как подстроку.



Задача «Кратчайшая суперстрока» как задача «Покрытие»



Нижняя оценка

  • Лемма 4.6

  • OPTstring  OPTcover  2 OPTstring



OPTcover  2 OPTstring



Алгоритм Ли

  • По индивидуальной задаче «Кратчайшая суперстрока» строим индивидуальную задачу «Покрытие».

  • Алгоритмом Хватала находим покрытие.

  • Пусть оно состоит из множеств set(π1),…, set(πk).

  • Соединяем строки π1,…,πk в любом порядке. Назовем полученную строку s.

  • Output (s)



Оценка качества алгоритма Ли

  • Теорема 4.7

  • Алгоритм Ли является 2Hn -приближенным алгоритмом для задачи «Кратчайшая суперстрока», где n – число строк в исходном примере.



Похожие:

Приближенные алгоритмы Комбинаторные алгоритмы iconОбщие комбинаторные алгоритмы Общие комбинаторные алгоритмы
Кнут Д. Искусство программирования, т Сортировка и поиск. М.: Вильямс, 2011. 824 с
Приближенные алгоритмы Комбинаторные алгоритмы iconОткрытые задачи (пока, оценочные)
Паскаль (основные типы данных и операторы, понятие сложности алгоритмов, процедуры и функции, рекурсия, арифметические и комбинаторные...
Приближенные алгоритмы Комбинаторные алгоритмы iconАлгоритмы обработки информации алгоритмы обработки информации
В области скоростных информационно-телекоммуникационных систем и массово используемых мобильных коммуникаций сложилось
Приближенные алгоритмы Комбинаторные алгоритмы iconАлгоритмы на топологических моделях Часть Алгоритмы на топологических моделях
Матрицы смежности, изоморфности, достижимости и контрдостижимости, списочные формы
Приближенные алгоритмы Комбинаторные алгоритмы iconАлгоритмы на топологических моделях Часть Алгоритмы на топологических моделях
Матрицы смежности, изоморфности, достижимости и контрдостижимости, списочные формы
Приближенные алгоритмы Комбинаторные алгоритмы iconТеория автоматов Машины Тьюринга
Иными словами, автоматы это ус­тройства, механически выполняющие алгоритмы. Можно строить различные мо­дели устройств, автоматически...
Приближенные алгоритмы Комбинаторные алгоритмы iconУзнать, когда и как появились алгоритмы сжатия. Узнать, когда и как появились алгоритмы сжатия
Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется
Приближенные алгоритмы Комбинаторные алгоритмы iconЛекция №7 Алгоритмы внешней сортировки (весенний семестр 2012 г.) Доцент Кафедры вычислительных систем, к т. н
Программирование/ языки программирования лекция №7 Алгоритмы внешней сортировки (весенний семестр 2012 г.)
Приближенные алгоритмы Комбинаторные алгоритмы iconАлгоритмы умение составлять алгоритмы просто необходимо, если человек хочет поручить обработку информации машине
Умение составлять алгоритмы просто необходимо, если человек хочет поручить обработку информации машине
Приближенные алгоритмы Комбинаторные алгоритмы iconБайесовские сети: Вероятностная семантика и оптимизационные алгоритмы в логико-вероятностном выводе
Вероятностная семантика и оптимизационные алгоритмы в логико-вероятностном выводе
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница