algorithm - surge - Algoritmos Combinatorios Complejos

qué es un problema de optimización combinatoria

Question

Así que Wendy''s anuncia que su sándwich tiene 256 combinaciones, lo que significa que hay 8 ingredientes que no debes tener (aunque me pregunto por qué contarán la combinación en la que no incluyes nada válido, pero estoy divagando).

Un enfoque generalizado le permite multiplicar los diversos estados de cada selección juntos, lo que permite combinaciones más complejas. En este caso, los artículos de Wendy''s solo se pueden incluir o excluir. Pero algunos sándwiches pueden tener la opción de dos tipos de mostaza (pero no ambas, para ahorrar costos).

Estos son bastante sencillos. Multiplicas el número de opciones juntas, por lo que para Wendy''s es:

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

Si diversificasen su selección de mostaza como antes, sería:

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

Ir más lejos parece ser más difícil.

Si haces que las semillas de sésamo sean un artículo separado, entonces requieren el artículo de pan. Puede tener la semilla de sésamo solo si incluye el bollo, y puede tener el bollo sin semillas de sésamo, pero no puede tener semillas de sésamo sin el bollo. Esto se puede simplificar a un solo elemento de panecillo con tres estados (ninguno, panecillo con semillas, panecillo sin), pero hay situaciones en las que no se puede hacer.

El configurador de computadoras de Dell, por ejemplo, no permite ciertas combinaciones (tal vez las ranuras estén todas llenas, los elementos son incompatibles cuando se colocan en el mismo sistema, etc.).

• ¿Cuáles son los enfoques combinatorios apropiados cuando se trata de sistemas significativamente más complejos donde los elementos pueden entrar en conflicto?
• ¿Cuáles son los enfoques buenos y generalizados para almacenar dicha información sin tener que codificar para cada producto / combinación / artículo para atrapar conflictos?
• ¿Hay una forma sencilla de decir "hay X formas de configurar su sistema / sándwich" cuando el sistema tiene que lidiar con complejas combinaciones en conflicto?

Answer 1

" Funciones de generación " viene a la mente como una construcción que puede usarse al resolver este tipo de problema. Me gustaría señalar que hay varias funciones de generación diferentes dependiendo de lo que quieras.

En América del Norte, las matrículas de automóviles pueden ser un problema combinatorio interesante para contar todas las permutaciones donde hay 36 valores posibles para cada lugar de los 6 o 7 que son las longitudes de las matrículas, dependiendo de dónde se obtenga una placa. Sin embargo, algunas combinaciones son descalificadas debido a que en algunas de ellas hay malas palabras o palabras racistas, lo que dificulta un problema un poco más. Por ejemplo, hay una palabra N infamora que tiene al menos un par de palabras diferentes que no se permitirían en las placas de licencia, creo.

Otro ejemplo sería determinar todos los diferentes órdenes de palabras usando un alfabeto dado que contiene algunos elementos repetidos varias veces. Por ejemplo, si uno quisiera todas las formas diferentes de ordenar las letras, diga la palabra "letra", ¡no son solo 6! cuál sería el caso de "abcdef" porque hay 2 pares de letras que lo hacen un poco más complicado de calcular.

L33t puede ser otra forma de L33t más complejidad en la identificación de palabras inapropiadas, mientras que asnos se censura a $$ o @ss no necesariamente puede tratarse de la misma manera, aunque es básicamente el mismo término expresado de diferentes maneras. No estoy seguro de si muchos caracteres especiales como $ o @ aparecerían en las matrículas, pero se podría pensar que los controles parentales en el contenido web tienen que tener este tipo de algoritmos para identificar qué términos censurar.

Answer 2

Como programador, haría lo siguiente (aunque nunca he tenido que hacer esto en la vida real):

• Calcule el número total de combinaciones, por lo general, será suficiente una multiplicación directa de las opciones según lo establecido en su pregunta. No hay necesidad de almacenar todas estas combinaciones.
• Luego divide tu total por las excepciones. Las excepciones se pueden almacenar como solo un conjunto de reglas, que indican efectivamente qué combinaciones no están permitidas.
• Para calcular el número total de combinaciones permitidas, deberá ejecutar todo el conjunto de reglas de excepción.

Si piensa en todas sus combinaciones como un conjunto, entonces las excepciones simplemente eliminan a los miembros de ese conjunto. Pero no necesita almacenar todo el conjunto, solo las excepciones, ya que puede calcular el tamaño del conjunto con bastante facilidad.

Answer 3

