Algoritmi combinatori complessi

https://stackoverflow.com/questions/1644389

10-07-2019
|

Domanda

Quindi Wendy's pubblicizza il suo sandwich con 256 combinazioni, il che significa che ci sono 8 ingredienti che non si possono avere (anche se mi chiedo perché dovrebbero considerare la combinazione in cui non si include nulla come valido, ma sto divagando).

Un approccio generalizzato consente di moltiplicare insieme i vari stati di ciascuna selezione, il che consente combinazioni più complesse. In questo caso gli articoli di Wendy possono essere inclusi o esclusi. Ma alcuni sandwich potrebbero avere l'opzione di due tipi di senape (ma non entrambi, per risparmiare sui costi).

Questi sono abbastanza semplici. Moltiplichi il numero di opzioni insieme, quindi per Wendy's è:

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

Se diversificassero la loro selezione di senape come sopra sarebbe:

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

Andare oltre sembra essere più difficile.

Se trasformi i semi di sesamo in un oggetto separato, allora richiedono l'elemento panino. Puoi avere i semi di sesamo solo se includi il panino e puoi avere il panino senza semi di sesamo, ma non puoi avere semi di sesamo senza il panino. Questo può essere semplificato per un singolo oggetto panino con tre stati (nessuno, panino con semi, panino senza) ma ci sono situazioni in cui ciò non può essere fatto.

Il configuratore di computer Dell, ad esempio, non consente determinate combinazioni (forse gli slot sono tutti pieni, gli elementi sono incompatibili quando vengono inseriti nello stesso sistema, ecc.)

Quali sono gli approcci combinatori appropriati quando si tratta di sistemi significativamente più complessi in cui gli oggetti possono entrare in conflitto?
Quali sono gli approcci validi, generalizzati, per la memorizzazione di tali informazioni senza dover codificare per ogni prodotto / combinazione / articolo per rilevare conflitti?
C'è un modo semplice per dire " ci sono X modi per configurare il tuo sistema / sandwich " quando il sistema deve gestire complesse combinazioni contrastanti?

Soluzione

Esistono molti modi per implementarlo nel codice, ma ecco a mio modesto parere il modo migliore per risolvere il problema prima di programmare qualsiasi cosa:

Definisci parti & amp; Prodotti (pre-codice)

