Algoritmo per soddisfare determinati vincoli - Assegnazione di valori da un array 2D

4

Quindi io e il mio amico abbiamo trovato una domanda di algoritmo piuttosto interessante (forse?) ma, ironia della sorte, stiamo facendo fatica a risolverlo. La domanda è:

C'è una vendita di pietre preziose in corso in una città dei ricchi. Ogni pietra in vendita ha una o più varianti di esso. Ad esempio, un diamante può essere rotondo, ovale, cuscino, ecc. Ogni variante deve essere contata come una pietra separata.

Le pietre sono posizionate in questo modo (esempio):

Diamond    Ruby     Emerald    Sapphire

round               red        colorless
oval                green      
cushion

Questo tipo di posizionamento impedisce la formazione di un array 2D perfetto, poiché il numero di tipi di ciascuna pietra può variare.

Ora i clienti ricchi vengono a comprare le pietre e ogni cliente ha un set di pietre che gli piace. Un cliente sarà soddisfatto se sarà in grado di acquistare almeno una delle pietre che preferisce.

Dato il numero di clienti, il numero di pietre e le varianti associate, scopri se è possibile soddisfare tutti i clienti .

Bonus: se possibile, trova le pietre acquistate da ciascun cliente.

Nota: le preferenze dei clienti non possono essere vuote, ad esempio, a ogni cliente piace almeno una pietra.

Cosa ho provato

(per scoprire se è possibile soddisfare tutti i clienti)

Backtracking:

Abbiamo un elenco di preferenze per ogni cliente. Quindi, basta assegnare la prima pietra possibile al cliente (dalla sua lista) e passare al prossimo cliente. Continua a farlo per tutti i clienti.

Se, per un cliente, non è possibile assegnare una pietra, andare al cliente precedente e cambiare la pietra assegnata.

Ripeti fino a quando almeno una pietra viene assegnata per ogni cliente.

Se torni al primo cliente e se non assegni alcuna pietra può portare alla soluzione, stampa "Impossibile".

Ho delle seguenti preoccupazioni su questo algoritmo (supponendo che sia corretto):

  • È difficile da implementare. Ho incontrato troppe variabili temporanee mentre provavo a implementarlo. (L'ho lasciato a metà).
  • Sembra una specie di forza bruta, perché in realtà sto provando ogni possibile combinazione.

Questo algoritmo è corretto? Può essere migliorato? Esiste un'alternativa facile da implementare?

    
posta Akshay Arora 30.06.2016 - 09:47
fonte

2 risposte

3

Direi che è un array 1D, dato che una pietra e la sua variante formano un singolo oggetto. È un'ipotesi errata?

Il tuo algoritmo dovrebbe essere corretto, tuttavia è veramente una soluzione a forza bruta.

Il mio semplice suggerimento: ordina questi elementi in base alla quantità di persone che li hanno nei loro "preferiti". Assegna gli oggetti alle persone in questo ordine, espandendo un albero limitato dalla quantità di elementi.

es. A 2 persone piace la pietra A, 3 persone come la pietra B, prima assegna la pietra A, in modo da sbarazzarti della meno prospettiva il prima possibile.

Probabilmente non è una soluzione ottimale, tuttavia potrebbe essere utilizzata una programmazione dinamica, dato che lo spazio degli stati è discreto.

    
risposta data 30.06.2016 - 10:22
fonte
1

Il backtracking è un buon approccio. Se la tua implementazione diventa complicata, dovresti leggere alcune implementazioni di esempio del backtracking.

Nota: il backtracking non sta "provando ogni combinazione possibile" perché non provi alcuna combinazione, dove già dopo alcuni compiti non poteva più essere un compito valido su tutto.
Vedi Varianti anticipate per una descrizione dettagliata. (L'animazione di soluzione Sodoku mostra abbastanza bene che sei lontano dal provare ciascuna combinazione)

    
risposta data 30.06.2016 - 10:00
fonte

Leggi altre domande sui tag