Задача о максимальной клике.

Нельзя ли было бы обойтись двумя красками? Двойственной задачей к этой является задача о максимальной клике (клика = полный подграф). Если в графе существует полный подграф на 3 ребрах, то минимальное число красок = 3 (т.к. минимальное число красок для полного подграфа на N вершинах равно N).

В нашем случае есть клика: т.е. чтобы решить задачу о максимальной клике и решить задачу о раскраске, и посмотреть не являются ли вершины с номерами 8, 7, 1 вершинами клики.

Задача о P-медиане на графе. Даны граф G =(V,E), матрица расстояний D ={d_ij} и веса вершин W={w_i}. Найти подмножество С  V и |С| = p такое, что Интерпретация: С – множество складов.

Минимизируем суммарную длину пути при подвозе товаров со складов.

Решение (аналог argmin алгоритма ДОСТРОЙКА). Пусть C^*= {j^*- новый склад} и - расстояние до ближайшего склада. Тогда

Трудоемкость: 1. C ^*= C  {j^*}, 2. r_i(C ^*) 3. n = |V|операций.

O(n²) - выбор одного центра. Повторяя выбор p раз, получим трудоемкость O(n²p). Задача на графе NP ‑полна, для деревьев существует полиномиальный алгоритм.

Задача о P-центре. В отличие от задачи о p‑медиане функционал будет такой:

Аналог алгоритма ДОСТРОЙКА для этой задачи – наиболее удаленный сосед.

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

Алгоритм 1. Иди в ближайшую непройденную вершину (может не найти цикл).

А лгоритм 2: Если выполнено неравенство треугольника d_ij  d_ik + d_kj, то гаран­тируется нахождение цикла с длиной, превышающий оптимум не более чем в 2 раза.

Сначала построим МОД и выпишем обход: 1,2,7,6,3,6,5,4,5,6,7,2,8,2,1 (вперед и назад). Проредим его, вычеркивая все повторные вхождения вершин, кроме последней. Получим эйлеров цикл: 1,2,7,6,3,5,4,8,1. Оценим погрешность :

Из неравенства треугольника D_постр  2D_МОД  2D_опт  - длина кратчайшего обхода.

2D_опт  D_постр  D_постр - D_опт  D_опт    - приближенный алгоритм. Трудоемкость решения O(n²) (построение МОД)

№28. Алгоритм Кристофидеса для ЗКНТ.

1. Строим МОД и на нем множество V’ вершин с нечетной степенью.

2. На множестве V’ строим минимальное взвешенное паросочетание (МПС) (вершины разбиваются на пары, соединяемые ребрами с минимальной суммарной длиной): (1,8), (2,3), (6,4). Добавляем эти ребра в дерево.

3. На этом мультиграфе строится эйлеров обход: 1 2 3 6 4 5 6 7 2 8 1

Прореживаем его так же, как в предыдущем алгоритме: 1 2 3 6 4 5 7 8 1.

Докажем, что его длина превышает оптимум не более, чем на.50%.

П усть {i₁, i₂,…,i_2m}- множество вершин из V’, выписанных в порядке появления их на оптимальном маршруте коммивояжера. Тогда по неравенству треугольника имеем для паросочетаний

S₁ = {(i₁, i₂), (i₃, i₄),…} и S₂ = {(i₂, i₃), (i₄, i₅),…}:

D_постр  D_МОД + D_МПС  D_опт + D_МПС , и D_опт  D(S₁) + D(S₂)  2D_МПС   .

Приведем пример того, что эта оценка неулучшаема. МОД – k треугольников.

при

3.7. Точные методы решения np-полных задач.

№29 Решение задачи коммивояжера методом ветвей и границ.

-	2	-	8	3	7
2	-	2	-	1	3
-	2	-	2	1	2
8	-	2	-	2	1
3	1	1	2	-	3
7	3	2	1	3	-

Н а основе чего делать ветвление? Фиксируем любую часть пути – цепочку C длины D_C. На вершинах, не вошедших в цепочку C, построим МОД длины D_МОД.

Пусть D_опт  – оптимальная длина цикла при фиксированной цепочке C,

-длина перемычки, D_опт ≥ D_C + D_МОД + D_перем.= f_C

Если f_C  f_R , т.е. f_R - D  D_МОД + D_перем , (где f_R – длина текущего рекордного цикла R), то цепочка C не улучшает рекорд  последнее звено цепочки C можно отбросить.

Некоторые ребра выкинем сразу. Если из гамильтонова цикла выкинуть любое ребро, то останется цепочка, для которой D_опт  D_МОД (V),  f_R  D_опт  D_МОД (V) + r (на множестве всех вершин графа, r-длина любого ребра, вошедшего в оптимальный цикл). Получаем r  f_R – D_МОД (V). Если r > f_R – D_МОД (V), то это ребро в улучшающий цикл не войдет.

Чтобы улучшить рекорд, необходимо r  f_R – D_МОД (V). Решаем:

1. С начала строим текущий рекордный цикл R:

f_R=14

2. Строим МОД алгоритмом Тарьяна: 1 – 2 – 5 – 3 – 4 – 6, D_МОД  =7

3. О тбросим ребра 1–4 и 1–6, длина которых. f_R - D_МОД = 14-7 = 7. Степень вершины 1 равна 2  ребра 1–2 и 1–5 участвуют в цепи, хорда 2–5 не участвует (иначе возникнет цикл). Начнем построение цепочки с вершины 5, т.к. ее степень больше степени вершины 2.

