Visitare punti su una linea numerica riducendo al minimo un costo non correlato alla distanza

Penso che puoi migliorarlo osservando il problema come un grafico diretto di coppie di posizioni.

Per questo esempio userò la linea con i valori -9, -6, -1, 3 e 5.

Poiché è troppo difficile disegnare un grafico con solo testo, rappresenterò le coppie come tabella. Possiamo pensare alle celle come a rappresentare lo stato in cui sono stati raccolti tutti i contenitori tra queste due posizioni. Ogni cella ha due valori, uno rappresenta il costo per andare a sinistra, l'altro rappresenta il costo per andare a destra (al successivo contenitore).

I valori possono essere semplicemente calcolati come la distanza tra i due punti moltiplicata per il numero di barili al di fuori di questi due punti + 1 . Le celle in cui entrambi i numeri hanno lo stesso segno rappresentano i casi in cui sono stati raccolti tutti i barili del segno opposto. Questi sono calcolati usando solo il numero di barili nella direzione lontano da zero.

Nella tabella valori di X significa che non puoi andare in quella direzione (tutti i barili in quella direzione sono stati presi). Le righe rappresentano la posizione corrente del raccoglitore e le colonne rappresentano la posizione del successivo barile opposto.

    +------+------+------+------+------+
    |  -9  |  -6  |  -1  |   3  |   5  |
+---+------+------+------+------+------+
|-9 |      |      |      | X, 24| X, 14|
+---+------+------+------+------+------+
|-6 | 3, X |      |      | 9, 27| 6, 22|
+---+------+------+------+------+------+
|-1 |      |10, X |      |20, 8 |15, 18|
+---+------+------+------+------+------+
| 3 |24, 4 |27, 6 |16, 8 |      | X, 2 |
+---+------+------+------+------+------+
| 5 |14, X |22, X |18, X |      |      |
+---+------+------+------+------+------+

Le regole per lo spostamento tra i quadrati possono essere un po 'confuse.

Per le colonne con numeri negativi, le regole sono le seguenti:

• La svolta a destra si sposta in basso di una cella.
• La svolta a sinistra si sposta in basso di una cella e quindi si specchia sulla diagonale.
• Se il valore corretto è X, andando a sinistra si passa alla diagonale (dove la colonna e la riga sono uguali) e lasciati da uno.

Per le colonne con numeri positivi, le regole sono le seguenti:

• La svolta a sinistra aumenta di una cella.
• Andando a destra, si sposta su una cella e poi si specchia sulla diagonale.
• Se il valore di sinistra è X, andando a destra si passa alla diagonale ea destra di uno.

Ora possiamo eseguire l'algoritmo di Dijkstra per calcolare il percorso migliore, utilizzando queste regole di movimento per attraversare il grafico. Le nostre posizioni di partenza sono (-1, 3) e (3, -1) con costi iniziali di 5 e 15, rispettivamente. Una volta calcolati i valori per le due posizioni finali (a sinistra di (-9, -9) e a destra di (5, 5)) la minore delle due è la nostra risposta.

Il tempo di esecuzione per ciascuno dei passaggi è:

• O (N log N) per l'ordinamento iniziale dei valori di input lungo la linea
• O (N ^ 2) per il calcolo della tabella / grafico
• O (N ^ 2 log N) per eseguire Dijkstra sul grafico (Nota: ci sono al massimo due bordi per ogni vertice dato).

I primi due passaggi sono dominati dall'ultimo, quindi il tuo runtime complessivo è O (N ^ 2 log N) che dovrebbe essere un runtime abbastanza buono per la sfida.

Distanza più breve

Ho scritto un'applicazione Java ieri per risolvere il problema. Il problema è fondamentalmente un problema di distanza più breve, come ha detto SRJ nel suo commento. La radiazione mostra semplicemente che puoi accumulare un valore insieme alla distanza più breve.

Fondamentalmente, ecco cosa ho fatto.

• Inserisci i numeri dei contenitori in un elenco < Integer >
• Mentre la lista contiene elementi;
  • Trova l'elemento (i) più vicino
  • Se c'è un elemento, vai lì e rimuovi l'elemento.
  • Se ci sono due elementi, copia il percorso e vai a entrambi gli elementi
• Trova il percorso con il valore di radiazione più piccolo.

Ecco alcuni output dall'applicazione

10 containers are located at [-90, -75, -47, -9, 9, 26, 48, 50, 64, 79].

You walk to position -9 and pick up the container.  The total radiation emitted is 90 units.
You walk to position 9 and pick up the container.  The total radiation emitted is 252 units.
You walk to position 26 and pick up the container.  The total radiation emitted is 388 units.
You walk to position 48 and pick up the container.  The total radiation emitted is 542 units.
You walk to position 50 and pick up the container.  The total radiation emitted is 554 units.
You walk to position 64 and pick up the container.  The total radiation emitted is 624 units.
You walk to position 79 and pick up the container.  The total radiation emitted is 684 units.
You walk to position -47 and pick up the container.  The total radiation emitted is 1,062 units.
You walk to position -75 and pick up the container.  The total radiation emitted is 1,118 units.
You walk to position -90 and pick up the container.  The total radiation emitted is 1,133 units.

