Algoritmo per disporre gli oggetti in modo che la lunghezza totale dei bordi tra di essi sia ridotta al minimo?

Question

Algoritmo per disporre gli oggetti in modo che la lunghezza totale dei bordi tra di essi sia ridotta al minimo?

#1 da (2 voti)

3

Ci viene data una lista di spigoli tra un insieme di N vertici. Ci sono almeno tre lati che si uniscono a un vertice. Dobbiamo sistemare tutti i vertici su una linea retta con le posizioni numerate da 1 a N in modo che la somma della lunghezza di tutti i bordi sia ridotta al minimo.
La lunghezza di un bordo a, b è la differenza tra le posizioni dei vertici 'a' e 'b' sulla linea. Ci sono almeno 12 vertici. L'algoritmo dovrebbe funzionare entro il limite di tempo di 1 secondo.

Questo è il vero problema.

Ho provato a risolvere questo problema provando tutte le permutazioni e scoprendo il costo totale di ogni spigolo. Ma questo funziona solo per 8 dei 12 test al problema. Perché nel peggiore dei casi il numero totale di operazioni è proporzionale a 12! * 18.

La dimensione di N è molto piccola quindi penso che la soluzione potrebbe essere simile a provare tutte le possibilità.
Non ho bisogno della soluzione completa a questo problema perché voglio provare a farlo da solo ma solo un suggerimento su come posso ottimizzare il mio algoritmo in modo che funzioni entro il limite di tempo. Grazie.

algorithms optimization

posta 2147483647 30.08.2013 - 08:58

fonte

1 risposta

Leggi altre domande sui tag algorithms optimization

Evitare il boilerplate nelle classi PHP Il modo migliore per rinominare i nomi di campi univoci esistenti nel database?

score 2 · Accepted Answer

Vorrei provare ad attaccare questo problema simile al puzzle di otto-queens

genera permutazioni incrementalmente
per ogni piazzamento degli elementi 1,..,k, k<N, puoi facilmente calcolare un limite inferiore per il punteggio finale senza generare tutti i piazzamenti finali di k+1,...,n . Ad esempio, potresti ignorare il fatto che k+1,...,n deve essere posizionato su punti diversi e calcolare i loro punteggi presumendo che ciascuno dei vertici possa essere posizionato nel "punto ottimale"
le permutazioni completate ti danno un limite superiore per il punteggio finale; questo limite superiore diminuirà più permutazioni generate
ogni volta che il limite inferiore per una posizione parziale supera il limite superiore, puoi tagliare l'albero di ricerca qui e interrompere ulteriori posizionamenti di k+1,...,n

Questa tecnica è anche chiamata branch-and-bound .

EDIT: ci sono ovviamente ulteriori ottimizzazioni possibili. Ad esempio: quando cerchi un posto per vertice k , non provare gli slot vuoti da sinistra a destra, ma preordinare gli slot vuoti, in modo da provare prima i posti con il punteggio più basso. Questo probabilmente porterà rapidamente il limite superiore, il che migliora la possibilità di tagliare l'albero di ricerca.

EDIT2: la generazione della permutazione definisce un albero di ricerca. Un nodo è costituito da k elementi già posizionati in uno slot, ei fratelli di questo nodo sono i nodi (n-k) in cui un altro elemento è posto in uno slot libero. Puoi assegnare ad ogni nodo un punteggio con limite inferiore, come ho scritto sopra. Ma invece di fare una ricerca approfondita attraverso questo albero, si mettono i nodi in una coda di priorità. Algo quindi prende il nodo con il punteggio minimo per primo fuori dalla coda-prio, genera i fratelli, calcola il punteggio limite inferiore per ciascun fratello e inserisce di nuovo quei nodi nella coda-prio. Quando raggiungi un nodo in cui tutti i vertici sono posizionati in uno slot, hai trovato la soluzione ottimale. Questo è chiamato A * search . È facile da implementare quando hai a disposizione una coda di priorità già pronta.