Es probable que desee crear una estructura de datos que represente una configuración individual de forma única. Luego, cada regla de compatibilidad debe definirse de manera que pueda generar un conjunto que contenga todas las configuraciones individuales que fallan en esa regla. Luego tomaría la unión de todos los conjuntos generados por todas las reglas para obtener el conjunto de todas las configuraciones que fallan en las reglas. Luego cuenta el tamaño de ese conjunto y lo resta del tamaño del conjunto de todas las configuraciones posibles.

La parte difícil es definir la estructura de datos de una manera que pueda ser generada por sus reglas y que las operaciones de configuración funcionen en ella. Eso es un ejercicio para el lector, AKA No tengo nada.

Answer 4

Hay muchas maneras de implementar esto en el código, pero aquí es en mi humilde opinión, la mejor manera de resolver el problema antes de programar algo:

Definir Partes y Productos (Pre-código)

Al definir todas las "partes" será primordial identificar la jerarquía y la categorización de las partes. Esto es cierto porque algunas reglas pueden ser exclusivas de una parte única (por ejemplo, "solo mostaza marrón") , algunas categóricas (por ejemplo, "todas las mostazas") , algunas por tipo (por ejemplo, "todos los condimentos") , etc.

Construir conjuntos de reglas (precódigo)

Defina los conjuntos de reglas (requisitos previos, exclusiones, etc.) para cada pieza, categoría, tipo y producto final únicos.

Puede parecer tonto, pero se debe tener mucho cuidado para garantizar que las reglas se definan con un alcance adecuado. Por ejemplo, si el producto terminado es una Burger :

• Regla de artículo único: "Setas solo disponibles con queso azul seleccionado" prerequisite
• Regla categórica - "Solo 1 mostaza puede ser seleccionada" exclusive
• Regla de tipo - "Pickles son incompatibles con Peppers" exclusive

Después de haber pasado tanto tiempo en reglas únicas / categoría / tipo para "partes", muchos diseñadores pasarán por alto las reglas que se aplican solo al producto terminado, incluso cuando las partes no tienen conflicto.

• Regla del producto - condition "máximo 5 condimentos"
• Regla del producto - "Burger debe tener un bollo" prerequisite

Este gráfico de la regla puede crecer rápidamente muy complejo.

Sugerencias para construir estructuras de datos (código)

1. Asegúrese de que sus estructuras se adapten a la jerarquía y la categorización. Por ejemplo: "mostaza marrón" y "mostaza dijon" son objetos individuales, y ambos son mostazas y condimentos.

   Seleccione cuidadosamente la combinación correcta de modelado de herencia (clases base) y atributos de objeto (por ejemplo, propiedad de Category , o bandera HasCondiments ) para hacer que esto funcione.

2. Haga un campo privado para RuleSets en cada nivel de objeto jerárquico.

3. Haga propiedades públicas para un indicador HasConflicts y una colección RuleViolations .

4. Cuando se agrega una parte a un producto, verifique todos los niveles de las reglas (su propia categoría, tipo y producto); hágalo a través de una función pública a la que se puede llamar desde el producto. O para una mejor internalización, puede hacer un controlador de eventos en la parte en sí.

Escribe tus algoritmos (Código)

Aquí es donde apesto, y bueno, ya que está más allá del alcance de tu pregunta.

El truco con este paso será cómo implementar en el código las reglas que viajan por el árbol / gráfico, por ejemplo, cuando una parte específica tiene un problema con otra parte fuera de su alcance, o cómo se ejecuta la validación cuando se utiliza otra parte. ¿adicional? Mi pensamiento:

1. Utilice una metodología de función pública para cada parte. CurrentParts colección CurrentParts del producto.

2. En el objeto Producto, tenga controladores definidos para manejar OnPartAdded y OnPartRemoved , y CurrentParts colección CurrentParts y llamen a la función de validación de cada parte.

Ejemplo de prototipo de huesos desnudos

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

Bonito y limpio.

Answer 5

Las instalaciones de fabricación de servidores de gama alta de HP en California usaron un sistema basado en reglas personalizadas durante muchos años para hacer precisamente esto.

El proceso del ciclo de construcción de la planta de producción de la fábrica incluyó verificaciones por adelantado para garantizar que el pedido se pudiera construir antes de entregarlo a los constructores y probadores.

Una de estas verificaciones determinó si la lista de materiales (BOM) de la orden se ajustaba a una lista de reglas especificadas por los ingenieros de proceso. Por ejemplo, si el cliente solicita procesadores, asegúrese de que también hayan pedido suficientes piezas de convertidor de CC; o, si han pedido una cierta cantidad de DIMM de memoria, asegúrese de que también hayan pedido una placa hija para acomodar la capacidad adicional.

Un estudiante de informática con antecedentes en compiladores habría reconocido el código. El código analizó la lista de materiales, generando internamente un árbol de subprocesos agrupados por tipo. A continuación, aplicó las reglas al árbol interno para determinar si la orden se ajustaba.

Como efecto secundario, el sistema también generó documentación de compilación para cada orden que los trabajadores detuvieron al construir cada sistema. También generó los resultados esperados de la prueba para el proceso de quemado posterior a la construcción, de modo que las bahías de prueba podrían hacer referencia a ellos y determinar si todo se construyó correctamente.

Answer 6

Lo único que puedo pensar en este momento en la construcción es si puedes construir un árbol que defina la dependencia entre las partes en las que tienes una solución simple.

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

esto simplemente dice que tiene 2 opciones para el Bollo (bollo o ningún bollo) - 1 para el sésamo (solo si tiene un bollo - lo que significa la dependencia - si tiene un 7 aquí significa 7 tipos que pueden existir si solo tener un bollo

3 para la mostaza .. etc

entonces simplemente multiplica la suma de todas las ramas.

Answer 7

Probablemente sea posible formalizar el problema como un problema k-sat . En algunos casos, el problema parece ser NP-completo y tendrá que enumerar todas las posibilidades para verificar si satisfacen o no todas las condiciones. En algunos otros casos, el problema será fácilmente solucionable (cuando se requieren pocas condiciones, por ejemplo). Este es un campo de investigación activo. Encontrarás referencias relevantes en google scholar.

En el caso de la mostaza, agregaría una entrada binaria "mustard_type" para el tipo de mostaza e introduciría la condición: not (not mustard and mustard_type) donde mustard es la entrada binaria para mustard. mustard_type == 0 opción predeterminada mustard_type == 0 cuando elija not mustard .

Para la elección de sésamo, esto es más explícito: not (sesame and not bun) .

Por lo tanto, parece que los casos que propones entran en la familia de problemas de 2 sat.

Answer 8

Adam Davis : Si entiendo correctamente, tiene la intención de desarrollar algún tipo de sistema que, de hecho, podría usarse para carritos de compras que ayuden a los usuarios a comprar piezas compatibles.

Definición del problema

Bueno, este es un problema gráfico ( no son todos ), tienes elementos que son compatibles con otros elementos. Por ejemplo, Pentium i3-2020 es compatible con cualquier Socket 1155 Motherboard , la Asrock H61M-VS es una Socket 1155 Motherboard , que es compatible con 2xDDR3 (velocidad = 1066), y requiere una PCI-Express GPU , DDR3 PC RAM{Total(size) <= 16GB} , 4 pin ATX 12V power , etc.

Debe poder (a) identificar si cada elemento de la cesta está satisfecho con otro elemento de la cesta (es decir, la tarjeta RAM tiene una placa base compatible), (b) asignar los elementos más apropiados (es decir, asignar el concentrador USB a la placa base USB el puerto y la impresora al concentrador USB si la placa base se queda sin puertos USB, en lugar de hacerlo al revés y deja el concentrador seco), y (c) proporciona al usuario una función para encontrar una lista de componentes satisfactorios. Quizás los concentradores USB siempre pueden tener prioridad, ya que son extensiones (pero tenlo en cuenta).

Estructuras de datos que necesitará

Necesitará un sistema de clasificación simple, es decir, H61M-VS es una placa base, H61M-VS tiene una ranura de memoria DDR3 (con propiedades de velocidad para cada ranura).

En segundo lugar a la clasificación y la composición, deberá identificar los requisitos, que es bastante simple. Ahora, la clasificación simple puede permitir que una consulta SQL simple encuentre todos los elementos que se ajustan a una clasificación.

Pruebas para una cesta satisfactoria

Para probar la cesta, se debe crear una configuración que identifique qué elementos se comparan con (la ranura DDR3 de la placa base coincide con el módulo RAM de 4 GB, el cable SATA HDD se conecta al puerto SATA de la placa base y el cable de alimentación SATA de la PSU, mientras que el ATX de 4 pines de la PSU El cable de alimentación de 12V se conecta a la placa base.

Lo más simple es comprobar si existe otro elemento satisfactorio.

Configurador de computadora de Dell

Usted comienza con un elemento, diga un procesador. El procesador requiere una placa base y un ventilador, por lo que puede darles la opción de una placa base (agregando el procesador-ventilador a la list_of_things_to_be_satisfied de list_of_things_to_be_satisfied para que list_of_things_to_be_satisfied ). Esto continúa hasta que no haya más elementos en list_of_things_to_be_satisfied . Por supuesto, todo depende de sus requisitos exactos y de saber qué problema (s) resolverá para el usuario.