Quando si definiscono tutte le " parti " sarà fondamentale identificare la gerarchia e la categorizzazione per le parti. Questo è vero perché alcune regole possono essere esclusive di una parte unica (es. & Quot; solo senape marrone & Quot;) , alcune categoriche (es. & Quot ; tutte le senape ") , alcune per tipo (es. " tutti i condimenti ") , ecc.

Crea set di regole (pre-codice)

Definire le serie di regole (prerequisiti, esclusioni, ecc.) per ogni parte, categoria, tipo e prodotto finito unici.

Può sembrare sciocco, ma è necessario prestare molta attenzione per garantire che le regole siano definite con un ambito appropriato. Ad esempio, se il prodotto finito è un Burger:

Regola oggetto unico - " I funghi sono disponibili solo con Blue Cheese selezionato " prerequisite
Regola categorica - " È possibile selezionare solo 1 senape " exclusive
Type Rule - " Sottaceti non sono compatibili con Peppers " condition

Dopo aver trascorso così tanto tempo in regole uniche / categoria / tipo per " parti " molti progettisti ignoreranno le regole che si applicano solo al prodotto finito anche quando le parti non hanno conflitti.

Regola del prodotto - " Massimo 5 condimenti " Category
Regola del prodotto - " Burger deve avere un panino " HasCondiments

Questo grafico della regola può rapidamente diventare molto complesso.

Suggerimenti per la costruzione di strutture dati (codice)

Assicurati che le tue strutture si adattino alla gerarchia e alla categorizzazione. Ad esempio: & Quot; senape marrone & Quot; e " senape di Digione " sono singoli oggetti e sono entrambe senape ed entrambi condimenti.

Seleziona con cura la giusta combinazione di modellazione ereditaria (classi base) e attributi oggetto (es. RuleSets proprietà o HasConflicts flag) per farlo funzionare.
Crea un campo privato per RuleViolations a ciascun livello di oggetto gerarchico.
Rendi proprietà pubbliche per una CurrentParts bandiera e una OnPartAdded collezione.
Quando una parte viene aggiunta a un prodotto, controlla tutti i livelli di regole (proprio, categoria, tipo e prodotto); esegui questa operazione tramite una funzione pubblica che può essere chiamato dal prodotto. O per una migliore interiorizzazione, puoi creare un gestore di eventi sulla parte stessa.

Scrivi i tuoi algoritmi (codice)

Questo è il posto in cui faccio schifo, e il bello è che va oltre lo scopo della tua domanda.

Il trucco di questo passaggio sarà come implementare nel codice le regole che percorrono l'albero / il grafico, ad esempio quando una parte specifica ha problemi con un'altra parte al di fuori del suo ambito o come viene eseguita la sua convalida quando è stata aggiunta un'altra parte? Il mio pensiero:

Utilizza una metodologia funzione pubblica per ogni parte. Passalo alla OnPartRemoved collezione del prodotto.
Nell'oggetto Prodotto, è necessario definire i gestori per gestire <=> e <=> e elencare la raccolta <=> e chiamare la funzione di convalida di ciascuna parte.

Esempio di prototipo di ossa nude

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

Bello e pulito.

Altri suggerimenti

La struttura di produzione di server di fascia alta di HP in California ha utilizzato per molti anni un sistema personalizzato basato su regole.

Il processo del ciclo di costruzione del piano di fabbrica includeva controlli anticipati per garantire che l'ordine fosse edificabile prima di consegnarlo ai costruttori e ai tester.

Uno di questi controlli ha determinato se la distinta base dell'ordine (BOM) era conforme a un elenco di regole specificate dagli ingegneri di processo. Ad esempio, se il cliente ordina processori, assicurarsi di aver ordinato anche sufficienti parti del convertitore cc; oppure, se hanno ordinato una determinata quantità di moduli DIMM di memoria, assicurati di aver ordinato anche una scheda figlia per ospitare la capacità aggiuntiva.

Uno studente di informatica con un background in compilatori avrebbe riconosciuto il codice. Il codice ha analizzato la DBA, generando internamente un albero filettato di parti raggruppate per tipo. Ha quindi applicato le regole all'albero interno per determinare se l'ordine era conforme.

Come effetto collaterale, il sistema ha anche generato la documentazione di costruzione per ogni ordine che i lavoratori hanno tirato su mentre costruivano ciascun sistema. Ha inoltre generato i risultati dei test previsti per il processo di burn-in post-build in modo che gli alloggiamenti dei test possano fare riferimento a loro e determinare se tutto è stato creato correttamente.

Adam Davis : se ho capito bene, intendi sviluppare una sorta di sistema che potrebbe effettivamente essere utilizzato per i carrelli della spesa che aiutano gli utenti ad acquistare parti compatibili.

Definizione del problema

Bene, questo è un problema grafico ( non sono tutti ), hai elementi compatibili con altri oggetti. Ad esempio, Pentium i3-2020 è compatibile con qualsiasi Socket 1155 Motherboard, Asrock H61M-VS è un PCI-Express GPU, che è compatibile con 2xDDR3 (velocità = 1066) e richiede un DDR3 PC RAM{Total(size) <= 16GB}, < =>, 4 pin ATX 12V power, ecc.

Devi essere in grado di (a) identificare se ogni articolo nel carrello è soddisfatto da un altro oggetto nel carrello (ad es. la scheda RAM ha una scheda madre compatibile), (b) assegnare gli oggetti più appropriati (cioè assegnare l'hub USB alla porta USB della scheda madre e alla stampante dall'hub USB se la scheda madre esaurisce le porte USB, invece di fare il contrario e lasciare l'hub asciutto) e (c) fornire all'utente una funzione per trovare un elenco di componenti soddisfacenti. Forse gli hub USB possono sempre avere la precedenza in quanto sono estensioni (ma attenzione).

Strutture di dati necessarie

Avrai bisogno di un semplice sistema di classificazione, ad esempio H61M-VS is-a scheda madre, H61M-VS has-a DDR3 slot di memoria (con proprietà di velocità per ogni slot).

Secondo la classificazione e la composizione, dovrai identificare i requisiti, il che è abbastanza semplice. Ora la semplice classificazione può consentire a una semplice query SQL di trovare tutti gli elementi che rientrano in una classificazione.

Test per un paniere soddisfacente

Per testare il cestino, è necessario creare una configurazione, identificando quali elementi sono stati abbinati con quale (cioè lo slot DDR3 della scheda madre corrisponde al modulo Ram da 4 GB, il cavo HDD SATA si collega alla porta SATA della scheda madre e al cavo di alimentazione SATA dell'alimentatore, mentre l'alimentatore Il cavo di alimentazione ATX 12V a 4 pin si collega alla scheda madre.

La cosa più semplice è solo verificare se esiste un altro oggetto soddisfacente

Dell Computer Configurator

Inizi con un elemento, ad esempio un processore. Il processore richiede una scheda madre e una ventola, quindi puoi dare loro una scelta di scheda madre (aggiungendo la ventola del processore a list_of_things_to_be_satisfied). Questo continua fino a quando non ci sono più elementi in <=>. Ovviamente tutto dipende dai tuoi requisiti esatti e dalla conoscenza di quali problemi risolverai per l'utente.

Come programmatore farei quanto segue (anche se in realtà non ho mai dovuto farlo nella vita reale):

Calcola il numero totale di combinazioni, di solito una scala moltiplicazione delle opzioni come indicato nella tua domanda sarà sufficiente. Non è necessario conservare tutti questi combinazioni.
Quindi dividi il totale per eccezioni. Le eccezioni possono essere memorizzato come solo un insieme di regole, dicendo effettivamente quali combinazioni non sono ammessi.
Per calcolare un numero totale di combinazioni consentite, avrai per scorrere l'intero set di regole di eccezione.

Se pensi a tutte le tue combinazioni come a un set, le eccezioni rimuovono semplicemente i membri di quel set. Ma non è necessario memorizzare l'intero set, solo le eccezioni, poiché puoi calcolare abbastanza facilmente la dimensione del set.

" Funzioni di generazione " viene in mente come un costrutto che può essere utilizzato per risolvere questo tipo di problema. Noterei che ci sono diverse funzioni di generazione a seconda di ciò che vuoi.

In Nord America, le targhe automobilistiche possono essere un problema combinatorio interessante nel contare tutte le permutazioni in cui ci sono 36 possibili valori per ogni posto di 6 o 7 che sono le lunghezze delle targhe a seconda di dove si ottiene una targa . Tuttavia, alcune combinazioni sono squalificate a causa della presenza di parolacce o parole razziste in alcune di esse che creano un problema leggermente più difficile. Ad esempio, esiste una N-word infamour che ha almeno un paio di ortografie diverse che non sarebbero consentite su targhe che credo.

Un altro esempio sarebbe determinare tutti i diversi ordini di parole usando un dato alfabeto che contiene alcuni elementi ripetuti più volte. Ad esempio, se si volessero tutti i diversi modi di disporre le lettere di dire la parola & Quot; letter & Quot; non sono solo le 6! quale sarebbe il caso di " abcdef " perché ci sono 2 coppie di lettere che rendono leggermente più complicato il calcolo.

L33t può essere un altro modo per rendere più complessa l'identificazione di parole inappropriate come as ass viene censurato un $$ o @ss potrebbe non essere necessariamente trattato allo stesso modo anche se sostanzialmente è lo stesso termine espresso in modi diversi. Non sono sicuro che molti caratteri speciali come $ o @ appaiano sulle targhe, ma si potrebbe pensare ai controlli parentali sui contenuti web come a dover avere questo tipo di algoritmi per identificare quali termini censurare.

Probabilmente vorresti creare una struttura di dati che rappresenti una singola configurazione in modo univoco. Quindi ogni regola di compatibilità dovrebbe essere definita in modo tale da generare un set contenente tutte le singole configurazioni che non soddisfano tale regola. Quindi dovresti prendere l'unione di tutti i set generati da tutte le regole per ottenere il set di tutte le configurazioni che non superano le regole. Quindi contate la dimensione di quel set e sottratela dalla dimensione del set tutte le possibili configurazioni.

La parte difficile sta definendo la struttura dei dati in un modo che può essere generato dalle tue regole e può far funzionare le operazioni impostate su di essa! Questo è un esercizio per il lettore, AKA Non ho niente.

L'unica cosa a cui riesco a pensare in questo momento è costruire se riesci a costruire un albero che definisce la dipendenza tra le parti che hai una soluzione semplice.

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

questo dice semplicemente che hai 2 opzioni per il Bun (bun o no bun) - 1 per il sesamo (solo se hai un bun - indicando la dipendenza - se hai un 7 qui significa che 7 tipi che possono esistere se hai solo un panino)

3 per la senape ... ecc

quindi moltiplica semplicemente la somma di tutti i rami.

Probabilmente è possibile formalizzare il problema come problema k-sat . In alcuni casi, il problema sembra essere NP-completo e dovrai elencare tutte le possibilità per verificare se soddisfano o meno tutte le condizioni. In alcuni altri casi, il problema sarà facilmente risolvibile (quando ad esempio sono necessarie poche condizioni). Questo è un campo di ricerca attivo. Troverai riferimenti pertinenti su google scholar.

Nel caso della senape, si dovrebbe aggiungere una voce binaria " mustard_type " per il tipo di senape e introdurre la condizione: not (not mustard and mustard_type) dove mustard è la voce binaria per senape. Imporrà la scelta predefinita mustard_type == 0 quando scegli not mustard.

Per la scelta del sesamo, questo è più esplicito: not (sesame and not bun).

Sembra quindi che i casi proposti rientrino nella famiglia di problemi 2-sat.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow