Циклы снятия в взвешенном ориентированном графе

Question

Это следующий вопрос по другим моим сообщениям.

Algorithm for clustering with size constraints

Я работаю на алгоритм кластеризации, После некоторого reclustering, теперь у меня есть этот набор точек, что ни один из них не находятся в оптимальном кластере, но не может быть переназначен в индивидуальном порядке, так как это будет нарушить ограничение.

Я пытаюсь использовать структуру графа для решения проблемы, но столкнулся с несколькими проблемами при реализации.

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

Пер @ Kittsil отвечают

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

Я пересмотрел график, добавляя вес как сумма числа точек, движущихся от А до В.

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

Сценарий 1. Для цикла, как показано ниже. Есть две точки, которые можно переместить из А в Б, и три от В до С. В этой ситуации, какой пункт следует выбрать для переназначения?

Сценарий 2. Для цикла, как показано ниже. Пусть все веса ребер равны 1. Для точки в кластере A она может быть переназначена либо кластеру B, либо D. В этом случае. Как мне сделать переназначение?

Сценарий 3 Подобный сценарий 2. Пусть все краевые веса равен 1. Есть два небольших циклов в большом цикле. Точка в кластере A может быть переназначена как для B, так и для E, как я могу принять решение о переназначении в этом случае?

Идея о любом сценарии приветствуются!

Также есть предложения по реализации алгоритма с учетом вышеприведенных случаев? Еще лучше с псевдокодом. Благодаря!

Answer 1

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

---

Обсуждение:

Алгоритм, описанный в Algorithm for clustering with size constraints жадный алгоритм поиска локального минимума. Поэтому нет никакой гарантии, что вы найдете лучшее решение независимо от того, как вы выбираете в этих сценариях, и любой выбор приблизит вас к локальному минимуму.

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