Описание тега set-cover

Описание тега Вопросы с тегом
В комбинаторике это проблема выбора минимального количества наборов, чтобы эти наборы вместе содержали все элементы, найденные в некотором ссылочном наборе.
1 ответ

Алгоритм Greedy Set Coverage, построенный на * удалении * множеств

Я пытаюсь реализовать решение для заданной проблемы покрытия, используя жадный алгоритм. Классический алгоритм жадного приближения для него input: collection C of sets over universe U , costs: C→R ≥0 output: set cover S 1. Let S←∅. 2. Repeat until S…
04 фев '13 в 07:01
1 ответ

Это минимальная проблема прикрытия?

У меня есть следующий сценарий (предварительные извинения за длину, но я хотел быть как можно более описательным): Мне представлен список "рецептов" (Ri), которые должны быть выполнены в указанном порядке, чтобы выполнить задание. Каждый рецепт сост…
14 мар '11 в 22:13
1 ответ

Измерение сложности NP-комплектного

Например, известно, что проблема решения с заданным покрытием является NP-полной проблемой. Входными данными этой проблемы является юниверс U, семейство S подмножеств U и целое число k (). Одна вещь, с которой меня смущает то, что если мы допустим k…
06 янв '14 в 07:33
1 ответ

Установить аппроксимацию покрытия в R

Я пытаюсь решить или реализовать приближение к задаче покрытия множеств в R. Приведенный кадр данных подобен этому. sets n 1 s1 1 2 s1 2 3 s1 3 4 s2 2 5 s2 4 6 s3 3 7 s3 4 8 s4 4 9 s4 5 Уникальное количество элементов в столбце n являются: unique(d$…
27 авг '16 в 18:09
1 ответ

Оптимизация результатов Itertools в Python

Я называю itertools в Python (см. Ниже). В этом коде snp_dic это словарь с целочисленными ключами и набором значений. Цель здесь - найти минимальный список ключей, объединение значений которых представляет собой комбинацию объединений множеств, экви…
22 ноя '16 в 22:47
1 ответ

Как бы я отсортировал списки часто используемых слов, чтобы найти эффективные комбинации, используя как можно более уникальные слова?

У меня есть списки наиболее часто используемых слов, полученные из общедоступных данных Google ngram. Я имею: 6800 частых 2 грамма 4800 частых 3 грамма 2500 частых 4 грамма 1100 частых 5 граммов Пример 2 Ngram будет что-то вроде: "собака", "книга", …
13 фев '13 в 21:28
2 ответа

Грубая сила сложности Set Cover

Мы можем решить проблему покрытия наборов, сформировав все возможные комбинации наборов и проверив, является ли это минимальным решением. Теперь у нас может быть не более 2^n таких комбинаций множеств, где 'n' - номер множества. Таким образом, сложн…
16 окт '14 в 09:24
0 ответов

Максимальное xor среди всех подмножеств фиксированного размера

Учитывая набор S из N битовые маски фиксированной ширины (скажем, 64-битные). И учитывая размер подмножества интересов M, Как найти такое подмножество S' из S (|S'| = M < N), тот xor из всех его элементов дает максимальное количество 1 в двоичной…
04 июл '18 в 05:33
0 ответов

Проверка возможности установки крышки

У меня есть набор массивов: [1,2,3] [1,2] [1] Мне нужно выяснить, существует ли "покрывающий набор" уникальных значений, каждое из которых соответствует значению в массиве. В этом случае набор покрытия может быть [3,2,1], Мне на самом деле не нужен …
23 ноя '17 в 17:22
1 ответ

Верхняя граница коэффициента аппроксимации для жадного алгоритма для заданного покрытия (отдельные экземпляры)

Умышленно у меня есть способ найти (и доказать) верхнюю границу коэффициента аппроксимации для жадного алгоритма, которую (границу) можно получить для отдельных случаев задачи покрытия множества. Для задач, которые у меня есть в моей библиотеке, эта…
30 мар '12 в 18:38
0 ответов

