Комплексные комбинаторные алгоритмы

Question

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

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

Это довольно просто. Вы умножаете количество вариантов вместе, поэтому для Венди это:

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256

Если бы они разнообразили свой выбор горчицы, как указано выше, это было бы:

2 * 2 * 3 * 2 * 2 * 2 * 2 * 2 = 384

Идти дальше кажется труднее.

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

Например, конфигуратор компьютера Dell запрещает определенные комбинации (возможно, все слоты заполнены, элементы несовместимы при установке в одну и ту же систему и т. Д.).

• Каковы подходящие комбинаторные подходы при работе со значительно более сложными системами, в которых предметы могут конфликтовать?
• Каковы хорошие, обобщенные подходы к хранению такой информации без необходимости кодировать каждый продукт / комбинацию / элемент для выявления конфликтов?
• Есть ли простой способ сказать: «Есть X способов настроить вашу систему / сэндвич», когда системе приходится иметь дело со сложными конфликтующими комбинациями?

Answer 1

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

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

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

Студент-информатик, имеющий опыт работы в компиляторах, распознал бы код.Код анализировал спецификацию, создавая внутреннее многопоточное дерево частей, сгруппированных по типу.Затем он применил правила к внутреннему дереву, чтобы определить, соответствует ли заказ.

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

Answer 2

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

Определение проблемы

Что ж, это проблема с графиком ( не все ли ), у вас есть предметы, совместимые с другими предметами. Например, Pentium i3-2020 совместим с любым Socket 1155 Motherboard, Asrock H61M-VS - это Socket 1155 Motherboard, который совместим с 2xDDR3 (скорость = 1066) и требует PCI-Express GPU, DDR3 PC RAM{Total(size) <= 16GB}, 4 pin ATX 12V power и т. Д.

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

Структуры данных, которые вам понадобятся

Вам понадобится простая система классификации, т.е. H61M-VS Материнская плата , H61M-VS имеет слот памяти DDR3 (со скоростными характеристиками для каждого слота). ).

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

Тестирование на удовлетворительную корзину

Чтобы протестировать корзину, необходимо создать конфигурацию, определяющую, с какими элементами сопоставляются (например, слот DDR3 материнской платы соответствует 4 Гб оперативному модулю, кабель жесткого диска SATA подключается к порту SATA материнской платы и кабелю питания SATA блока питания, а блок питания - к блоку питания). 4-контактный кабель питания ATX 12 В подключается к материнской плате.

Самое простое - просто проверить, существует ли другой удовлетворительный предмет

Компьютерный конфигуратор Dell

Вы начинаете с одного предмета, скажем, Процессор. Для процессора требуются материнская плата и вентилятор, поэтому вы можете выбрать для них материнскую плату (добавив процессор-вентилятор к list_of_things_to_be_satisfied). Это продолжается до тех пор, пока в list_of_things_to_be_satisfied не останется больше предметов. Конечно, все это зависит от ваших точных требований и знания , какую проблему (проблемы) вы решите для пользователя.

Answer 3

Есть много способов реализовать это в коде, но, по моему скромному мнению, лучший способ решить проблему перед программированием:

Определение деталей и продуктов (предварительный код)

При определении всех «частей» будет иметь первостепенное значение для определения иерархии и категоризации для частей. Это верно, потому что некоторые правила могут быть исключительными для уникальной части (например, "только коричневая горчица") , некоторые категориальные (например, "все горчицы") , некоторые по типу (например, "все приправы") и т. Д.

Наборы правил построения (пре-код)

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

Это может звучать глупо, но нужно позаботиться о том, чтобы правила были определены в соответствующем объеме. Например, если готовый продукт представляет собой Burger:

• Правило уникального предмета - "Грибы доступны только с выбранным Голубым сыром" prerequisite
• Категориальное правило - «Можно выбрать только 1 горчицу» exclusive
• Правило типа - «Соленья несовместимы с перцем» exclusive

Потратив так много времени на уникальные правила / категории / типы для "деталей", многие дизайнеры будут игнорировать правила, которые применяются только к готовому продукту, даже если у деталей нет конфликта.

• Правило продукта - "Максимум 5 приправ" condition
• Правило продукта - "Бургер должен иметь булочку" prerequisite

Этот график правил может быстро стать очень сложным.

Предложения по построению структур данных (код)

1. Убедитесь, что ваши структуры соответствуют иерархии и категоризации. Например: «коричневая горчица» и «дижонская горчица» являются отдельными объектами, и они оба горчицы, и оба приправы.

   Тщательно выберите правильную комбинацию моделирования наследования (базовые классы) и атрибутов объекта (например, свойство Category или флаг HasCondiments), чтобы эта работа работала.

2. Создайте личное поле для RuleSets на каждом уровне иерархического объекта.

