Алгоритм нахождения максимального количества допустимых комбинаций? - PullRequest
Новая
       12

Алгоритм нахождения максимального количества допустимых комбинаций?

1 голос
/ 20 октября 2011

ОК ... так что у меня есть немного хитрости (для меня, по крайней мере).

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

Если элемент добавлен в коллекцию, где этому конкретному элементу «нравится» один (или более) из других элементов, уже находящихся в коллекции, то добавленный элемент возвращает оценку +1 длякаждый предмет в коллекции, который ему нравится.Аналогично, оценка -1 возвращается для каждого элемента в коллекции, который добавленному элементу не нравится.После добавления всех элементов в итоговую коллекцию оценка для каждого должна быть> = 0.

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

Надеюсь, это имело смысл ... Кроме того, я использую C # (.NET 4.0), но любой язык программированияможно использовать, мне просто нужно разобраться в логике этого.

Заранее спасибо,Sonny

1 Ответ

2 голосов
/ 21 октября 2011

Я думаю, что вы правы, говоря, что это сложная проблема.Я думаю об объектах как об узлах на графике, а информация типа «нравится / не нравится» как о весах для связей между узлами.Игнорируйте поле «Мне нравится» и присвойте всем ссылкам вес 0 или вес -1.В этом случае ваша проблема состоит в том, чтобы найти максимальное количество узлов, чтобы все ссылки между ними имели вес 0, и ни один из них не имел вес -1.Предположим, у вас есть программа, которая делает это эффективно.

Теперь рассмотрим проблему http://en.wikipedia.org/wiki/Clique_problem,, которая является известной трудной проблемой.Если у вас проблема с максимальным кликом, создайте связи между всеми узлами.Там, где два узла были связаны в максимальном клике, задайте вес 0. Если ссылки не существует, задайте вес -1.Теперь запустите программу, чтобы решить вашу проблему, и вы решили макс клика.Поэтому я думаю, что ваша проблема - NP-Complete, и вряд ли найдется эффективное решение для нее.

...