Teletrasporto viaggiatore, profitto ottimale nel tempo Problema

Question

Sono nuovo a tutto il problema da viaggio commesso così come StackOverflow quindi fatemi sapere se dico qualcosa che non è giusto.

Introduzione:

Sto cercando di codificare un algoritmo di multiple-trade profitto / tempo ottimizzati per un gioco che coinvolge più città (nodi) all'interno di più paesi (zone), dove:

• Il tempo fisico necessario per viaggiare tra due città collegate è sempre la stessa;
• Le città non sono linearmente collegati (si può teletrasportarsi tra alcune città nello stesso tempo);
• Alcuni paesi (aree) hanno itinerari di teletrasporto che rendono il percorso più breve disponibile attraverso altri paesi.
• Il viaggiatore (o commerciante) ha un limite sul suo coin-borsa, il peso dei suoi beni, e la quantità negoziabili in un certo commercio-percorso. La rotta commerciale può estendersi su più città.

---

Domanda Parametri:

Esiste già un database in memoria (python: sqlite) che detiene compravendite in base alla loro città di origine e la loro città di destinazione, le città dei cammini minimi inbetween come un array e quantità, e il fattore limitante, con il suo ritorno% sul totale il capitale (o nel caso in cui nessuno dei fattori stanno limitando, quindi solo il metodo che offre il più alto rendimento del capitale totale).

• Sto cercando di trovare il profitto ottimale per un certo pezzo di tempo prestabilito (cioè 30 minuti)
• L'atto di attraversare in una nuova città è in realtà simultanea
• Di solito ci vogliono la stessa quantità di tempo definito per viaggiare attraverso la mappa della città (vale a dire 2 minuti)
• L'atto di avvio del primo o qualsiasi nuovo commercio impiega lo stesso tempo di attraversare una mappa della città (vale a dire 2 minuti)
• Il mio punto di partenza potrebbe in realtà non hanno un mestiere valido (avrei dovuto viaggiare per la prima / più vicino / migliore)

---

Pseudo-Solution So Far

Ottimizzazione

In primo luogo, mi rendo conto che perché ho un limite al tempo che ci vuole, e so quanto tempo ogni hop richiederà (compreso -1 per intiating il commercio), posso limitare il grafico a cui tutti i mestieri luppolo sono sotto o pari a max_hops=int(max_time/route_time) -1. Ho tagliato elementi del database di commercio che non rientrano in questo limite di tempo, la potatura città che hanno percorso più breve lunghezza superiore a max_hops.

Faccio un'altra voce nel database mestieri che comprende le più breve percorsi tra la mia città attuale e le città di partenza di tutti i mestieri esistenti che non sono la mia città corrente, e dare loro un ritorno del 0%. Vorrei limitare questi al punto in cui il numero di città luppolo è inferiore a max_hops, e vorrei anche calcolare se l'attuale città per la città di partenza, più che commercia più breve-path-luppolo sarebbero durare più max_hops e rimuovere quelli che era anche meglio questo limite.

Allora prendo le restanti mestieri che non sono (current_city->starting_city) e aggiungere rotte commerciali con ritorno del 0% tra tutte le destinazioni e l'avvio città wheres il luppolo non durare più max_hops

Poi faccio un ultimo prugna per tutte le città che non sono nel database traffici sia come città di partenza, città di destinazione, o di una parte dei più brevi array percorso della città.

Graph ricerca Mi rimane un (molto) minore grafico di traffici possibili entro il limite di tempo (cioè 30 minuti).

Poiché tutti i nodi collegati sono adiacenti, i collegamenti sono per default tutti pesata 1. dividere il rendimento% rispetto al numero di salti nel commercio poi prendono l'inverso e aggiungere + 1 (ciò comporterebbe un peso 1,01 per un percorso di ritorno al 100%). Nel caso in cui il ritorno è 0%, aggiungo ... 2?

Si deve quindi restituire il percorso più redditizia ...

---

La questione:

Per lo più,

1. Come faccio ad aggiungere la possibilità di prendere percorsi multipli, quando ho lasciato più soldi o spazio e mantenere percorso di ricerca attraverso il percorso discrete per singole rotte commerciali? A causa della natura dei beni venduti a prezzi più e le quantità all'interno della città, ci sarebbero un sacco di sovrapposizione percorsi.

2. Come faccio a penalizzare l'avvio di una nuova rotta commerciale?

3. E 'di ricerca grafico anche utile in questa situazione?

Su un lato nota,

