Qual è l'algoritmo più elegante per trovare la combinazione migliore?

Question

Qual è l'algoritmo più elegante per trovare la combinazione migliore?

#1 da (1 voti)
#2 da (-2 voti)

0

Ho una funzione, chiamiamola test . Questa funzione ha argomenti, ma non so quanti argomenti abbia. Restituisce sempre un booleano.

Ho un'altra funzione, chiamiamola calibrator . Questa funzione calibrator ottiene il possibile alternatives degli argomenti test in un array 2d. Ogni argomento può avere molte alternative. Devo chiamare la funzione test sull'argomento combination s finché non trovo qualcosa che restituisce true . La funzione calibrator dovrebbe restituire combination o default se non trova un combination corretto.

Qual è il miglior algoritmo per calibrator ?

Ho inventato qualcosa di simile finora, ma sono bloccato:

function calibrator(test, alternatives, default){
    var combination = [];

    // certainly not the way I need to use for iteration
    // this does not find every combination
    for (var argument in alternatives)
        for (var alternative in alternatives[argument])
            combination[argument] = alternatives[argument][alternative];

            // returns the combination when the test succeeds, so exists from the loop
            // this should run by every possible combination
            if (test(combination))
                return combination; 

    // returns default if no proper combination 
    return default;
}

Ho bisogno di scorrere tutte le combinazioni, ma non so come farlo. : S

modifica

Ho finito con il seguente codice basato sulla risposta accettata.

var eachCombination = function (alternativesByDimension, callback, combination){
    if (!combination)
        combination = [];
    if (combination.length < alternativesByDimension.length) {
        var alternatives = alternativesByDimension[combination.length];
        for (var index in alternatives) {
            combination[combination.length] = alternatives[index];
            eachCombination(alternativesByDimension, callback, combination);
            --combination.length;
        }
    }
    else 
        callback(combination);
};

function calibrator(alternativesByDimension, test) {
    try {
        eachCombination(alternativesByDimension, function (combination){
            if (test.apply(null, combination))
                throw combination;
        });
    } catch (combination){
        return combination;
    }
    return alternativesByDimension.map(function (alternatives){
        return alternatives[0];
    });
}

console.log(calibrator([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
], function(x, y, z) {
    return x > 2 && y > 5; 
}));

Nel frattempo mi sono reso conto che il problema è in qualche modo simile all'iterazione delle foglie degli alberi e così pure la soluzione. Riconosco che è più elegante con i generatori, ma avevo bisogno di qualcosa che funzioni anche con MSIE. : -)

algorithms

posta inf3rno 21.08.2016 - 17:00

fonte

2 risposte

-2

Senza conoscere meglio e senza alcun indizio su quale combinazione ha più probabilità di successo, sembra che tu abbia "solo" bisogno di implementare l'intero set di permutazione di tutte le alternative, testare ognuna e tornare al successo

for (i = 0; i < numAlternatives[0]; i++)
   for (j = 0; j < numAlternatives [1]; j++)
      for (k = 0; k < numAlternatives [2]; k++)
         if (test (alternative [0, i], 
                   alternative [1, j], 
                   alternative [2, k]) == TRUE)
            return new solutionSet (alternative [0, i], 
                   alternative [1, j], 
                   alternative [2, k]);

E "l'eleganza" può entrare in gioco non appena si ha un'idea del tipo di alternative che hanno maggiori probabilità di successo rispetto ad altre. Dovresti ordinare le alternative in termini di probabilità decrescente per colpire prima le combinazioni più probabili.

risposta data 21.08.2016 - 17:59

fonte

Leggi altre domande sui tag algorithms

Versione richiesta di AngularJS e NodeJS Come aggiungere algoritmicamente note a un file midi esistente rispetto alle posizioni delle note esistenti in python

score 1 · Accepted Answer

Puoi aggiungere un'altra funzione getCombinations che genera tutte le combinazioni di elementi in alternative. index è l'indice di cui abbiamo creato tutte le combinazioni fino a, e combination l'array che contiene la combinazione corrente.

function* getCombinations(index, combination, alternatives) {
    if (index == alternatives.length) {
        yield combination;
    } else {
        for (var alternative of alternatives[index]) {
            combination[index] = alternative;
            yield* getCombinations(index + 1, combination, alternatives);
        }
    }
}

function calibrator(test, alternatives, defaultValue) {
    for (var combination of getCombinations(0, [], alternatives)) {
        if (test(combination)) {
            return combination;
        }
    }

    return defaultValue;
}

test = function([x, y, z]) { return x > 2 && y > 5; };
alternatives = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
defaultValue = [0, 0, 0];

console.log(calibrator(test, alternatives, defaultValue));