Алгоритм
<<  Конструирование алгоритмов Изучаем алгоритмы  >>
Комбинаторные алгоритмы
Комбинаторные алгоритмы
Задача «Кратчайшая суперстрока»
Задача «Кратчайшая суперстрока»
Задача «Покрытие»
Задача «Покрытие»
Задача «Кратчайшая суперстрока» как задача «Покрытие»
Задача «Кратчайшая суперстрока» как задача «Покрытие»
Нижняя оценка
Нижняя оценка
OPTcover
OPTcover
Алгоритм Ли
Алгоритм Ли
Теорема 5.2 Алгоритм Ли является 2Hn -приближенным алгоритмом для
Теорема 5.2 Алгоритм Ли является 2Hn -приближенным алгоритмом для
Задача Штейнера
Задача Штейнера
Метрическая задача Штейнера
Метрическая задача Штейнера
Сводимость
Сводимость
Сводимость задачи Штейнера
Сводимость задачи Штейнера
Деревья Штейнера и остовные деревья (MST)
Деревья Штейнера и остовные деревья (MST)
Оценка
Оценка
Доказательство
Доказательство
Алгоритм MST
Алгоритм MST
Оценка качества алгоритма MST
Оценка качества алгоритма MST
Точность оценки
Точность оценки
Задача Коммивояжера
Задача Коммивояжера
Неаппроксимируемость
Неаппроксимируемость
Идея доказательства
Идея доказательства
Метрическая задача Коммивояжера
Метрическая задача Коммивояжера
Алгоритм MST-2
Алгоритм MST-2
Пример
Пример
Оценка качества алгоритма MST-2
Оценка качества алгоритма MST-2
Алгоритм MST-2
Алгоритм MST-2
Точность оценки
Точность оценки
Точность оценки: оптимальный тур
Точность оценки: оптимальный тур
Точность оценки (MST)
Точность оценки (MST)
Точность оценки: Гамильтонов цикл
Точность оценки: Гамильтонов цикл
Алгоритм Кристофидиса-Сердюкова
Алгоритм Кристофидиса-Сердюкова
Пример
Пример
Нижняя оценка
Нижняя оценка
Оценка качества алгоритма Кристофидиса-Сердюкова
Оценка качества алгоритма Кристофидиса-Сердюкова

Презентация: «Комбинаторные алгоритмы». Автор: Kononov. Файл: «Комбинаторные алгоритмы.ppt». Размер zip-архива: 92 КБ.

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

содержание презентации «Комбинаторные алгоритмы.ppt»
СлайдТекст
1 Комбинаторные алгоритмы

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

Задачи с метрикой

1

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

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

Дано: Конечный алфавит ? и множество из n строк Sstring = {s1,…,sn} ? ?+ (множество всех строк в алфавите ? ). Найти кратчайшую суперстроку s, которая содержит каждую строку si, как подстроку. Без ограничения общности будем считать, что никакая строка si не содержит другую строку sj, i ? j, как подстроку.

2

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

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

Дано: Совокупность Ucover из n элементов, и набор подмножеств Ucover , Scover = {S1,…, Sk}, и веса(стоимости) подмножеств c: Scover ? Q+. Найти покрытие наименьшего веса.

3

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

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

k > 0

si

sj

?ijk

M ={?ijk | ?ijk – допустимая}

Scover? {set(?ijk) | ?ijk – допустимая}

c(set(?)) = | ? |

?? ?+ : set(?)={s?s | s – подстрока ?}

Ucover? Sstring

4

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

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

Лемма 5.1 OPTstring ? OPTcover ? 2 OPTstring Рассмотрим оптимальное покрытие {set(?i)|1? i ? l} и получим строку s, записав друг за другом все строки ?i. Тогда | s | = OPTcover . Каждая строка из Sstring является подстрокой некоторого ?i. ? s ? суперстрока, и OPTstring ? OPTcover .

5

6 OPTcover

OPTcover

2 OPTstring

S ? кратчайшая суперстрока

sb1

se1

sb2

se2

sb3

se3

?1

?2

?3

6

7 Алгоритм Ли

Алгоритм Ли

По индивидуальной задаче «Кратчайшая суперстрока» строим индивидуальную задачу «Покрытие». Алгоритмом Хватала находим покрытие. Пусть оно состоит из множеств set(?1),…, set(?k). Соединяем строки ?1,…,?k в любом порядке. Назовем полученную строку s. Output (s)

7

8 Теорема 5.2 Алгоритм Ли является 2Hn -приближенным алгоритмом для

Теорема 5.2 Алгоритм Ли является 2Hn -приближенным алгоритмом для

задачи «Кратчайшая суперстрока», где n – число строк в исходном примере.

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

8

9 Задача Штейнера

Задача Штейнера

Дано: Граф G = (V, E), веса (стоимости) ребер cost: E ? Q+, подмножество R ? V. Найти дерево T наименьшей стоимости, такое что R ? T ,то есть содержит все вершины из R. Множество R будем называть множеством требований. Множество V/R называют множеством Штейнера.

9

10 Метрическая задача Штейнера

Метрическая задача Штейнера

Дано: Полный граф G = (V, E), стоимости ребер cost: E ? Q+ такие, что для любых трех вершин u, v и w: cost(u,v) ? cost(u,w) + cost(w,v), подмножество R ? V. Найти дерево T наименьшей стоимости, которое содержит все вершины из R.

10

11 Сводимость

Сводимость

