Жадные алгоритмы/Задача о покрытии отрезков точками — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 17 промежуточных версий 2 участников)
Строка 1: Строка 1:
Пусть все наши N отрезков представлены парами {left, id}, {right, id}. Где left - координата левого конца, right - координата правого конца, id - "номер" нашего отрезка.<br />
+
<latex>
Так же, очевидно, что нам нужно как-то отмечать уже покрытые отрезки. Для этого заведем булевый массив flags[1..N], который изначально содержит все значения false.<br />
+
Дано $N$ отрезков на прямой. Требуется покрыть их наименьшим числом точек, т.е. найти наименьшее множество точек такое, что каждому отрезку принадлежит хотя бы она точка. Предложить эффективный жадный алгоритм, оценить сложность.
Так же заведем LIFO очередь для хранения рассматриваемых в данный момент вершин. <br />
+
</latex>
И массив для хранения ответов.<br />
+
Все пары наших отрезков {left, id}, {right, id} будут храниться в массиве.<br />
+
Отсортируем его по возрастанию координат отрезков. При чем, если у нас встречается "правая" и "левая" часть с одинаковой координатой, сначала в отсортированном массиве пойдет "левая", потом "правая". <br />
+
Данная операция займет минимум O(N*Log(N)) - если значение N неизвестно, или O(N)- если значение N известно.<br />
+
  
Начинаем обход нашего массива:<br />
+
[[Категория:Решенные задачи]]
:Если мы встретили левый конец отрезка -> добавляем его в LIFO очередь.<br />
+
[[Категория:Теоретические задачи]]
:Если мы встретили правый конец:<br />
+
::Если в нашем массиве flags отрезок с этим id помечен как покрытый, ничего не делаем, пропускаем эту запись.<br />
+
::Если в нашем массиве flags отрезок с этим id помечен как непокрытый, то добавляем координату его правого конца в ответ. Очевидно, что в нашей LIFO есть только "левые" части отрезков -> все они покрылись только что добавленной в ответ точкой. Поэтому, мы просто выталкиваем все "левые" концы из очереди, помечая их отрезки как покрытые. <br />
+
 
+
И так до самого конца массива. <br />
+
 
+
Т.к. мы просматриваем все элементы массива. Всего записей в массиве 2N. А так же тратим время на заталкивание/выталкивание из нашей LIFO очереди. В худшем случае в нее можно затолкать N элементов и N вытолкнуть(левых частей N штук), следовательно, времени на работу со стеком потратиться не более 2N. Поэтому количество операций не превосходит 4N. <br />
+
Следовательно, мы имеем сложность O(N) на обход.<br />
+
 
+
Таким образом, алгоритм будет работать или O(NlogN) или O(N) в зависимости от того, какая сортировка будет применена к массиву.<br />
+
[[Категория:На проверку]]
+

Текущая версия на 06:50, 4 мая 2023