Оптимизация разбиения графа

Эта проблема

У меня есть набор местоположений на плоскости (на самом деле это булавки в файле KML), и я хочу разбить этот граф на подграфы. Связь довольно хорошая — как и во всех реальных дорожных сетях — поэтому я предполагаю, что если два места расположены близко, у них есть какая-то связь. Результирующий набор подграфов должен соответствовать следующим ограничениям:

  • Каждый узел должен быть покрыт подграфом
  • Каждый узел должен быть ровно в 1 подграфе
  • Каждый узел в подграфе должен быть близок друг к другу (нормальные расстояния L2).
  • Каждый подграф должен содержать не менее 5 местоположений.
  • Количество подграфов должно быть минимальным

На данный момент количество локаций не превышает 100, поэтому я думал о переборе всех возможностей, но это, очевидно, не будет хорошо масштабироваться.

Я думал об использовании некоторого алгоритма k-Nearest-Neighbors (например, используя QuickGraph), но Я не могу понять, с чего начать и как расширять/сокращать подграфы по пути. Возможно, эту задачу можно сопоставить с другой задачей, которую можно легко решить с помощью какой-либо численной процедуры (например, Simplex) ...

Может быть, у кого-то есть опыт решения подобных проблем с оптимизацией, и он готов помочь мне найти решение? У меня нет доступа к Mathematica/Matlab и т.п., но есть достаточные навыки программирования на .NET и хммм Excel :-)

Большое спасибо!


person mfeineis    schedule 21.07.2014    source источник


Ответы (1)


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

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

Если у вас есть такая функция, присваивающая разделам их соответствующие «значения», вам просто нужно оптимизировать ее, и тогда вы, надеюсь, получите хорошее решение, если вы разумно определили свою служебную функцию. Эволюционные алгоритмы хорошо справляются с этой задачей, поскольку ваша функция полезности, вероятно, слишком сложна для аналитического решения из-за ее дискретного характера.

Проблема заключается только в том, как вы назначаете «значения» разделам с помощью этой служебной функции. Тогда это ваша задача. Это можно сделать, например, взвешивая каждый критерий с коэффициентом и суммируя результаты, или даже более сложные функции (наименьшие квадраты и т. д.). Факторы, которые вы используете в определении функции полезности, являются параметрами настройки и могут варьироваться до тех пор, пока результат не будет казаться хорошим.

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

person infty10000101    schedule 06.08.2014
comment
Спасибо за совет, подход кажется разумным - я думаю, что функция рейтинга несколько сложна :-) - person mfeineis; 07.08.2014
comment
Это так сложно, как вы хотите, чтобы это было. Это может быть очень легко, например. просто суммируя рейтинг по каждому критерию и оптимизируя его. Я использовал аналогичный подход для многокритериальной задачи оптимизации в своей диссертации, и он работал нормально. - person infty10000101; 07.08.2014