Как найти решение для задачи?

Question

[Анастасия]

Каким алгоритмом решить задачу?
Предположим, мы хотим создать универсальную программную камеру, объединив множество негибких аппаратных камер. Каждая аппаратная камера хорошо работает для определенного диапазона расстояний до объекта и для определенного диапазона уровней освещенности. Программная камера будет измерять уровень освещенности и расстояние до объекта для каждого кадра и выбирать подходящую аппаратную камеру для его съемки. Напишите функцию, которая принимает желаемые характеристики программной камеры (диапазон расстояний до объекта и диапазон уровней освещенности, которые она должна поддерживать), а также список аппаратных камер с их соответствующими характеристиками и проверяет, будет ли этого набора аппаратных камер достаточно.

Comments

[alexalexes]

Пока что описание похоже на задачку о рюкзаке. Возможно, в целевой функции max на min поменять.
Если был бы пример вход/выход данных, тогда точно будет понятно.

Answer 1

[Wataru]

Rsa97 правильно написал про геометрический смысл. Но есть более быстрое решение за O(n log n), использующее метод заметающей прямой.

Пересеките все прямоугольники с тем, который надо покрыть, отрезав от них торчащую наружу часть.

Если числа в задаче большие или нецелые, то сначала через бинпоиск или хешмап замените все координаты по X и по Y на их порядковый номер в отсортированном массиве (отдельно по каждой оси). Эта операция называется "сжатие координат". Теперь у вас все координаты целые числа от 0 до 2*n.

Потом примените алгоритм "заметающей прямой". Представьте, что вертикальная линия двигается слева-направо и "заметает" картинку. Вам надо отслеживать, какие прямоугольники ее пересекают в каждый момент времени и проверить, что вся прямая покрыта в каждый момент.

Для этого каждый прямоугольник (X1, Y1, X2, Y2) создаст 2 события "открылся отрезок с Y1 до Y2 во время X1" и "закрылся отрезок с Y1 до Y2 во время X2". Эти все события вы сортируете по X и в таком порядке обрабатываете.

Для отслеживания состояния прямой используйте дерево отрезков на минимум с отложенной суммой. Эта структура данных потребует массив на примерно 4n элементов для дерева с 2n листами. Каждая вершина будет хранить минимум на соответсвующем ей отрезке. При открытии прямоугольника вы должны добавить +1 на его отрезок. При закрытии - вычесть 1. Сначала открывайте прямоугольники, если время у событий одинаковое. Учитывайте это при сортировке. Так касающиеся по вертикали прямоугольники не создадут пустых мест.
Если после обработки какого-либо события вы получили минимум в дереве отрезков 0 и следующее событие имеет большую координату по X - то какая-то часть оказалась не покрыта. Еще есть случай, если первое событие не X1=левая граница покрываемого прямоугольника, или последнее событие - не X2=правая граница всего прямоугольника. Тут тоже покрытия нет.

Еще, аккуратно с целыми числами, чтобы если у вас 2 прямоугольника касаются горизонтальными сторонами - там пустое место не подсчиталось. Например, каждый лист дерева отвечает за единичный отрезок координат. Тогда изменяйте в дереве всегда отрезок от Y1 до Y2-1 для события с координатам Y1..Y2.

Comments

[Alexandroppolus]

Если после обработки какого-либо события вы получили минимум в дереве отрезков 0 и следующее событие имеет большую координату по X

второе условие можно не проверять, в сортировке по Х сначала идут "открывашки" при равенстве Х

[Wataru]

Alexandroppolus, Нет, тут проблема в самом начале, например. Дерево пустое. Открыли вы один прямоугольник, в дереве куча нулей. Но они закроются другими прямоугольниками в этот же момент времени.

[Rsa97]

Как будет выглядеть дерево в случае пересекающихся и/или вложенных отрезков, например [(0, 4), (1, 3) (2, 5)]? Предварительно придётся разбить их на непересекающиеся интервалы?
Но тогда нужно ли здесь дерево? Ведь если мы при стратегии "сначала сложение, потом вычитание" в какой-то момент на каком-либо интервале получили ноль, то нам этот ноль незачем распространять выше, интервале то уже не заполнен.
И что тогда со сложностью? У нас максимум 2n событий, для каждого события нам надо обработать максимум 2n-1 интервалов, то есть получаем O(n²)?

[Wataru]

Rsa97, Не надо ничего разбивать. Дерево отрезков работает над массивом в 2n элементов. Пусть тут будет от 0 до 7. Корень отвечает на все 8 элементов, 2 ребенка - за 2 половинки: 0..3 и 4..7. И т.д. до листьев, которые отвечают за один элемент. Каждая вершина хранит минимум из двух детей. Обычно их хранят в массиве так что у вершины i дети 2*i+1 и 2*i+2.