Установить покрытие (удар) на бикубических (т.е. двудольных 3-регулярных) графиках

Я пытался придумать эффективный алгоритм для решения этой проблемы. Дело в том, что я знаю, что проблема попадания в двудольных графах является NP-трудной, и то же самое относится к кубическим графам. Тем не менее, я не совсем уверен, существует ли …
23 июл '18 в 02:49
4 ответа

Вариация на задаче покрытия множества в R / C++

Учитывая универсум элементов U = {1, 2, 3,...,n} и количество множеств в этой вселенной {S1, S2,...,Sm}, какое наименьшее множество, которое мы можем создать, будет охватить хотя бы один элемент в каждом из m наборов? Например, учитывая следующие эл…
19 июл '11 в 16:42
0 ответов

Максимальная заданная обложка графика

У меня есть универсальный набор и количество наборов S. Мне нужно найти максимальное количество наборов из S, чтобы между любыми двумя выбранными наборами не было общего элемента. Мой подход --- Я рассмотрел каждый набор в S как узел, и если между д…
11 мар '14 в 10:59
1 ответ

Существуют ли какие-либо приблизительные алгоритмы в покрытии множеств, когда существует слишком много множеств, скажем, 2^n множеств?

Я недавно работаю над проблемой, которая, на мой взгляд, является ответвлением проблемы установленного покрытия. Однако число наборов в моей задаче достигает 2^n. И приблизительные алогрифы, которые я нашел, кажутся эффективными только тогда, когда …
20 июн '12 в 08:02
1 ответ

Алгоритм минимального набора покрытия: определение размера оптимального покрытия

Проблема Set-Cover состоит из следующего: Дано: Набор предметов U. Набор множеств S, каждый из которых содержит предметы из U. Найдите множество множеств C такое, что: C является подмножеством S. Наборы в C содержат все элементы в U. (хотя бы один р…
19 апр '15 в 05:30
1 ответ

Установить обложку: создание тестовых экземпляров

Я с нетерпением жду, чтобы решить проблему Set Cover, используя генетический алгоритм. Я везде искал хорошие тестовые примеры, но без особого успеха. То, что я ищу, - это несколько экземпляров в форме: набор U = {1,2,...,n} и набор его подмножеств S…
27 май '17 в 14:19
3 ответа

Минимальное умножение по сравнению с проблемой прикрытия

У меня есть набор I ={P1, P2, ..., Pm} и n конечных подмножеств I, обозначаемых через R1,R2,...,Rn следующим образом: R1 = {P1, P2} R2 = {P2, P4} R3 = {P2, P3, P4} R4 = {P1, P2, P4} .... где Pi обозначает целое число. Для каждого Ri я хочу вычислить…
30 май '12 в 16:24
1 ответ

Минимальная комплектация обложки

Я хотел бы решить проблему минимального набора покрытия следующего вида. Все списки содержат только 1 и 0. Я говорю, что список A охватывает список B если вы можете сделать B от A вставив точно x символы. Рассмотрим все 2^n списков длины 1 и 0 n и у…
24 сен '13 в 12:30
2 ответа

Запрос для Set Cover

Добрый день, я хотел бы реализовать T-SQL-запрос для решения проблемы покрытия, но не смог найти никаких подсказок о том, как это сделать в SQL. В моем случае в моей таблице только два столбца (IDnumber а также Mut) и я хочу найти минимальное количе…
28 окт '16 в 03:59
1 ответ

Какой самый быстрый способ сделать жадный набор прикрытием пандами?

Этот вопрос не совсем совпадает с проблемой покрытия жадных множеств, но они разделяют ту же идею. Для данного Pandas dataframe df1 с одним столбцом df['s'] состоит из набора ключей df2: import numpy as np import pandas as pd >>> df = pd.Da…
13 сен '15 в 18:25