Riduzione dell'albero decisionale (?)

0

Devo verificare alcune condizioni (della dimensione n) su un oggetto ed eseguire una delle varie opzioni disponibili (dimensione m) in base al risultato. Mi sembra che si adatti a un albero.

Ora. L'albero è abbastanza grande e mi chiedo se c'è un modo per ridurlo.

Ecco un esempio di questo

Le condizioni sono contrassegnate come c1, ..., cn e le funzioni da eseguire sono contrassegnate come f1, ..., fm (gli zeri incrociati sono valori dont-care)

    
posta Yoni Levy 07.05.2015 - 09:05
fonte

1 risposta

4

In effetti, un albero è una buona struttura dati per questo. Puoi quindi creare un BST che permetterà di trovare cercando un'azione specifica basata su c 1 a c n condizioni.

Ovviamente, questo ha un enorme vantaggio nell'evitare codice brutto come:

if (c1) {
    if (c2) {
        if (c3) {
            ...
        }
        ...
    }
    ...
}

Se il BST può essere semplificato ancora di più dipende dall'associazione esatta tra le condizioni e le azioni. Cerca uno schema. Immagina cosa succederebbe se mettessi c 1 dopo c 2 .

Come faccio a cercare l'azione?

Se esprimi le tue condizioni come una matrice di elementi n [ c 1 , c 1 , ⋯ c n ], è quindi possibile cercare l'azione in modo ricorsivo o iterativo. Ad esempio, un approccio ricorsivo sarebbe simile a questo:

var findAction = function (conditions, node) {
    // 'shift' also removes the element from the array.
    var currentCondition = conditions.shift();

    if (typeof node !== 'boolean') {
        return node;
    }

    return findAction(conditions, node[currentCondition]);
}

che può essere chiamato in questo modo:

var conditions = [false, false, true, false];
var tree = {
    true: {
        true: f1,
        false: {
            true: f2,
            false: f1
        }
    },
    false: {
        true: {
            true: f5,
            false: f3
        },
        false: {
            true: {
                true: f2,
                false: f6
            },
            false: f4
        }
    }
};


findAction(conditions, tree)(); // Will execute 'f6'.

La mappa di Karnaugh sembra molto più semplice ...

Lo è, ma ha anche una limitazione: tutte le tue foglie dovrebbero essere alla stessa profondità. Questo è effettivamente il caso nella tabella che hai mostrato, ma potrebbe non essere necessariamente il caso del vero problema che stai tentando di risolvere.

Se, ad esempio, alcuni nodi sono profondi in due livelli mentre altri sono profondi otto livelli, con la mappa di Karnaugh, devi allinearli in modo che siano otto livelli profondi, il che probabilmente porterà a duplicazione grave (ma non necessariamente in ridotta manutenibilità, potrebbe effettivamente essere che la manutenibilità aumenterà solo). Con un BST, non devi farlo.

Un esempio semplicistico del seguente BST:

var tree = {
    true: {
        true: f1,
        false: {
            true: {
                true: f2,
                false: f3
            },
            false: f4
        }
    },
    false: f5
};

sarà espresso come questa mappa di Karnaugh:

var tree = {
    true: {
        true: {
            true: {
                true: f1,
                false: f1
            },
            false: {
                true: f1,
                false: f1
            }
        },
        false: {
            true: {
                true: f2,
                false: f3
            },
            false: {
                true: f4,
                false: f4
            }
        }
    },
    false: {
        true: {
            true: {
                true: f5,
                false: f5
            },
            false: {
                true: f5,
                false: f5
            }
        },
        false: {
            true: {
                true: f5,
                false: f5
            },
            false: {
                true: f5,
                false: f5
            }
        }
    }
};
    
risposta data 07.05.2015 - 09:19
fonte

Leggi altre domande sui tag