Non ho ottimizzato l'algoritmo in alcun modo. Non ho nemmeno notato che l'elenco di numeri di input è stato ordinato. (Sono un doofus.)

Quando ho eseguito il mio codice con i valori massimi, 1.000 contenitori e un intervallo compreso tra -500.000 e 500.000, il mio codice impiegava 3 secondi per essere eseguito. La maggior parte di quel tempo stava scrivendo le 1.000 linee di stampa sulla console.

Non sono una persona O grande, ma penso che la mia forza bruta che percorre l'algoritmo del percorso più breve sia O (N al quadrato), non O (N!).

Se ho approfittato del fatto che i numeri di input sono ordinati, così ho dovuto solo controllare i due numeri su entrambi i lati di dove mi trovo attualmente, potrei far scendere l'applicazione vicino a O (N) . Devo solo controllare 2 numeri perché sto rimuovendo gli elementi dall'Elenco mentre arrivo a loro.

Hai usato algoritmi diversi, come l'algoritmo ingordo, per trovare una soluzione approssimativa.

Se il mio programma avesse impiegato 3 ore per essere eseguito anziché 3 secondi, allora avresti una scelta da fare.

La soluzione abbastanza buona è abbastanza buona?

In altre parole, sono disposto a negoziare la velocità di elaborazione per una risposta sufficientemente buona?

Se una risposta abbastanza buona è abbastanza buona, allora usi gli algoritmi di approssimazione.

Se vuoi la risposta perfetta, devi percorrere tutti i cammini più corti. Non c'è scorciatoia.

Se qualcuno vuole che inserisca il mio codice, lo farò. Sono sicuro che ci sono ancora bug, perché volevo vedere se potevo implementare un algoritmo di camminata più breve.

Ho una soluzione che risolverà questo problema in 2^N time, che è scadente, ma penso che sia un modo utile per inquadrare il problema, quindi ho pensato di pubblicare.

Invece di modellare il problema come un grafico, modellerei è un albero decisionale binario (diciamo T ). Ad ogni livello devi scegliere se andare a destra oa sinistra. È abbastanza facile calcolare il "costo" di ogni spigolo. Lascia che h(K) sia l'altezza del nodo corrente, K , quindi il costo del margine che va a left_child(K) = h(K) x dist(K, left_child(K)) . Un calcolo simile è sufficiente per il costo del margine per il bambino giusto. Costruisci questo albero e tieni traccia del costo cumulativo dei bordi fino in fondo, e segnala il percorso al nodo foglia con il minor costo totale.

Si noti che il calcolo dei costi funziona perché la lunghezza di ciascun margine dist(K, left_child(K)) rappresenta il tempo necessario per passare al sito successivo, mentre l'altezza della sottostruttura è il numero di siti rimanenti (ad esempio, emissione continua di radiazioni).

Ora il trucco all'interno di questa struttura è determinare se ci sono alcune euristiche che puoi usare per "provare" che puoi ignorare espandendo la ricerca lungo un ramo. La mia intuizione è che per qualsiasi euristica di questo tipo esiste una disposizione di siti che la sconfiggeranno, ma forse qualcuno può inventare qualcosa.

Un numero ha proposto di applicare soluzioni di percorso più brevi per i grafici, ho qualche dubbio sul fatto che una soluzione del genere possa funzionare. I tuoi vicini nel "grafico" del problema cambieranno a seconda del percorso che segui. Ad esempio nel tuo post originale con [-12, -2, 3, 7] se vai a -2 allora -12 e 3 diventano 'vicini di casa' e se vai a 3 allora -2 e 7 sono vicini. Ogni possibile 'coppia' di valori positivi e negativi può essere potenzialmente nebulosa nel grafico finale. Non conosco alcun algoritmo di percorso più breve che sia dimostrabilmente corretto in un grafico dinamico.

Penso che abbia più senso pensare a ogni stadio semplicemente come una scelta binaria tra andare direttamente al barile più vicino e andare a sinistra al barile più vicino. Basta avere una funzione di costo che dettaglia il numero di unità di radiazioni che sarebbero state sostenute in totale facendo qualsiasi movimento e scegliere quello con il costo più basso.

NON consideri semplicemente il barile più vicino, ma supponi invece che spostandoti da un barile tu stia effettivamente aggiungendo il raddoppio della radiazione perché spostandoti hai anche dovuto sostenere il costo di dover tornare indietro in quella direzione più tardi.

Nel tuo esempio di [-12, -2,3,7], spostandoti a sinistra dovresti incorrere in un totale di 14 (2 + 2 + 10) a sinistra, e 18 (2 + 2 + 5 + 9) su il diritto, per un totale di 22. Muovere a destra dovrebbe comportare 10 (3 + 3 + 4) a destra, e 26 (3 + 3 + 5 + 15) a destra. Chiaramente a sinistra è la soluzione giusta in un primo momento. Un calcolo simile può essere fatto per ogni movimento successivo.

