Какой тип алгоритма будет уместен здесь?

Question

Мне нужно разработать алгоритм для решения следующей задачи:

Рассмотрим прямую L в плоскости. Конечное множество Т мишеней расположено над линией L, а конечное множество S беспроводных датчиков расположено ниже линии L. Датчик s может контролировать цель t тогда и только тогда, когда евклидово расстояние между s и t не более один. Предположим, что каждый датчик s ∈ S имеет положительную стоимость c (s), и каждая цель t ∈ T может контролироваться по меньшей мере одним датчиком в S. Рассмотрим, что подмножество S0 датчиков в S. S0 считается крышкой, если каждый Цель в Т покрывается, по меньшей мере, одним датчиком в S0. Стоимость S0 - это общая стоимость датчиков в S0. Цель состоит в том, чтобы вычислить покрытие S0 минимальной стоимости. Пожалуйста, разработайте алгоритм полиномиального времени и напишите программу для его реализации.

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

Answer 1

Посмотрите здесь http://www.pressingquestion.com/3830657/Computing-Minimum-Cost-With-Using-Dynamic-Programming. Это вопрос, очень похожий на ваш. Решение этого вопроса указывает на то, что ваш вопрос NP-Hard, а не полиномиальный. Однако, если вы слегка измените свой вопрос таким образом, чтобы эти цели были на линиях, а не выше линии, то вы можете использовать способ динамического программирования для его решения. Подробности указаны в ссылке.

Если ваш вопрос не изменен, и вы все еще хотите использовать полиномиальное решение, то вам может потребоваться предположение, что датчики размещены в разрешенном пути . В этом случае вы можете использовать подход divide-and -quer. Отсортируйте все датчики в направлении линии (предположим, что линия L является осью x, затем сортируйте датчики по оси x), а затем разделите их на середину. Когда вы делите, вам нужно рассуждать о тех точках, координата которых находится около (не более 1) от того места, где вы делите очень тщательно. Если слишком много точек, алгоритм не будет полиномиальным, и поэтому требуется разреженное предположение.