Выбор k подпозиций

Я столкнулся с следующей алгоритмической проблемой, экспериментируя с алгоритмами классификации. Элементы классифицируются в многоиерархию, я понимаю, что это poset с одним корнем. Я должен решить следующую проблему, которая очень похожа на set cover problem.Выбор k подпозиций

Я загрузил (а) проблему с Latex-ed Описание here.

Разработка алгоритма аппроксимации, который удовлетворяет 1 & 2 довольно просто, только начинайте с вершин G и «подходите» или начинайте с корня и «идите вниз». Скажем, вы начинаете с корня, итеративно расширяете вершины, а затем удаляете ненужные вершины, пока не получите не менее k подрешеток. Оценка аппроксимации зависит от количества дочерних элементов вершины, что подходит для моего приложения.

Кто-нибудь знает, имеет ли эта проблема собственное имя или, может быть, древовидная версия проблемы? Мне было бы интересно узнать, является ли эта проблема NP-hard, может быть, у кого-то есть идеи по хорошей NP-жесткой проблеме, чтобы уменьшить или имеет полиномиальный алгоритм для решения проблемы. Если вы оба собираете your million dollar price. ;)

источник

2010-07-17 dareios

Я не понимаю. Если вы выберете S '= {r}, где r - корень, то \ sigma (r) = V. Вы имеете в виду, что сигма (ы) - все элементы, которые меньше или равны r и больше или равны s (где все меньше и больше - частичный порядок решетки)? – deinst

@deinst Вот почему 'k' есть: сделать проблему более интересной :)' S = {r} '- это решение для' k = 1'. – Bolo

@dareios Возможно, вы захотите исправить две незначительные ошибки в заявлении проблемы. 1) Второй последний абзац не является истинным в целом, зависит от выбора 'G' (если я что-то не упускаю, если' G' содержит двух детей и ничего больше, тогда 'S = G' является решением с' l = k = 2'. 2) В третьем последнем абзаце вы, вероятно, имеете в виду: «[...] мы все еще хотим сохранить ** 2 **». – Bolo

Версия DAG жестко (барабан рулон) сокращение от установленной крышки. Установите k = 2 и сделаем очевидное: условие (2) не позволяет нам взять корень. (Заметим, что (3) на самом деле не подразумевает (2) из-за нижней границы k.)

Дерево версия является частным случаем серийно-параллельной версии poset, которая может быть решена точно в полиномиальное время. Вот рекурсивная формула, которая дает многочлен p (x), где коэффициент при x ⁿ - количество покрытий мощности n.

Одиночная вершина, подлежащая покрытию: p (x) = x.

Другая вершина: p (x) = 1 + x.

Параллельная композиция, где q и r - многочлены для двух наборов: q (x) r (x).

Состав серии, где q - многочлен для верхнего позитива и r для дна: Если верхний набор не содержит покрываемых вершин, то p (x) = (q (x) - 1) + r (Икс); в противном случае p (x) = q (x).

источник

2010-07-17 16:45:21 user382751

Хорошее наблюдение с (3) не означает (2), я полностью пропустил это. Изменено в заявлении проблемы. Для остальных, я думаю, мне нужна первая ночь сна, спасибо за ваш ответ! – dareios

Сокращение действительно просто, не знаю, почему я не смог сделать это вчера. Благодаря! – dareios

Для формулы рекурсивной версии дерева: если у меня есть одна вершина, которую нужно покрыть, у меня есть p (x) = x, как вы говорите, так как есть только одна обложка. Для того, чтобы никакие вершины не были покрыты, мы должны иметь p (x) = 1 (поскольку покрытие пусто). Я не понимаю, когда применяется полином «Другой вершины: p (x) = 1 + x». Кроме того, я не понимаю, когда применяется «верхний poset не содержит вершин» (для покрытия): верхний poset всегда будет содержать другие posets, поэтому, если он не содержит вершин, которые должны быть покрыты, другие posets не будут или. Может быть, здесь вступает в действие ограничение> = k на минимальное свойство? – dareios

Выбор k подпозиций

ответ

Смежные вопросы