вариация на обложке - PullRequest
Новая
       6

вариация на обложке

3 голосов
/ 23 ноября 2010

Задача оптимизации покрытия набора: для заданного юниверса U и набора S подмножеств U (т. Е. S \ subsetof 2 ^ U) найти минимальное подмножество C из S таких что объединение его элементов U. Известно, что NP-хард.

Вариант, который меня интересует, с учетом тех же вещей (U и S) найти минимальное подмножество C из S, такое, что C является прикрытием, а также для некоторых ( элемент u в U, все наборы в S, содержащие u, находятся в C.

Проблема, к которой я применяю это: с учетом ряда симптомов, которые я вижу (U), у меня есть потенциальные причины этих проблем (S - каждый элемент S соответствует «причина» потенциально множественных симптомов). Мне нужно наименьшее количество причин, которые могут вызвать все симптомы, которые я вижу, и я также хочу получить результат, который устранит все эти «причины», что также приведет к устранению хотя бы одного симптома.

Есть ли у кого-нибудь хорошие идеи о том, проще ли это, чем первоначальная проблема?

ИЗМЕНИТЬ, чтобы включить решение (включая комментарии)

Это по крайней мере так же сложно, как установить крышку.

SetCover(U,S) может быть решено через SetCoverNew(U + {w}, S + {{w}}), где w является элементом, не входящим в U и +, обозначающим объединение множеств.

Любое решение данного экземпляра SetCoverNew должно включать набор {w} (в противном случае это не набор покрытия U + {w}).

Утверждается, что решением SetCover(U,S) является X = SetCoverNew(...) \ {{w}}. Во-первых, X должен быть обложкой U, в противном случае X + {{w}} не может быть обложкой U + {w}. Во-вторых, X должен быть минимальным покрытием U, в противном случае SetCover(U,S) + {{w}} - покрытие с меньшим количеством элементов, чем SetCoverNew(...).

Ответы [ 2 ]

3 голосов
/ 23 ноября 2010

Это также NP-Hard, так как мы можем решить эту проблему с помощью оригинального покрытия.
Предположим, мы снабжены алгоритмом, который решает эту новую проблему (называется SetCoverNew).

Вот алгоритм для решения SetCover. 

SetCover(U, S)
  1. build new universe U1 = {U + w} (w is not in `U`, and `+` means `union`).
  2. build the new set S1 = S + {w}.
  3. result = SetCoverNew(U1, S1, w)
  4. return result - {w}.

EDIT извините, я не видел unspecified u позвольте мне обдумать это :)

0 голосов
/ 23 ноября 2010

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

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

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

...