Итак, я работал над алгоритмом. Задача, которую я пытаюсь решить, такова: рассмотрим двумерную плоскость, в которой есть цели, случайным образом распределенные между верхней и нижней границей. Это множество T. T1 помечен координатами (X, Y). Существует набор S датчиков, которые гарантированно покрывают каждую цель, каждый датчик имеет радиус 1 и координату (X,Y). Каждая цель имеет стоимость (с), которая представляет собой вес. Итак, моя задача состоит в том, чтобы найти минимальный вес или стоимость набора S', покрывающего каждый сенсор.
Итак, я знаю, что между дисками, которые «доминируют» или «контролируют» другие диски, существует рекурсивная связь, но я не вижу свойства, показывающего, как использовать доминирование дисков. Я зашел так далеко:
Пусть D+ — множество кругов, центр которых лежит над полосой (верхние круги).
Пусть D- — множество дисков, центр которых лежит ниже полосы (нижние диски).
Рассмотрим верхний диск d, и d пересекает вертикальную линию L. Говорят, что другой верхний диск d' контролируется или доминируется диском d, если выполняется одно из следующих условий: (1) d' не пересекает L (2) нижний диск конечная точка пересечения d' и L выше нижней конечной точки пересечения d и L (3) нижняя конечная точка пересечения d' и L идентична нижней конечной точке пересечения d и L, но центр d' находится на справа от центра д.
Точно так же для нижнего диска d и d пересекает вертикальную линию L. Говорят, что другой нижний диск d' находится под контролем или доминированием d, если выполняется одно из следующих условий: (1) d' не пересекает L (2) верхняя конечная точка пересечения d' и L ниже верхней конечной точки пересечения d и L (3) верхняя конечная точка пересечения d' и L идентична верхней конечной точке пересечения d и L, но центр d' находится справа от центра d. Пример:
Но у меня возникли проблемы с доработкой алгоритма. любая помощь? Это ясно?
Спасибо, Кристофер
