Ordinare gli array in ordine crescente riducendo al minimo il "costo"

Question

Sto prendendo il comp 2210 (Data Structures) il prossimo semestre e ho svolto i compiti per il semestre estivo che è stato pubblicato online. Fino ad ora, non ho avuto problemi a svolgere i compiti. Dai un'occhiata al compito 4 di seguito, e vedi se puoi darmi un suggerimento su come affrontarlo. Si prega di non fornire un algoritmo completo, solo un approccio. Grazie!

Un "ordinamento costato" è un algoritmo in cui una sequenza di valori deve essere organizzata in ordine crescente. L'ordinamento è eseguito scambiando la posizione di due valori uno alla volta finché la sequenza non è nell'ordine corretto. Ogni interscambio comporta un costo, che è calcolato come la somma dei due valori coinvolti nello scambio. Il costo totale del tipo è la somma del costo degli interscambi.

Ad esempio, si supponga che la sequenza iniziale sia {3, 2, 1}. Una possibile serie di svincoli è

Interchange 1: {3, 1, 2} interchange cost = 0 
Interchange 2: {1, 3, 2} interchange cost = 4 
Interchange 3: {1, 2, 3} interchange cost = 5, 
given a total cost of 9 

Sei scrivere un programma che determina il costo minimo di organizzare una specifica sequenza di numeri.

Modifica: il professore non consente la forzatura bruta.

Answer 1

Se si desidera sorprendere il proprio professore, è possibile utilizzare Simulated Annealing. Poi di nuovo, se lo gestisci, probabilmente puoi saltare alcuni corsi :). Si noti che questo algoritmo fornirà solo una risposta approssimativa.

Altrimenti: provare un algoritmo Backtracking o Branch and Bound. Entrambi troveranno la risposta ottimale.

Answer 2

Hai imparato gli alberi? È possibile creare un albero con tutte le possibili modifiche che portano al risultato desiderato. Il trucco, ovviamente, è evitare di creare l'intero albero, in particolare quando una parte di esso non è ovviamente la soluzione migliore, giusto?

Answer 3

Provare diversi algoritmi di ordinamento sugli stessi dati di input e stampare il minimo.

Answer 4

Penso che l'approccio appropriato sia quello di riflettere su quali proprietà definenti abbia un "costo" minimo. Quindi calcola il costo simulando questo tipo ideale. L'elemento chiave qui è che non devi implementare un algoritmo di ordinamento dei costi minimo generale.

Ad esempio, supponiamo che la proprietà di definizione di un ordinamento a costo minimo sia che ogni scambio inserisce almeno uno degli elementi scambiati nella posizione ordinata (non so se questo è vero). Ogni tipo di scambio piacerebbe essere in grado di avere questa proprietà, ma non è facile (possibile?) Nel caso generale. Tuttavia è possibile creare facilmente un programma che accetta una matrice non ordinata, prende la versione ordinata (che a sua volta può essere generata da un algoritmo non ottimale) e quindi utilizzando questa informazione decide il costo minimo per ottenere la matrice ordinata dall'array non ordinato.

Answer 5

Cosa intendi per "forza bruta?" Intendi "prova tutte le combinazioni possibili e seleziona il più economico?" Solo controllando.

Penso che "branch and bound" è quello che stai cercando - controlla qualsiasi fonte sugli algoritmi. È "come" la forza bruta, eccetto quando provi una sequenza di mosse, non appena quella sequenza di mosse è meno ottimale di qualsiasi altra sequenza di mosse provata finora, puoi abbandonare la sequenza che ti ha portato a quel punto - la costo. Questo è un sapore del "backtracking" menzionato sopra.

La mia lingua preferita per fare questo sarebbe Prolog ma sono strana.

La ricottura simulata è un algoritmo PROBABLISTICO: se lo spazio della soluzione ha minimi locali, è possibile che si rimanga intrappolato in uno e si ottenga ciò che si ritiene sia la risposta giusta ma non lo è. Ci sono modi per aggirarlo e la letteratura su tutto ciò può essere trovata, ma non sono d'accordo sul fatto che sia lo strumento che desideri.

Si potrebbe provare anche gli algoritmi genetici correlati se questo è il modo in cui si vuole andare.

Answer 6

Descrizione

penso che il modo più economico per farlo è quello di swap la voce fuori luogo più economico con l'elemento che appartiene al suo posto. Credo che questo riduca i costi spostando le cose più costose solo una volta. Se ci sono n elementi che sono fuori luogo, allora ci saranno al massimo n-1 swap per metterli a posto, al costo di n-1 * costo del minimo item + costo di tutti gli altri fuori luogo.

Se l'elemento globalmente più economico non è mal riposto e lo spread tra questo più economico e quello meno costoso è abbastanza grande, può essere più economico scambiare quello più economico nel suo posto corretto con quello meno costoso. Il costo quindi è n-1 * più economico + costo di tutti fuori luogo + costo di più economico fuori luogo.

Esempio

Per [4,1,2,3], questo algoritmo scambi (1,2) per la produzione di:

[4,2,1,3] 

e poi swap (3,1) per la produzione di :

[4,2,3,1] 

e poi swap (4,1) per la produzione:

[1,2,3,4] 

Si noti che ogni elemento fuori posto in [2,3,4] viene spostato una sola volta e viene scambiato con l'elemento di costo più basso.

Codice

Ops: "Si prega di non fornire un algoritmo completo, solo un approccio." Rimosso il mio codice.

Answer 7

Nel tentativo di farti solo andare avanti, questo potrebbe non avere senso.

Determina tutte le mosse possibili e il costo per ogni mossa e memorizza quelle in qualche modo, effettua la mossa meno costosa, quindi determina le mosse che possono essere eseguite da questa variazione, memorizzandole con il resto delle mosse memorizzate, esegui meno costoso ecc. fino a quando l'array non viene ordinato.

Mi piace risolvere cose come questa.

Answer 8

Questo problema è anche noto come il problema Silly Sort in alcuni concorsi ACM. Date un'occhiata a this solution utilizzando Divide & Conquer.