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

обновить:

Я немного поиграл с этой проблемой, и вот мои выводы:

Простой метод (назовем его случайным выбором) для получения набора точек, удовлетворяющих заявленному условию, заключается в следующем:

1. начните с B пустым
2. выберите случайную точку x из A и поместите ее в B
3. удалить из A каждую точку y такую, что dist(x, y) ‹ d
4. пока A не пусто перейти к 2

Kd-дерево можно использовать для относительно быстрого выполнения поиска на шаге 3.

Эксперименты, которые я провел в 2D, показывают, что сгенерированные подмножества примерно вдвое меньше, чем те, которые были сгенерированы вашим нисходящим подходом.

Затем я использовал этот алгоритм случайного выбора, чтобы запустить генетический алгоритм, который привел к дополнительному уменьшению размера подмножеств на 25%.

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

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

Я реализовал все на Perl, используя оболочку для GAUL (GAUL можно получить по адресу здесь.

Скрипт находится здесь: https://github.com/salva/p5-AI-GAUL/blob/master/examples/point_density.pl

Он принимает список n-мерных точек из стандартного ввода и генерирует набор изображений, показывающих лучшее решение для каждой итерации генетического алгоритма. Сопутствующий скрипт https://github.com/salva/p5-AI-GAUL/blob/master/examples/point_gen.pl можно использовать для генерации случайных точек с равномерным распределением.

Вы можете смоделировать свою задачу с помощью графов, принять точки за узлы и соединить два узла ребром, если расстояние между ними меньше, чем d. Теперь вам нужно найти минимальное количество вершин, чтобы они были связаны вершины покрывают все вершины графа, это минимальная проблема покрытия вершин (что в общем случае является NP-Hard ), но вы можете использовать быструю 2-аппроксимацию: неоднократно брать обе конечные точки ребра в вершинное покрытие, а затем удалять их из графа.

P.S: конечно, вы должны выбрать узлы, которые полностью отключены от графа. После удаления этих узлов (означает их выбор) ваша проблема заключается в покрытии вершин.

Вот предложение, в котором делается предположение о манхэттенской метрике расстояния:

1. Разделите все пространство на сетку детализации d. Формально: разбить A так, чтобы точки (x1,...,xn) и (y1,...,yn) находились в одном и том же разделе точно тогда, когда (floor(x1/d),...,floor(xn/d ))=(этаж(y1/d),...,этаж(yn/d)).
2. Выберите одну точку (произвольно) из каждого пространства сетки, то есть выберите представителя из каждого набора в разделе, созданном на шаге 1. Не беспокойтесь, если некоторые пространства сетки пусты! Просто не выбирайте представителя для этого пространства.

На самом деле, реализация не должна делать никакой реальной работы, чтобы выполнить первый шаг, а второй шаг можно выполнить за один проход по точкам, используя хэш идентификатора раздела ((floor(x1/d),.. .,floor(xn/d))) чтобы проверить, выбрали ли мы уже представителя для определенного пространства сетки, так что это может быть очень, очень быстро.

Для некоторых других показателей расстояния можно использовать адаптированный подход. Например, евклидова метрика может использовать сетки размера d/sqrt(n). В этом случае вы, возможно, захотите добавить шаг постобработки, который попытается немного уменьшить покрытие (поскольку сетки, описанные выше, больше не являются точно шарами радиуса d — шары немного перекрывают соседние сетки), но я Я не уверен, как эта часть будет выглядеть.

Чтобы быть ленивым, это можно привести к проблеме покрытия набора, с которой можно справиться с помощью решателя/оптимизаторов смешанных целочисленных задач. Вот модель GNU MathProg для решателя GLPK LP/MIP. Здесь C обозначает, какая точка может «удовлетворить» каждую точку.

param N, integer, > 0;
set C{1..N};

var x{i in 1..N}, binary;
s.t. cover{i in 1..N}: sum{j in C[i]} x[j] >= 1;
minimize goal: sum{i in 1..N} x[i];

При нормальном распределении 1000 точек он не нашел оптимальное подмножество за 4 минуты, но заявил, что знает истинный минимум, и выбрал только одну дополнительную точку.