Для отрезков [(0, 4), (1, 3) (2, 5)] вы получите массив вида

[0,    1, 0,    1, 2, 0, 0,   1, 2, 3, 2, 1, 0, 0, 0]

. Последние 8 элементов изменены за счет +1 от всех трех отрезков и хранят, сколько отрезков покрывает [i..i+1]. Предыдущие 7 элементов хранят минимум. Так что видно, что в корне 0, а значит на всем отрезке 0..8 есть пустые места. Но чуть дальше стоит 1, а значит отрезок 0..4 покрыт хотябы по одному разу.

Добавление на отрезке делается чуть сложнее, через отложенное добавление - надо хранить второй массив, сколько на всем текущем отрезке надо добавлять, и при выполнении операции идти рекурсивно от корня к листьям, пока нельзя весь текущий отрезок увеличить на 1, тогда эта 1 добавляется во второй массив. А при поиске минимума (тоже рекурсивно) надо перед любым обращением к вершине сначала спустить отложенное добавление в двух ее детей.

Работает за O(log n) и добавление на отрезке и проверка минимума на отрезке.

[Rsa97]

Wataru,

А при поиске минимума (тоже рекурсивно) надо перед любым обращением к вершине сначала спустить отложенное добавление в двух ее детей.

То есть, добавляя, например, интервал (1, 6) мы всё равно будем добираться до всех листьев в этом интервале?
И только ли при поике минимума? Или при любой следующей операции, в которой приходится заходить в детей?

[Wataru]

Rsa97,

То есть, добавляя, например, интервал (1, 6) мы всё равно будем добираться до всех листьев в этом интервале?

Нет. Мы же останавливаемся, когда текущая вершина покрыта целиком обновляемым отрезком. Не надо спускаться до листьев. В итоге спустимся до O(log n) вершин. Так, 1..6 разбивается на 1..3 и 4..6. 1..3 - на 1..1 и 2..3, а 4..6 - на 4..5 и 6..6.

Так же и при поиске минимума: рекурсинво спускаемся, пока текущая вершина не станет целиком лежать в искомом отрезке.

Мы обойдем максимум 4log n вершин, это можно доказать. После первого же деления пополам, потому что искомый отрезок есть и слева и справа, будет ситуация, что искомый отрезок касается отрезка-вершины с одного конца. В этом случае второе деление пополам сразу завершит одну из веток.

[Rsa97]

Wataru, Спасибо, теперь понял логику. При каждом обращении к детям помимо самого изменения тянем вглубь ещё и отложенное изменение от родителя.

Answer 2

[Rsa97]

Геометрически здесь задача проверки, что заданный в координатах X(distance) - Y(light) прямоугольник полностью покрывается набором других прямоугольников.
Как вариант, формируем общий список левых и правых границ всех покрывающих прямоугольников по X, сортируем его, слева и справа ограничиваем целевым прямоугольником, затем для каждого интервала проверяем, что он полностью покрывается по Y.
Например:
Целевой прямоугольник (1, 1)-(6, 6)
Покрывающие прямоугольники: (0, 0)-(3, 4), (2, 1)-(7, 5), (0, 3)-(6, 7)
Составляем список границ по X: 0, 3, 2, 7, 0, 6
Удаляем дубли, сортируем и ограничиваем по [1, 6]: 1, 2, 3, 6
Для каждого интервала составляем список интервалов по Y и объединяем интервалы:
[1, 2]: [0, 4] + [3, 7] = [0, 7], что перекрывает целевой [1, 6]
[2, 3]: [0, 4] + [1, 5] + [3, 7] = [0, 7], что перекрывает целевой [1, 6]
[3, 6]: [1, 5] + [3, 7] = [1, 7], что перекрывает целевой [1, 6]
На всех интервалах полное покрытие, значит целевой прямоугольник покрывается полностью.
Сложность, правда, высокая - n².

Answer 3

[mayton2019]

Мы ищем функцию select_camera следующего вида. (На неком подобии Python/Scala)

case class Range(begin:Double,end:Double)

case class CameraProps(distance_range : Range, luminosity_range : Range) 

def select_camera(distance : Double, luminosity : Double, cams : List[CameraProps]) : List[Int] = {
  ....
}

По смыслу мы можем найти не одну а много камер, удовлетворяющих условию. Тоесть результат
это - список камер.

По реализации - это похоже на поиск точки, которая попадает в прямоугольники.

Быстрые алгоритмы и структура это QuadTree-s, R-Trees (Antonin Guttman).
И те и другие - подходят. Они по сути - вспомогательные структуры для ускорения поиска камер.

При условии что точка будет двигаться а камеры стоят стационарно а искать надо много.

Если двигаются и камеры и точки - то тогда надо искать другие структуры данных.