Minimizzare somma delle distanze: ottimizzazione Problema

Question

La domanda reale è questa:

McDonald sta progettando di aprire un numero di articolazioni (diciamo n) lungo una strada diritta. Queste articolazioni richiedono magazzini per conservare il cibo. Un magazzino può immagazzinare cibo per qualsiasi numero di giunti, ma deve essere posizionato solo in uno dei giunti. McD ha un numero limitato di magazzini (per esempio k) disponibili e desidera posizionarli in modo tale da ridurre al minimo la distanza media dei giunti dal magazzino più vicino.

Dato un array (n elementi) di coordinate dei giunti e un intero 'k', restituisce una matrice di elementi 'k' che fornisce le coordinate del posizionamento ottimale dei magazzini.

Spiacente, non ho esempi disponibili poiché sto scrivendo questo dalla memoria. Comunque, un campione può essere:

matrice = {} 1,3,4,5,7,7,8,10,11 (n = 9)
k = 1

Ans: {7 }

Questo è quello che stavo pensando: per k = 1, possiamo semplicemente scoprire la mediana del set, che darebbe la posizione ottimale del magazzino. Tuttavia, per k> 1, il set dato dovrebbe essere diviso in sottoinsiemi 'k' (disgiunto e di elementi contigui del superset), e la mediana per ogni sottoinsieme darebbe le posizioni del magazzino. Tuttavia, non capisco su quali basi dovrebbero essere formati i sottoinsiemi 'k'. Grazie in anticipo.

MODIFICA: C'è una variante a questo problema anche: invece di sum/avg, ridurre al minimo la distanza massima tra un giunto e il suo magazzino più vicino. Non capisco neanche questo ..

Answer 1

L'autostrada rettilinea rende questo un esercizio di programmazione dinamica, lavorando da sinistra a destra lungo l'autostrada. Una soluzione parziale può essere descritta dalla posizione del magazzino più a destra e dal numero di magazzini collocati. Il costo della soluzione parziale sarà la distanza totale dal magazzino più vicino (per k fisso minimizzare ciò equivale a minimizzare la media) o la distanza massima fino al magazzino più vicino.

In ogni fase sono state elaborate le risposte per i giunti N più a sinistra e sono indicizzati dal numero di magazzini utilizzati e dalla posizione del magazzino più a destra: è necessario salvare solo il costo migliore. Ora considera la prossima giuntura e trova la soluzione migliore per i giunti N + 1 e tutti i valori possibili di k e il magazzino più a destra, utilizzando le risposte che hai memorizzato per N articolazioni per velocizzarlo. Una volta elaborata la migliore soluzione di costo che copre tutti i giunti, sai dove si trova il magazzino più a destra, che ti dà la posizione di un magazzino. Torna alla soluzione che ha quel magazzino come giunto più a destra e scopri la soluzione su cui si basava. Questo ti dà un altro magazzino più a destra - e così puoi tornare alla posizione di tutti i magazzini per la soluzione migliore.

Tendo ad avere il costo di risolvere questo problema errato, ma con N giunti e k magazzini per posizionare hai N passi da compiere, ognuno basato sul considerare non più di Nk soluzioni precedenti, quindi ritengo che il costo sia kN^2.

Answer 2

Questo NON è un problema di cluster, è un caso particolare di un problema di localizzazione della struttura. È possibile risolverlo utilizzando un pacchetto di programmazione generale intero/lineare, ma poiché il problema è su una linea, potrebbero esserci algoritmi più efficienti (e meno costosi dal punto di vista del software) che funzionerebbero. Potresti considerare la programmazione dinamica poiché probabilmente ci sono combinazioni di strutture che potrebbero essere eliminate abbastanza rapidamente. Guarda nello P-Median problem per maggiori informazioni.