3. Quali tipi di prugne / ottimizzazioni per il grafico dovrei (o dovrei no) fare?
4. è il mio metodo di ponderazione corretta? Ho la sensazione che mi darà pesi sproporzionati. Devo usare il rendimento effettivo, invece di rendimento percentuale?
5. Se io sono la codifica in Python sono le biblioteche, come python-grafico adatto per i miei bisogni? O sarebbe me risparmiare un sacco di spese generali (a quanto ho capito, algoritmi di ricerca grafico può essere computazionalmente intensive) di scrivere una funzione specializzata?
6. Sono io best off utilizzando una ricerca *?
7. Dovrei essere precalcolato punti cammini minimi nel database commerciali e maxing ottimizzazioni o dovrei lasciare tutto al grafico-ricerca?
8. Si può notare tutto ciò che ho potuto migliorare?

Answer 1

Credo che tu abbia definito qualcosa che si inserisce in una classe di problemi chiamati inventario - problemi di routing. Presumo poiché avete entrambi i beni e moneta, il viaggiatore è sia acquisto e la vendita lungo il percorso scelto. Diamo prima supporre che tutto è deterministico - tutte le quantità di merci della domanda, offerta disponibile, acquisto e di vendita, ecc sono noti in anticipo. La versione stocastica diventa più difficile (ovviamente).

Uno degli obiettivi sarebbe quello di massimizzare i profitti con un vincolo sulla borsa e la merce. Se il viaggiatore deve tornare a casa il suo aspetto come un tour, in caso contrario, si presenta come un percorso. Dal momento che non è stato necessario il viaggiatore a visitare ogni nodo, NON è un TSP. Questo è un bene - più brevi problemi di cammino sono in genere molto più facile che TSP da risolvere.

A causa dei vincoli laterali e la scelta limitata di passi successivi a ogni nodo - mi piacerebbe prendere in considerazione usando la programmazione dinamica primo tentativo di una tecnica di soluzione. Essa vi aiuterà a enumerare ciò che si acquista e vende in ogni fase e c'è un numero limitato di fasi. Inoltre, poiché si mette un limite di tempo per la decisione, che limita lo spazio degli stati di scelte.

Per chi ha suggerito l'algoritmo di Djikstra - Forse hai ragione - le convenzioni di etichettatura dovrebbero includere il tempo, moneta, e dei beni e dei profitti corrispondenti. Può darsi che le ipotesi di Djikstra di potrebbero non funzionare per questo con la complessità del profitto. Non hanno ancora pensato attraverso questo.

Ecco un link ad un problema simile in capitale budgeting.

In bocca al lupo!

Answer 2

Se questo è un gioco dove si sta giocando contro gli esseri umani Vorrei assumere la dimensione totale dello spazio di dati è in realtà abbastanza limitata. Se è così sarei propenso a buttare fuori tutta la potatura di fantasia, come dubito ne vale la pena.

Al contrario, come su di una semplice ricerca in ampiezza?

Crea un elenco di tutte le città, contrassegnarli non visitato

Prendete la vostra città di partenza, segnare il tempo di viaggio come zero

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O (): il ciclo esterno viene eseguito città * massima luppolo volte. Il ciclo interno viene eseguito una volta per ogni città. Non sono necessari allocazioni di memoria.

Ora, per ogni aspetto della città a quello che si può comprare qui e vendere là. Quando per capire il tasso di rendimento su un commercio ricordare che la crescita è esponenziale, non lineare. Due volte l'utile di un mestiere che prende il doppio del tempo è non un buon affare! Look up come calcolare il tasso interno di rendimento.

Se la città corrente non ha commercio non perdere tempo con l'analisi completa, è sufficiente guardare oltre i vicini ed eseguire l'analisi su di loro, invece, l'aggiunta di uno alla volta per ogni mossa.

Se si dispone di cicli di CPU per risparmiare (e molto bene potrebbe, qualsiasi cosa significava per un essere umano di giocare avrà un aspetto abbastanza piccolo spazio per i dati) è possibile eseguire l'analisi su ogni città aggiungendo il tempo necessario per arrivare al città.

Modifica: Sulla base della sua commento avete tonnellate di potenza della CPU disponibili come il gioco non sia in esecuzione sul CPU. Mi alzo dalla mia soluzione: controllare tutto. Ho il forte sospetto che ci vorrà più tempo per ottenere il percorso e commercio informazioni di quanto non lo sarà per calcolare la soluzione ottimale.