Генерация ограниченных множеств по порядку

Question

Сначала я вставлю сценарий, а затем задам свой вопрос:

Предположим, у вас есть список категорий, например:

Food,Meat,Dairy,Fruit,Vegetable,Grain,Wheat,Barley

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

Вот примерный список элементов: Pudding,Cheese,Milk,Chicken,Barley,Bread,Couscous,Fish,Apple,Tomato, Banana,Grape,Lamb,Roast,Honey,Potato,Rice,Beans,Legume,Barley Soup

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

Например, Cheese - это Food и Dairy.

Каждый элемент имеет два атрибута:
1) Ценник
2) Случайное значение

Набор определяется как привязка каждой категории к элементу.
Другими словами, все категории должны присутствовать в наборе.

Набор из вышеперечисленных предметов может быть следующим:

[Pudding,Lamb,Milk,Apple,Tomato,Legume,Bread,Barley Soup]

Как вы видите, каждый предмет привязан к слоту категории:

• Пудинг сопоставлен с категорией продуктов питания
• Ягненок сопоставлен с категорией мяса
• Молоко сопоставлено с категорией молочных продуктов
• Яблоко сопоставлено с категорией фруктов
• Помидорсоответствует овощной категории
• бобовые привязаны к зерновой категории
• хлеб сопоставлен с пшеничной категорией
• ячменный суп сопоставлен с ячменной категорией

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

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

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

Надеюсь, я ясен, спасибо!

Answer 1

---

Мне удалось решить эту проблему только с помощью представленного мной решения.

Я надеюсь найти лучшее решение.

Введение

Корневой набор определен как лучший набор из всех элементов.

Ключевые наблюдения этой проблемы следующие:

1. Если мы заменим 2 элемента вКорневой набор, заменяющий 1 элемент, не означает, что он будет автоматически лучше.Поскольку мы можем заменить очень плохой элемент, хотя он всего 1, однако 2 элемента, которые мы используем для замены в корневом наборе, могут дать лучший набор в целом.То же самое относится к любому количеству элементов, то есть 4 замены могут быть лучше, чем просто 1 замена в некоторых случаях.
2. Мы также должны понимать эффективность не генерации дублирующих наборов ни в одном решении.

Решение 1:

Первым шагом является создание корневого наилучшего набора, действительного или недействительного.Мы делаем это, сначала сортируя список элементов по возрастанию и убыванию.И выбирайте один предмет за предметом и помещайте его в его категорию, пока мы не получим полный набор.

Затем мы делаем то, что мне нравится называть delta sort или relative sort.Все, что он делает, это просто берет каждый элемент и пытается вычесть значение из соответствующей категории в корневом наборе, что дает нам дельту или значение относительно категории элемента в корневом наборе.Если мы добавим категории, которые включают другие категории, код получится более сложным, но идея та же самая - иметь значение от минимального до максимального значения каждого элемента, сопоставленного с элементом в корневом наборе.

Теперь, когда мы имеемтакую ​​структуру мы можем генерировать потомками по порядку, из корневого набора.Каждый набор, сгенерированный из корня, добавляется в очередь с приоритетами, где лучшие наборы с точки зрения значения будут наивысшим приоритетом.

Как только мы генерируем дочерние элементы, мы удаляем родительский элемент, так как он больше не нужен, если он недействителен,Меньшее количество элементов в нашей очереди означает лучшее время для вставки.

В конечном итоге мы получим действительный набор, который мы берем из очереди.

Это все хорошо и здорово, но розовый слон в комнатечто мы не помешали нашему алгоритму генерации генерировать дубликаты наборов, что вызывает кучу ужасов.Во-первых, если мы родим 10 детей, скажем, каждый ребенок уникален, поэтому вы можете сказать, что каждый набор уникален, но что происходит, когда мы рожаем внуков?Мы создадим много дубликатов!Причина в том, что мы всегда хотим лучшую дельту, поэтому даже если у 5-го ребенка дельта хуже, чем у первого, но когда мы генерируем ее, она будет использовать лучшую дельту, которая будет такой же, как у 1-го ребенка, генерирующего 5-еребенок.Фактически мы генерируем n (n-1) / 2 дубликатов, что плохо, и вторая причина, по которой это плохо, состоит в том, что теперь наша очередь будет раздутой с теми же наборами, чтобы мы продолжали выполнять избыточные операции, что безумно неэффективнои недопустимо.

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

