Ответ 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот где я сосать, и хорошо, потому что это выходит за рамки вашего вопроса.

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

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

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

Пример прототипа Bare-bones

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 rule set.
    }
}

Приятный и чистый.

Ответ 2

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

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

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

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

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

Ответ 3

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

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

Ну, это проблема графа (не все), у вас есть элементы, совместимые с другими элементами. Например, 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 и т.д.

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

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

Вам понадобится простая система классификации, то есть материнская плата H61M-VS is-a, H61M-VS имеет DDR3 слот памяти (со свойствами скорости для каждый слот).

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

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

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

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

Конфигуратор Dell Dell

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

Ответ 4

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

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

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