Dopo che il problema si riduce sostanzialmente a una ricerca, la complessità dovrebbe essere O (nlog (n)), che è MOLTO meglio di O (n!). Credo che questa sia necessariamente la complessità più bassa che possa esistere per questo problema poiché è fondamentalmente un algoritmo di ricerca basato sul confronto per il quale non è possibile fare meglio di O (nlog (n))

Apparentemente non ero abbastanza chiaro con questa descrizione, quindi ho deciso di renderlo un po 'più programmatico: 1. Calcola il costo sostenuto andando a sinistra, e il costo sostenuto andando a destra in base alla posizione corrente 2. Spostati nella direzione meno costosa 3. Togli il barile raggiunto dalla considerazione nel calcolare il costo dello spostamento in una direzione

Calcolo del costo: 1. Identifica il barile più vicino nella direzione indicata. Diciamo che $ dist è la distanza dalla posizione attuale al barile più vicino nella direzione data. 2. Il costo è inizializzato come N * $ dist dove N considera solo i barili ancora attivi. 3. A questo, aggiungi la distanza che la nuova posizione indicata da $ dist sarebbe da ogni barile rimasto.

Soluzione parziale - Ci tornerò più tardi.

Supponiamo che la strategia "predefinita" sia eseguita a sinistra o a destra, a seconda di quale sia più economica. Ora chiedi, vale la pena fare un piccolo viaggio nell'altro modo per prendere un barile. È abbastanza facile calcolare la risposta.

Per l'esempio di input, correre tutto a destra è più economico di tutto il resto. Vale per -2 vale un viaggio di andata? Riduce il costo della corsa fino a destra e poi torna a 0 per 14 (perché stavi "pagando" 4 unità di radiazione per mossa da 0 a 3 sulla strategia predefinita, ora è giù a 3, pagavi 3 da 3 a 7, ora è 2, ecc.), più riduce di uno per mossa il costo del passaggio da 0 a -2, risparmiando così 2 ulteriori per un totale di 16.

Tuttavia, aggiunge un costo di andare a -2 e poi di ritornare a 0 di 14 (4 unità per mossa a -2, 3 per muovere indietro a 0), per un guadagno netto di (16-14) = 2. Nota che per calcolare questo non devi valutare il costo esatto per risolvere l'intero problema per ogni decisione: hai abbastanza informazioni per decidere solo sapendo se correre tutto a sinistra è più economico di correre tutto a destra, oltre a come molti contenitori di rifiuti sono su ciascun lato di te e la distanza dal più vicino 2. Quindi questo è O (N ^ 2).

Tranne per un problema importante - ho pensato che tu correrai fino alla fine, e sappiamo che potresti contraccambiare. Per pulirlo, dobbiamo aggiornare il mio calcolo. Per l'input del campione, ho pensato che avresti risparmiato 14 emettendo 1 radiazione totale in meno per unità al secondo mentre corressi da 0 a 7 e viceversa. Ma, se si raddoppia prima di correre a 7, i risparmi si ridurranno.

È piuttosto brutto, perché, non so come calcolare il prossimo doppio dorso senza provare tutte le possibilità, il che ci riporta a O (2 ^ N).

Tranne che è 2 ^ N con la potatura. Ho calcolato che il "viaggio laterale" a -2 costava 14, ma ho guadagnato 16, se non avessi avuto più trasferte prima di arrivare al numero più a destra. Se il numero più a destra fosse stato 5, saprei immediatamente che il viaggio di andata a -2 non potrebbe essere ripagato. (Costo ancora 14, massimo beneficio 12). Né devo prendere in considerazione l'idea di andare a -2, quindi fare una deviazione prima di raggiungere i 6, dato che è sempre inferiore a andare direttamente a quel punto in primo luogo.

Penso che tu possa risolverlo usando una ricerca in ampiezza, mantenendo non più di 2 * N ^ 2 tuple di (boolean, int, int, int, string) dove le stringhe sono lunghe quanto il percorso è complicato.

Le tuple sono (minimo o massimo booleano, posizione minima percorsa, posizione massima percorsa, radiazione totale emessa, storia del percorso).

Vedo che l'algoritmo procede in questo modo:

1. Inizializza il pool di tuple in una singola voce, (min, 0, 0, 0, "")
2. Trova un elemento nel pool con radiazioni minime emesse. Se il minimo e il massimo corrispondono al minimo e al massimo di tutti i barili, la cronologia del percorso è ottimale soluzione. Altrimenti cancellalo dal pool.
3. Calcola i 2 discendenti di questa tupla, ognuno dei quali corrisponde a camminare a sinistra oa destra verso il successivo barile non trattato.
4. Inserisci i discendenti nella piscina. Se esiste già un elemento nel pool con lo stesso valore booleano, min e max come nuovo discendente, quindi eliminare l'elemento con il conteggio di radiazioni più elevato.
5. goto 2.

Trovare e rimuovere tuple dominate migliorerà sensibilmente le prestazioni. Potrebbe essere utile aggiungere un flag "ha generato" a ciascuna tupla e lasciare le tuple allevate nel pool.

Ci sono anche alcune decisioni importanti da prendere nel decidere come conservare le tuple e cercare in loro domini e nuovi elementi da allevare.