Algoritmo / struttura dati per rispondere "quali ricette posso creare con questo set di ingredienti?"

Question

Algoritmo / struttura dati per rispondere "quali ricette posso creare con questo set di ingredienti?"

#1 da (3 voti)

10

Formalmente, lascia s ( U , Q ) = { V | V ∈ U e V ⊆ Q } dove U , Q e V rappresentano tutti gli insiemi e U , più specificamente, rappresenta un insieme di insiemi. Ad esempio, U potrebbe essere un insieme di (set di) ingredienti necessari per varie ricette in un libro di cucina con Q che rappresenta l'insieme di ingredienti che ho V rappresenta una ricetta che potrei fare con quegli ingredienti. La query s ( U , Q ) corrisponde alla domanda "Che cosa posso fare con questi ingredienti?"

Quello che sto cercando è una rappresentazione di dati che indicizzi U in modo tale da supportare query efficienti di s ( U , Q ) dove Q e tutti i membri di U saranno generalmente piccoli rispetto all'unione di tutti i membri di U . Inoltre, mi piacerebbe che fosse in grado di aggiornare in modo efficiente U (ad esempio, aggiungere o rimuovere una ricetta).

Non posso fare a meno di pensare che questo problema debba essere ben compreso, ma non sono stato in grado di trovare un nome o un riferimento per questo. Qualcuno sa di una strategia per risolvere questo in modo efficiente o un luogo dove posso leggere di più su di esso?

Per quanto riguarda il pensare a una soluzione, ho pensato di creare un albero decisionale per il set U . In ogni nodo dell'albero, la domanda "la tua lista degli ingredienti contiene x ?" verrebbe chiesto con x scelto per massimizzare il numero di membri di U che vengono eliminati dalla risposta. Quando U viene aggiornato, questo albero delle decisioni dovrebbe essere riequilibrato per ridurre al minimo il numero di domande richieste per trovare il risultato corretto. Un altro pensiero è quello di rappresentare U con qualcosa come n -dimensionale booleano "octree" (dove n è il numero di ingredienti unici).

Credo che "Quali ricette possono essere fatte con questi ingredienti?" si può rispondere prendendo il prodotto cartesiano dei (set di ingredienti richiesti per le) ricette nel ricettario con il powerset degli ingredienti che si hanno e filtrando le coppie ordinate risultanti per le coppie in cui entrambi gli elementi sono uguali, ma questo non è un soluzione efficiente, e quello che sto chiedendo è come ottimizzare questo tipo di operazione; come si potrebbe comporre questo in SQL in modo tale che sarebbe efficiente e cosa fa SQL che consente di essere efficiente?

Anche se uso l'illustrazione di un ricettario di ricette e una serie di ingredienti, prevedo che il numero di "ricette" e il numero di "ingredienti" saranno molto grandi (fino a centinaia di migliaia ciascuno), anche se il il numero di ingredienti in una determinata ricetta e il numero di ingredienti in un determinato set di ingredienti sarà relativamente piccolo (probabilmente circa 10-50 per una tipica "ricetta" e circa 100 per un tipico "set di ingredienti"). Inoltre, l'operazione più comune sarà la query s ( U , Q ), quindi dovrebbe essere la più ottimale. Ciò significa anche che un algoritmo a forza bruta che richiede il controllo di ogni ricetta o il funzionamento su ogni ingrediente sarebbe comunque indesiderabilmente lento da solo. Con il caching intelligente, penso che questo potrebbe non funzionare troppo male, però.

data-structures algorithms

posta user16054 13.06.2015 - 16:35

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms

Mantenere una cronologia git pulita durante l'utilizzo di gitflow - commit non interrotti durante lo sviluppo Gestori di comandi e DDD

score 3 · Answer 1

Per i numeri che hai dato, solo forza bruta.

Ecco un programma JavaScript che brute lo forza per 10 ingredienti nel DB, 10 ricette nel DB, ogni ricetta ha bisogno di 2 ingredienti e ho 5 ingredienti disponibili:

var i, j;
var numIngredients = 10;
var numRecipes = 10;
var numIngredientsPerRecipe = 2;
var numIngredientsInQuery = 5;

function containsAll(needles, haystack){ 
  var i, len;
  for(i = 0 , len = needles.length; i < len; i++){
      if(haystack.indexOf(needles[i]) == -1) {
          return false;
      }
  }
  return true;
}

// Set up a fake DB of recipes
var ingredients = [];
for (i = 0; i < numIngredients; i++) {
    ingredients.push(i);
}
console.log('Here are the ingredients:', ingredients);

var recipes = [];
for (i = 0; i < numRecipes; i++) {
    var neededIngredients = [];
    for (j = 0; j < numIngredientsPerRecipe; j++) {
        neededIngredients.push(Math.floor(Math.random() * numRecipes));
    }
    recipes.push({ recipeId: i, needed: neededIngredients});
}
console.log('Here are the recipes:', recipes);

// Set up a fake query
var ingredientsAvailable = [];
for (i = 0; i < numIngredientsInQuery; i++) {
    ingredientsAvailable.push(Math.floor(Math.random() * numRecipes));
}

console.log("Here's a query:", ingredientsAvailable);

//Time how long brute force takes
var start = Date.now();
var result = [];
for (i = 0; i < numRecipes; i++) {
    var candidateRecipe = recipes[i];
    if (containsAll(candidateRecipe.needed, ingredientsAvailable)) {
        result.push(candidateRecipe);
    }
}
var end = Date.now();
console.log('Found ' + result.length + ' recipes in ' + (end - start) + ' milliseconds.');
console.log(result);

Funziona in 0 millisecondi. Ho scelto questi piccoli numeri in modo da poterlo eseguire da solo un paio di volte e convincerti che fa quello che vuoi ed è relativamente privo di bug.

Ora cambialo in modo da avere 1000000 ingredienti nel DB, 1000000 ricette nel DB, 50 ingredienti per ricetta e 100 ingredienti a mia disposizione. Cioè valori che sono tutti uguali o maggiori del caso d'uso più grande che hai dato.

Funziona in 125 millisecondi sotto nodejs, e questo è con l'implementazione più stupida senza alcuno sforzo da ottimizzare.