Будем говорить, что задача P сводится к задаче Q с сохранением фактор-аппроксимации, если существуют функции f и g, вычислимые за полиномиальное время, такие что f преобразует частную задачу IP из P в частную задачу IQ из Q, и g преобразует решение ?Q ( f (IP)) в решение ?P (IP) (?P (IP)=g(?Q ( f (IP)))) и y(IP,?P (IP))/OPT(IP) ? y(IQ,?Q( f (IP))/OPT(f (IP)).

11

12 Сводимость задачи Штейнера

Сводимость задачи Штейнера

Теорема 5.3 Задача Штейнера сводится к метрической задачи Штейнера с сохранением фактор-аппроксимации. Доказательство. Пусть I пример задачи Штейнера с графом G = (V, E). По графу G построим полный граф G? для примера I? метрической задачи Штейнера. Определим стоимость ребра (u,v) в G? , как стоимость кратчайшего u-v-пути в G. OPT(I?) ? OPT(I). По любому решению I? можно построить решение I с не большей стоимостью.

12

13 Деревья Штейнера и остовные деревья (MST)

Деревья Штейнера и остовные деревья (MST)

R

Дерево Штейнера

5

5

Остовное дерево

3

3

3

5

13

14 Оценка

Оценка

Теорема 5.4 Пусть R ? V множество требований в задаче Штейнера. Тогда стоимость минимального остовного дерева на R не превосходит двух стоимостей оптимального дерева Штейнера в G.

14

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

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

Дерево Штейнера

Эйлеров обход

Остовное дерево

15

16 Алгоритм MST

Алгоритм MST

Input (G, R, cost: E ? Q+) Найти минимальное остовное дерево T на множестве вершин R. Output (T)

16

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

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

Следствие 5.5 Алгоритм MST является 2-приближенным алгоритмом для задачи Штейнера.

17

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

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

2

2

2

1

1

2

18

19 Задача Коммивояжера

Задача Коммивояжера

Дано: Полный граф G = (V, E), веса (стоимости) ребер cost: E ? Q+. Найти гамильтонов цикл С минимальной стоимости. Цикл, который содержит все вершины, называется гамильтоновым.

19

20 Неаппроксимируемость

Неаппроксимируемость

Теорема 5.6 Для любой полиномиально вычислимой функции ?(n), для задачи коммивояжера не существует ?-приближенного алгоритма с ?= ?(n), если P ? NP.

20

21 Идея доказательства

Идея доказательства

Предположим, что существует ?-приближенный алгоритм A с ? = ?(n) для задачи коммивояжера. Покажем что с помощью A можно решать задачу «Гамильтонов цикл». По примеру задачи «Гамильтонов цикл» построить пример задачи коммивояжера: G имеет гамильтонов цикл ? стоимость оптимального цикла равна n. G не имеет гамильтонов цикла ? стоимость оптимального цикла больше n?(n).

21

22 Метрическая задача Коммивояжера

Метрическая задача Коммивояжера

Дано: Полный граф G = (V, E), веса (стоимости) ребер cost: E ? Q+ такие, что для любых трех вершин u, v и w: cost(u,v) ? cost(u,w) + cost(w,v). Найти гамильтонов цикл С минимальной стоимости.

22

23 Алгоритм MST-2

Алгоритм MST-2

Input (G, cost: E ? Q+) Найти минимальное остовное дерево T в G. Удвоить каждое ребро в T и получить Эйлеров граф H. Найти Эйлеров обход R в H. Построить Гамильтонов цикл C, посещая вершины графа G в порядке, в котором они встречаются в R. Output (С)

23

24 Пример

Пример

Остовное дерево

Эйлеров обход

Гамильтонов цикл

24

25 Оценка качества алгоритма MST-2

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

Теорема 5.7 Алгоритм MST-2 является 2-приближенным алгоритмом для метрической задачи Коммивояжера.

25

26 Алгоритм MST-2

Алгоритм MST-2

Input (G, cost: E ? Q+) Найти минимальное остовное дерево T в G. Удвоить каждое ребро в T и получить Эйлеров граф H. Найти Эйлеров обход R в H. Построить Гамильтонов цикл C, посещая вершины графа G в порядке, в котором они встречаются в R. Output (С)

26

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

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

2

1

2

1

1

1

27

28 Точность оценки: оптимальный тур

Точность оценки: оптимальный тур

28

29 Точность оценки (MST)

Точность оценки (MST)

29

30 Точность оценки: Гамильтонов цикл

Точность оценки: Гамильтонов цикл

30

31 Алгоритм Кристофидиса-Сердюкова

Алгоритм Кристофидиса-Сердюкова

Input (G, cost: E ? Q+) Найти минимальное остовное дерево T в G. Найти паросочетание минимальной стоимости M на множестве вершин в T с нечетными степенями. Добавить ребра M к T и получить Эйлеров граф H. Найти Эйлеров обход R в H. Построить Гамильтонов цикл C, посещая вершины графа G в порядке, в котором они встречаются в R. Output (С)

31

32 Пример

Пример

Остовное дерево

Паросочетание

Гамильтонов цикл

32

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

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

Лемма 5.8 Пусть V? ? V, такое что |V?| четно и пусть M совершенное паросочетание минимальной стоимости на V? . Тогда cost(M) ? OPT/2.

33

34 Оценка качества алгоритма Кристофидиса-Сердюкова

Оценка качества алгоритма Кристофидиса-Сердюкова

Теорема 5.9 Алгоритм Кристофидиса-Сердюкова является 3/2-приближенным алгоритмом для метрической задачи Коммивояжера. Доказательство:

34

«Комбинаторные алгоритмы»
http://900igr.net/prezentacija/informatika/kombinatornye-algoritmy-152702.html
cсылка на страницу

Алгоритм

31 презентация об алгоритме
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Алгоритм > Комбинаторные алгоритмы