При поиске сначала вглубь цепочка с фиксированным началом целиком определяется своей последней вершиной k.  вместо f_C и D_C будем писать f_k. и D_k..

f₆ = 8+2+(1+1) = 12 = f₃ = 7+1+(2+2) < f_R = 14. Оценочные функции совпали  выбираем для ветвления вершину с мин.номером, т.е. 3: f_R-D₃=14-7=7

 Ветвим и делаем проверку на новый рекорд: в самом деле, имеем f_R=12  назад.

Т .к. рекорд изменился, снова проверяем вершину 6 на возможность ветвления. Проверяем

f₆ =12 ≥ f_R = 12.  улучшения быть не может,  назад.

Все висячие вершины раскрыты  R – оптимален, f_R=12.

Этот метод работает, если граф неориентированный (нужно для построения МОД).

№30. Задача оптимального распределения ограниченного ресурса.

Пусть задан ресурс R  0 и n потребителей со своими функциями прибыли  _i(x). Требуется распределить ресурс между потребителями: R = _i r_i , r_i  0, максими­зируя суммарную прибыль _i  _i(r_i). Заметим, что любая часть оптимального рас­пределения сама является оптимальным распределением (принцип Беллмана).

Пусть F_k(y) = {  _k(x_k) + F_k+1(y-x_k)} - максимальная прибыль потребителей с номерами от k до n-1 при распределении между ними ресурса y и F_n(y) =  _n(y). Если R и r_i – целые, то, меняя k от n-1 до 1 (метод динамического программирова­ния), мы найдем максимальную прибыль F₁(R). Трудоемкость = O(nR²).

Пример: 3 экзамена за 8 дней.  _i – оценка на экзамене, x - время на подготовку.

x	1	2	3		y	F3(y)	x2(y)	F2(y)	x1(y)	F1(y)		2(x)	F3(4-x)	2+F3			1(x)	F2(8-x)	1+F2
0	2	3	2		0	2	0	5				3	3	6			2	8	10
1	2	3	2		1	2	0	5				3	3	6			2	8	10
2	3	4	2		2	2	2	6				4	2	6			3	7	10
3	3	4	3		3	3	0	6				4	2	6			3	7	10
4	4	5	3		4	3	4	7				5	2	7			4	7	11
5	4	5	3		5	3	2	7						max=7			4	6	10
6	5	5	4		6	4	0	7			xk(y) = min { xk  y |						5	6	11
7	5	5	4		7	4	4	8			k(xk) + Fk+1(y-xk)=Fk(y)}						5	5	10
8	5	5	4		8	4	2	8	4	11					max=11		5	5	10

Случай идентичных потребителей: _i(x)=(x). Докажите, что

а) если (x) выпукла по x, то весь ресурс можно отдать одному потребителю,

б) если вогнута, то его надо делить поровну между всеми потребителями.

№31. Задача о рюкзаке.

Пусть есть рюкзак объема V  0 и n камней с объемами v_i и ценами c_i. С каждым камнем свяжем переменную x_i, равную 1 (если камень берется) или 0 (в противном случае). Требуется найти подмножество камней с максимальной суммарной стоимостью, влезающее в рюкзак (т.е. _i c_ix_i → max при _i v_ix_i,   V).

Пусть F_k(y) - максимальная стоимость камней с номерами от k до n, влезающих в рюкзак объема y. Т.к. любая часть оптимального решения оптимальна, то

F_n(y) = c_n (если v_n  y) или 0 (в противном случае) Если V и v_i – целые, то метод

F_k(y) = max { F_k+1(y), c_k + F_k+1(y-v_k) если y v_k} динамического программирования:

x_k(y) = min { x_k  y | c_kx_k + F_k+1(y-v_kx_k) = F_k(y) }. меняя k от n-1 до 1, найдем F₁(V), Трудоемкость - O(nV). x₁(y₁=V), x_k+1(y_k+1= y_k - v_kx_k(y_k)).

y	x1(y)	F1(y)	x2(y)	F2(y)	x3(y)	F3(y)	x4(y)	F4(y)
 1			0	0	0	0	0	0
2			1	6	0	0	0	0
3			0	8	1	8	0	0
4			0	10	0	10	1	10
5	1	15	1	14	0	10	1	10

Пример:

5 x₁ + 6 x₂ + 8 x₃ + 10 x₄  max

 x₁ + 2 x₂ + 3 x₃ +  4 x₄  5

F₂(4) =max{ F₃(4),6+ F₃(4-2=2)}

= max {10,6+0} = 10, x₂(4)=0.

F₁(5) =max{ F₂(5),10+ F₂(5-1)}

= max {14,5+10} = 15, x₁(5)=1.

x₁ =x₁(5)=1, x₂ =x₂(5-v₁x₁ =4)=0, x₃ =x₃(4-v₂x₂ =4)=0, x₄=x₄(4-v₃x₃ =4)=1.

NP-полны и варианты задачи: если x_k  {0,1,2,3,…} или ограничен вес рюкзака. Точное решение дает метод ветвей и границ, нижние оценки для которого получают при отказе от ограничений (целочисленности), или метод динамического программирования. NP-полна и задача о двух кучах камней: можно ли разделить на 2 равные части кучу камней с целочисленными весами?

Пример: для набора весов {5,4,3,3,3} жадная эвристика не находит решения.