Исключение дубликатов - единственный способ, которым это решение работает достаточно быстро.Создание 50 лучших подходящих наборов из 133 предметов занимает около 20 секунд.Как только мы приблизились к 200, это становится очень медленным.

Чтобы ускорить процесс, я всегда могу генерировать ребенка за ребенком, а не генерировать всех детей за один снимок.

Answer 2

Хорошо, вот моя вторая попытка ответить на этот вопрос.

Допустим, у нас есть следующие входные данные

class Item {
public:
    // using single unsigned int bitwise check sets
    unsigned int category;
    int name;
    int value;
    int price;
...
};

class ItemSet
{
public:
    set<Item> items;
    int sum;
};

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

bool operator<(const Item& item1, const Item& item2) {
    if (item1.value == item2.value) {
        if (item1.price == item2.price) {
            return item1.name < item2.name;
        }
        return item1.price > item2.price;
    }
    return item1.value < item2.value;
}
...
vector<Item> v = generateTestItem();
sort(v.begin(), v.end(), greater<Item>());

Затем используйте обратный трекинг, чтобы собрать топ-сеты в кучу, пока не будут выполнены условия.Сортировка входных данных в нашем алгоритме обратного отслеживания гарантирует, что собранные данные будут самыми высокими на основе самых высоких значений value и самых низких price.Еще одна вещь, которую стоит отметить, я сравнил категории элементов (currentCats) с битовыми манипуляциями, что дает O(1) сложность.

priority_queue<ItemSet> output;
void helper(vector<Item>& input, set<Item>& currentItems, unsigned int currentCats, int sum, int index)
{
    if (index == input.size()) {
        // if index reached end of input, exit
        addOutput(currentItems);
        return;
    }
    if (output.size() >= TOP_X) {
        // if output data size reached required size, exit
        return;
    }
    if (sum + input[index].price < PRICE_TAG) {
        if ((input[index].category & currentCats) == 0) {
            // this category does not exists in currentCats
            currentItems.insert(input[index]);
            helper(input, currentItems, currentCats | input[index].category, sum + input[index].price, index + 1);
        }
    } else { 
        addOutput(currentItems);
        return;
    }
    if (currentItems.find(input[index]) != currentItems.end()) {
        currentItems.erase(input[index]);
    }
    helper(input, currentItems, currentCats, sum, index + 1);
    return;
}

void getTopItems(vector<Item>& items)
{
    set<Item> myset;
    helper(items, myset, 0, 0, 0);
}

В худшем случае при таком возврате будет сложность O (2 ^ N), но, поскольку TOP_X является ограниченным значением, в реальном времени это не займет слишком много времени.

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

Answer 3

Я не совсем уверен, что вы подразумеваете под "генерацией наборов по порядку".

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

Задача о ранце 0-1 , как было показано, NP-hard , что означает, что не существует известного решения за полиномиальное время (т.е. O (n ^ k)).Эта проблема такая же, как и у вас, если бы при вашем вводе случайное число всегда было равным цене и была только одна категория.Другими словами, ваша проблема, по крайней мере, так же сложна, как и проблема с рюкзаком, поэтому вы не можете ожидать, чтобы найти гарантированное решение за полиномиальное время.

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

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

Answer 4

То, что вы пытаетесь достичь, - это форма максимального соответствия, и я не знаю, существует ли эффективный способ вычисления наборов по порядку, но все же это сокращение может вам помочь.

Определитьдвудольный граф с одной стороной по одному узлу на категорию, а с другой стороны по одному узлу на единицу.Добавьте грань между элементом и категорией, если эти элементы принадлежат этой категории, с весом, определяемым случайным значением элемента.

«Набор», как вы определили, соответствует максимальному количеству элементов вэтот график.Они могут быть перечислены в разумные сроки, как доказал Такеаки Уно в « Быстрый алгоритм для перечисления небипартийных максимальных соответствий », и он, вероятно, будет еще быстрее в вашей ситуации, потому что ваш график является двудольным.

Среди этих наборов вы ищете наборы с максимальным весом и ценовым ограничением.В зависимости от ваших данных, может быть достаточно просто перечислить их все, отфильтровать их по цене и отсортировать оставшиеся результаты, если их не слишком много.

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