Эта проблема
У меня есть набор местоположений на плоскости (на самом деле это булавки в файле KML), и я хочу разбить этот граф на подграфы. Связь довольно хорошая — как и во всех реальных дорожных сетях — поэтому я предполагаю, что если два места расположены близко, у них есть какая-то связь. Результирующий набор подграфов должен соответствовать следующим ограничениям:
- Каждый узел должен быть покрыт подграфом
- Каждый узел должен быть ровно в 1 подграфе
- Каждый узел в подграфе должен быть близок друг к другу (нормальные расстояния L2).
- Каждый подграф должен содержать не менее 5 местоположений.
- Количество подграфов должно быть минимальным
На данный момент количество локаций не превышает 100, поэтому я думал о переборе всех возможностей, но это, очевидно, не будет хорошо масштабироваться.
Я думал об использовании некоторого алгоритма k-Nearest-Neighbors (например, используя QuickGraph), но Я не могу понять, с чего начать и как расширять/сокращать подграфы по пути. Возможно, эту задачу можно сопоставить с другой задачей, которую можно легко решить с помощью какой-либо численной процедуры (например, Simplex) ...
Может быть, у кого-то есть опыт решения подобных проблем с оптимизацией, и он готов помочь мне найти решение? У меня нет доступа к Mathematica/Matlab и т.п., но есть достаточные навыки программирования на .NET и хммм Excel :-)
Большое спасибо!