Il problema della ricetta ottimale

Questo è il problema di Cover esatta , uno dei 21 problemi originali mostrati da Karp come NP-completo nel suo carta classica del 1972 che stabilì l'importanza della completezza della NP.

La descrizione di Wikipedia è:

given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*.

Il problema di base è, dato S e X, S contiene una copertura esatta di X?

Qui X è l'insieme dei contenuti del tuo frigorifero, e S è la raccolta di ricette. Il compito è trovare un sottoinsieme S * di ricette in modo tale che ogni ingrediente di X sia usato esattamente da una ricetta.

È noto che la copertina esatta rimane NP-completa anche quando ogni ricetta richiede non più di 3 ingredienti. Se ogni ricetta ha 2 o meno ingredienti, c'è un algoritmo tempo-polinomiale basato sulla ricerca di una corrispondenza massima in un grafico bipartito.

Il problema analogo, se esiste una copertura S * che copre almeno n elementi di X, è anche NP-completo. Allo stesso modo, si può riformulare questo come un problema di ottimizzazione: trovare il sottoinsieme S * che copre il numero massimo possibile di elementi. Una soluzione efficiente a questo problema di ottimizzazione risolverebbe il problema di decisione NP-completo, quindi è almeno altrettanto difficile del problema decisionale.

Come al solito con i problemi NP-completi, si può dire quanto segue:

1. Un buon algoritmo che funziona per tutte le istanze del problema è certamente fuori portata al momento e probabilmente non esiste.

2. La ricerca ad albero diramata può trovare rapidamente una buona soluzione per molte istanze del problema e per piccole istanze.

3. Gli approcci semplici (diciamo, selezionando sempre la ricetta con il maggior numero di ingredienti disponibili) possono produrre risultati che non sono mai troppo lontani dall'essere ottimali. Ci sono molte ricerche su questo genere di cose e non dovrebbe essere difficile scoprirne alcune.

Wikipedia menziona anche un algoritmo di Donald Knuth che esegue in modo efficiente una ricerca esaustiva di lo spazio della soluzione (che può essere molto grande) rappresentando le ricette come righe di una matrice.

sembra un problema di individuazione dei percorsi, inizi su un nodo X e vuoi spostare più passaggi con il minor costo.

il costo aumenta quando acquisti cose e rimane uguale quando non lo fai.

Suggerisco un flood-fill o minimax con l'abbattimento di alfa-beta finché non trovi un nodo in cui il tuo frigo è vuoto . (dopodiché dovrai acquistare comunque)

L'approccio che adotterei è un approccio meno-errori.

1) Crea un set di simboli per rappresentare ogni cibo.

2) Rappresenta il contenuto del tuo frigorifero come una stringa di simboli. La stringa è ordinata e più elementi sono rappresentati come simboli multipli. I liquidi, ecc., Dovrebbero essere rappresentati da più frazioni di tazza (cioè 6 x 1/4 di tazza di latte).

3) Rappresenta ogni ricetta allo stesso modo.

Ora, esegui una corrispondenza minima tra gli errori di ogni stringa di ricette con la stringa del frigo.

Ho avuto esperienza, una volta, con i primi riconoscimenti. Non so se questo aiuti.

Che dire dell'utilizzo di un approccio ermeneutico dare ad ogni destinatario determinati punti in base a criteri diversi. Eg unendo un ingrediente 5 punti per ogni ingrediente. Quello con il punteggio più basso vince