Просмотр исходного текста страницы Жадные алгоритмы. Задача о "покрытии" на вещественной оси/Решение Мотренко

<latex>Решение предложенной студентами задачи:

Задан набор точек $\left\{x_1,\dots,x_n\right\}$, где $x_i \in \mathcal{R}$.
Необходимо покрыть все точки минимальным количеством единичных отрезков. Предложите эффективный жадный алгоритм. Докажите его корректность.

Отсортируем точки по возрастанию (будем считать, что возрастание индекса уже соответствует возрастанию значения) и сопоставим полученному набору точек вектор $\delta = [\delta_1, \dots, \delta_{n-1}]^T = [x_2-x_1, \dots, x_n -x_{n-1}]^{T}$. Для каждого $i = 1,\dots,n-1$ посчитаем количество $K_i$ точек с индексом больше $i$, таких что $\sum_{k = 0}^{K_i-1} \delta_{i+k} ≤ 1$. Пока множество непокрытых точек непусто, выполняем шаги
\begin{enumerate}
\item Выберем точку $x_i$ с наибольшим $K_i$, покроем ее отрезком $[x_{i}, x_i + 1]$. 
\item Ее покрытых соседей пометим как покрытые и удалим из рассмотрения. При этом, если $i > 1$, $K_{i-1} = 0$.
\end{enumerate}

Алгоритм полиномиален и работает за $O(n^2)$ ($n^2$ на сортировку, $n^2$ на подсчет $K_i$).
Корректность алгоритма:
\begin{enumerate}
\item Алгоритм покрывает все вершины.
\item Точность. %Пусть существует покрытие $J^{*}$ меньшим количество отрезков. Тогда один из отрезков в $J^{*}$ покрывает больше  
Является ли алгоритм точным, вечером подумаю, а так:
Переформулируем задачу в терминах теоремы 2.1.1 о точности жадного алгоритма для задачи о покрытии: $X = \left\{x_1,\dots,x_n\right\}$, семейство покрывающих подмножеств $S = \{S_1,\dots,S_m\}$, где $S_k = \{ \cup\{x_i\} | |x_i - x_j| ≤ 1 \}$. Тогда, согласно теореме 2.1.1, точность описанного алгоритма $1+\ln n$.
\end{enumerate}
</latex>