3. Сделать общедоступными свойствами для флага HasConflicts и коллекции RuleViolations.

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

Напишите свои алгоритмы (код)

Это то, где я отстой, и это хорошо, так как это выходит за рамки вашего вопроса.

Уловка с этим шагом будет заключаться в том, как реализовать в коде правила, которые перемещаются вверх по дереву / графику - например, когда конкретная часть имеет проблему с другой деталью вне ее области действия, или как ее проверка выполняется, когда другая часть добавлена? Моя мысль:

1. Используйте методологию public function для каждой части. Передайте коллекцию CurrentParts товара.

2. В объекте Product задайте обработчики, определенные для обработки OnPartAdded и OnPartRemoved, и перечислите коллекцию CurrentParts и вызовите функцию проверки каждой части.

Пример прототипа "Голые кости"

interface IProduct
{
    void AddPart();
    void OnAddPart();
}
// base class for products
public class Product() : IProduct
{
     // private or no setter. write functions as you like to add/remove parts.
    public ICollection<Part> CurrentParts { get; };
    // Add part function adds to collection and triggers a handler.
    public void AddPart(Part p)
    {
        CurrentParts.Add(p);
        OnAddParts();
    }
    // handler for adding a part should trigger part validations
    public void OnAddPart()
    {
        // validate part-scope rules, you'll want to return some message/exception
        foreach(var part in CurrentParts) {
            part.ValidateRules(CurrentParts); 
        }
        ValidateRules(); // validate Product-scope rules.
    }
}

interface IProduct
{
    // "object" should be replaced with whatever way you implement your rules
    void object RuleSet; 
    void ValidateRules(ICollection<Part> otherParts);
}
// base class for parts
public class Part : IPart
{
    public object RuleSet; // see note in interface.

    public ValidateRules(ICollection<Part> otherParts)
    {
        // insert your algorithms here for validating 
        // the product parts against this part's rule set.
    }
}

Красиво и чисто.

Answer 4

Как программист, я бы сделал следующее (хотя мне никогда не приходилось делать это в реальной жизни):

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

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

Answer 5

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

В Северной Америке автомобильные номерные знаки могут быть интересной комбинаторной проблемой при подсчете всех перестановок, где существует 36 возможных значений для каждого места из 6 или 7, которые являются длинами номерных знаков в зависимости от того, где вы получаете номерной знак , Однако некоторые комбинации дисквалифицируются из-за того, что в некоторых из них содержатся нецензурные или расистские слова, что делает проблему несколько сложнее. Например, есть недобросовестное N-слово, в котором есть хотя бы пара различных вариантов написания, которые я бы не допустил на номерных знаках.

Другим примером может быть определение всех различных порядков слов с использованием заданного алфавита, который содержит некоторые элементы, повторенные несколько раз. Например, если кто-то хотел по-разному расположить буквы, скажем, слово «буква», это не просто 6! что может быть в случае с «abcdef», потому что есть две пары букв, которые делают его немного сложнее для вычисления.

L33t может быть еще одним способом усложнить определение неуместных слов, так как в то время как задница подвергается цензуре, $$ или @ss могут необязательно трактоваться одинаково, даже если это в основном тот же термин выражается по-разному. Я не уверен, что на номерных знаках появилось бы много специальных символов, таких как $ или @, но можно было бы подумать, что родительский контроль над веб-контентом должен иметь такие алгоритмы, чтобы определить, какие термины подвергать цензуре.

Answer 6

Вероятно, можно формализовать проблему как задачу k-sat . В некоторых случаях проблема кажется NP-полной, и вам придется перечислить все возможности проверить, удовлетворяют ли они или не все условия. В некоторых других случаях проблема будет легко разрешима (например, когда требуется несколько условий). Это активная область исследований. Соответствующие ссылки вы найдете в Google Golopar.

В случае горчицы вы должны добавить двоичную запись "mustard_type" для типа горчицы и ввести условие: not (not mustard and mustard_type) где mustard - двоичная запись для горчицы. Это навязывает выбор по умолчанию mustard_type == 0, когда вы выбираете not mustard.

Для выбора кунжута это более явно: not (sesame and not bun).

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

Answer 7

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

sandwitch
|
|__Bun(2)__sesame(1)
|
|__Mustard(3)
|
|__Mayo(2)
|
|__Ketchup(2)
|
|__Olives(3)

это просто говорит о том, что у вас есть 2 варианта для булочки (булочка или без булочки) - 1 для кунжута (только если у вас есть булочка - обозначение зависимости) - если у вас есть 7 здесь, это означает 7 типов, которые могут существовать если у вас есть только булочка)

3 для горчицы и т. Д.

затем просто умножьте сумму всех ветвей.

Answer 8

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

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