Come ottimizzare il prodotto cartesiano

7

Esiste un modo migliore per calcolare il prodotto cartesiano. Dal momento che il prodotto cartesiano è un caso speciale che differisce su ogni caso. Penso, devo spiegare cosa devo raggiungere e perché finisco per fare un prodotto cartesiano. Per favore aiutami se il prodotto cartesiano è l'unica soluzione per il mio problema. In tal caso, come migliorare le prestazioni.

Sfondo:

Stiamo cercando di aiutare i clienti ad acquistare prodotti più economici.

Lascia che il cliente abbia ordinato 5 prodotti (prod1, prod2, prod3, prod4, prod5).

Ogni prodotto ordinato è stato offerto da diversi fornitori.

Rappresentazione Formato1:

Fornitore1 - offre prod1, prod2, prod4

vendor2 - offre prod1, prod5

vendor3 - offre prod1, prod2, prod5

vendor4 - offre prod1

vendor5 - offre prod2 vendor6 - offerte prod3, prod4

In altre parole

Rappresentazione Formato2:

Prod1 - offerto da vendor1, vendor2, vendor3, vendor4

Prod2 - offerto da vendor5, vendor3, vendor1

prod3 - offerto dal fornitore6

prod4 - offerto da vendor1, vendor6

prod5 - offerto da vendor3, vendor2

Ora scegliere il miglior fornitore in base al prezzo. Possiamo ordinare i prodotti in base al prezzo e prendere il primo.

In questo caso scegliamo

prod1 dal fornitore1

prod2 dal fornitore5

prod3 dal fornitore

prod4 dal fornitore1

prod5 from vendor3

Complessità:

dal momento che abbiamo scelto 4 fornitori unici, dobbiamo pagare 4 costi di spedizione.

Anche ogni venditore ha un ordine di acquisto minimo. Se non ci incontriamo, finiamo anche per pagare quell'accusa.

Per scegliere la migliore combinazione di prodotti. Dobbiamo fare un prodotto cartesiano di prodotti offerti per calcolare il prezzo totale.

total price computation algorithm:

foreach unique vendor 
if(sum(product price offered by specific vendor * quantity)<minimum purchase order limit specified by specific vendor)
totalprice +=sum(product price * quantity) + minimum purchase charge + shipping price
else
totalprice +=sum(product price * quantity) + shipping price
end foreach

Nel nostro caso

{vendor1, vendor2, vendor3, vendor4}

{vendor1, vendor3, vendor5}

{vendor6}

{vendor1, vendor6}

{vendor2, vendor3}

4 * 3 * 1 * 2 * 2 = 48 la combinazione deve essere calcolata per trovare la combinazione migliore.

{vendor1, vendor1, vendor6, vendor1, vendor2} = totalprice1,

{vendor1, vendor3, vendor6, vendor1, vendor2} = totalprice2,

.

.

{vendor4, vendor5, vendor6, vendor6, vendor3} = totalprice48

Ora ordina il prezzo totale calcolato per trovare la combinazione migliore.

Problema effettivo:

Se l'ordine del cliente è più di 15 prodotti. Supponiamo che ogni prodotto sia stato offerto da 8 fornitori unici, quindi finiamo per calcolare la combinazione 8 ^ 15 = 35184372088832. Il che richiede più di un paio d'ore. Se l'ordine del cliente è più di 20 prodotti, ci vogliono più di un paio di giorni.

Esiste una soluzione per affrontare questo problema con un'angolazione diversa?

    
posta Esen 25.04.2012 - 17:57
fonte

1 risposta

2

Il tuo problema è nella stessa categoria del famoso "problema del commesso viaggiatore". Trovare la soluzione migliore sarà molto costoso con un numero crescente di fornitori e prodotti. Puoi provare ad implementare un algoritmo di backtracking che tenta di ridurre lo spazio della soluzione il prima possibile.

Alcune idee sono:

  1. Inizia con il "costo maggiore" = max (quantità * min (prezzo))
  2. Cerca di ridurre al minimo il numero di venditori (= > prova a ottenere più prodotti da un fornitore già presente nell'elenco)
  3. aggiungi una soluzione se tutti gli articoli sono ordinati
  4. interrompi e rintraccia se la somma totale corrente è maggiore del tuo miglior risultato
  5. ...
risposta data 25.04.2012 - 18:24
fonte

Leggi altre domande sui tag