Блог

Детали немного пугают, справедливое предупреждение, лол:

Я хочу настроить счетчики на этаже моего здания, чтобы поймать кого-то; предположим, что мой этаж — это числовая строка от 0 до длины L. Конкретный тип измерителя, который я разрабатываю, имеет радиус обнаружения, который составляет 4,7 метра в направлении -x и x (диаметр обнаружения 9,4 метра). Я хочу настроить их таким образом, чтобы, если человек, которого я пытаюсь найти, ступит в любую точку пола, я буду знать. Однако я не могу просто установить счетчик в любом месте (это может раздражать других жителей); поэтому есть только n допустимых местоположений, в которых я могу установить счетчик. Кроме того, эти счетчики дороги и требуют много времени, поэтому я хотел бы использовать как можно меньше.

Для простоты вы можете предположить, что счетчик имеет ширину 0, и что каждое допустимое местоположение — это просто точка на упомянутой числовой строке. Что такое жадный алгоритм, который размещает как можно меньше метров, будучи в состоянии обнаружить весь коридор длиной L, как я хочу, или, если обнаружение всего коридора невозможно, выведет false для набора из n местоположений, которые у меня есть (и, если он не способенчтобы обнаружить весь коридор, все еще использует как можно меньше метров при попытке сделать это)?

Редактировать: некоторые разъяснения о возможности обнаружения всего коридора или нет

Учитывая:

• L (длина коридора)
• список из N допустимых позиций для размещения метра ( p_0 … p_N-1 ) радиуса 4.7

Вы можете определить в O (N) либо действительное и минимальное («хорошее») покрытие всего коридора, либо доказательство того, что такого покрытия не существует, учитывая следующие ограничения (псевдокод):

 // total = total length; 
// start = current starting position, initially 0
// possible = list of possible meter positions
// placed = list of (optimal) meter placements, initially empty
boolean solve(float total, float start, List<Float> possible, List<Float> placed):

   if (total-start <= 0): 
        return true; // problem solved with no additional meters - woo!
   else:
        Float next = extractFurthestWithinRange(start, possible, 4.7);
        if (next == null):
             return false; // no way to cover end of hall: report failure
        else:
             placed.add(next); // placement decided
             return solve(total, next   4.7, possible, placed); 
  

Где extractFurthestWithinRange(float start, List<Float> candidates, float range) возвращает null , если внутри нет candidates range start , или возвращает последнюю позицию p в candidates таком, что p <= start range — а также удаляет p , и все кандидаты c такие, что p >= c .

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

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

 // remaining = length (starts at hallway length)
// possible = positions to place meters at, starting by closest to end of hallway
// placed = positions where meters have been placed
boolean solve(float remaining, List<Float> possible, Queue<Float> placed):

   if (remaining <= 0): 
        return true; // problem solved with no additional meters - woo!
   else:
        // extracts points p up to and including p such that p >= remaining - range
        Float next = extractFurthestWithinRange2(remaining, possible, 4.7);
        if (next == null):
             return false; // no way to cover start of hall: report failure
        else:
             placed.add(next); // placement decided
             return solve(next - 4.7, possible, placed); 
  

Чтобы доказать, что ваше решение является оптимальным, если оно найдено, вам просто нужно доказать, что оно находит лексикографически последнее оптимальное решение.

И вы делаете это путем индукции по размеру лексикографически последнего оптимального решения. Случай пола нулевой длины и отсутствия монитора тривиален. В противном случае вы демонстрируете, что нашли первый элемент лексикографически последнего решения. И покрытие остальной части строки оставшимися элементами — это ваш шаг индукции.

Техническое примечание, чтобы это сработало, вам должно быть разрешено размещать станции мониторинга за пределами линии.