Algoritmo per videogame

[Senzacervello]

Ciao a tutti. Spero che questo mio topic non sia fuori luogo, ma mi sto interrogando da tempo sul miglior modo di risolvere un problema specifico che mi sta torturando.

Descrivo: In un semplice videogame che sto disegnando con alcuni amici, abbiamo il problema di determinare l'utilizzo ottimale del carburante per un certo numero automobili impegnate in una corsa. In sostanza, ogni automobile ha un suo ammontare massimo di carburante alla partenza e consuma quantita' di carburante variabili in funzione della velocita'.

Le velocita' sono tre ognuna delle quali comporta un diverso consumo di combustibile al secondo.

Lo scopo e' trovare un algoritmo che calcoli il tempo minimo di percorrenza date la lunghezza del tracciato, la quantita' di carburante e le velocita' utilizzabili.

Quindi, date la lunghezza del tracciato (L) e la quantita' di carburante (C) e sapendo che

- alla velocita' V1 l'auto percorre "x" metri al secondo e consuma "x1" unita' di carburante;
- alla velocita' V2 l'auto percorre "x*2" metri al secondo e consuma "x1*2,5" unita' di carburante;
- alla velocita' V3 l'auto percorre "x*4" metri al secondo e consuma "x1*6" unita' di carburante

come mi suggerite di impostare l'algortimo per trovare il tempo minimo possibile di percorrenza a condizione che l'auto non consumi piu' del 90% del totale del carburante (C)?

Spero di essermi espresso in modo comprensibile. Se qualcuno mi potesse dare un suggerimento sarei molto felice. Grazie comunque per la pazienza

Ciao

Mauro

[axpgn]

Mi pare sia un problema più adatto alla sezione di "Ricerca operativa", lì sapranno darti migliori consigli sugli algoritmi più adatti.
Fai spostare il thread da un moderatore.

[vict85]

Hai che \(s = vt\) e \(c = C_0 - kt\) dove \(s\) è lo spazio percorso, \(v\) la velocità scelta, \(c\) la quantità di carburante, \(C_0\) la dimensione del serbatoio, \(k\) il consumo di carburante al secondo e \(t\) il tempo in secondi.
Siccome stai ponento \(c = 0\) (hai finito il carburante), puoi ricavare \(t\) dalla seconda equazione. Ovvero hai che \(\displaystyle t = \frac{C_0}{k}\). A questo punto ricavi che \(\displaystyle s = \frac{v}{k}C_0\). Siccome C_0 è lo stesso per tutte le velocità, non ti resta che confrontare i \(\displaystyle\frac{v_i}{k_i}\).

Il primo è pari a \(1\), il secondo a \(\displaystyle\frac{4}{5}\) e il terzo \(\displaystyle\frac{2}{3}\). Quindi il primo è quello più conveniente in termini di spazio percorribile. Cosa piuttosto prevedibile dato che l'aumento di velocità è accompagnato da un aumento più alto nei consumi.

Se invece vuoi fissare lo spazio. Hai che \(\displaystyle t = \frac{s}{v}\). Sostituisci nell'altra equazione e ricavi che \(\displaystyle (C_0 - c) = k\frac{s}{v}\). Insomma ti basta a questo punto vedere se \( \displaystyle (C_0 - c) > \frac{9C_0}{10}\)

[Senzacervello]

Hai che \(s = vt\) e \(c = C_0 - kt\) dove \(s\) è lo spazio percorso, \(v\) la velocità scelta, \(c\) la quantità di carburante, \(C_0\) la dimensione del serbatoio, \(k\) il consumo di carburante al secondo e \(t\) il tempo in secondi.
Siccome stai ponento \(c = 0\) (hai finito il carburante), puoi ricavare \(t\) dalla seconda equazione. Ovvero hai che \(\displaystyle t = \frac{C_0}{k}\). A questo punto ricavi che \(\displaystyle s = \frac{v}{k}C_0\). Siccome C_0 è lo stesso per tutte le velocità, non ti resta che confrontare i \(\displaystyle\frac{v_i}{k_i}\).

Il primo è pari a \(1\), il secondo a \(\displaystyle\frac{4}{5}\) e il terzo \(\displaystyle\frac{2}{3}\). Quindi il primo è quello più conveniente in termini di spazio percorribile. Cosa piuttosto prevedibile dato che l'aumento di velocità è accompagnato da un aumento più alto nei consumi.

Se invece vuoi fissare lo spazio. Hai che \(\displaystyle t = \frac{s}{v}\). Sostituisci nell'altra equazione e ricavi che \(\displaystyle (C_0 - c) = k\frac{s}{v}\). Insomma ti basta a questo punto vedere se \( \displaystyle (C_0 - c) > \frac{9C_0}{10}\)

Il mio problema e' diverso e, molto probabilmente, non mi sono espresso in modo del tutto comprensibile. Durante la gara le auto possono cambiare velocita' in modo da percorrere il tracciato nel minor "t" possibile. Alla "v1" sicuramente l'auto puo' percorrere l'intero tracciato e preservare una quantita' di carburante superiore al vincolo posto (C_residuo >= C*0.1), ma avra' gareggiato in modo sub ottimale poiche', se avesse incrementato la velocita' per un certo periodo, avrebbe impiegato meno tempo.

L'algoritmo che vorrei individuare dovrebbe darmi come risultante, ferme le condizioni, per quanto tempo l'auto viaggia a v1 (minimo possibile in quanto e' la velocita' minore), a v2 (minimo possibile poiche' non e' la velocita' massima) e a v3 (massimo possibile perche' e' la velocita' massima).

Avveo pensato di ricorrere ad una matrice, ma forse e' una sciocchezza

Spero di essere stato piu' chiaro

[vict85]

Ok, allora ha ragione axpgn, si tratta di un problema di ottimizzazione lineare. Insomma, hai tre tempi \(t_1\), \(t_2\) e \(t_3\) da trovare e le condizioni su spazio percorso e consumo. Con funzione obiettivo \(t = t_1 + t_2 + t_3\). Non sono un esperto, non è un argomento che ho trattato durante i miei studi.

[giammaria]

Il problema era stato originariamente postato in Scuola Secondaria e temo che una vera risposta tecnica sarebbe incomprensibile per il proponente; do una risposta a livello liceale.

Premesse
- Intendo che in frasi come "consuma "x1" unita' di carburante" sia sottinteso "al secondo".
- Non scrivo i calcoli intermedi, limitandomi all'impostazione e al risultato, che consiglio di controllare.
- Per brevità spesso non faccio distinzioni come quella fra $>$ e $>=$ e considero solo la più facile.
- Indico con $t_k$ il tempo (in secondi) in cui si viaggia alla velocità $v_k$ e con $c_k$ il relativo consumo al secondo.

Soluzione
Dobbiamo trovare la più piccola $y$ collegata al sistema
${(y=t_1+t_2+t_3), (v_1t_1+v_2t_2+v_3t_3=L),(c_1t_1+c_2t_2+c_3t_2<=90/100C):}$

Inoltre tutte le grandezze indicate devono essere positive (le $t_k$ possono annullarsi).
I dati dicono che si ha $v_2=2v_1; v_3=4v_1; c_2=5/2c_1; c_3=6c_1$ e conviene porre $L=av_1; 90/100C=bc_1$; il sistema diventa
${(y=t_1+t_2+t_3), (t_1+2t_2+4t_3=a),(t_1+5/2t_2+6t_3<=b):}$

Se si viaggiasse sempre alla velocità $v_1$ il consumo sarebbe $a$, quindi per $b<a$ non si può arrivare al traguardo col previsto margine di sicurezza. Se invece si viaggiasse sempre alla velocità $v_3$ il consumo sarebbe $3/2a$, quindi per $b>=3/2a$ si arriva in ogni caso e conviene usare sempre la massima velocità. Resta da esaminare cosa succede per valori intermedi di $b$.
Dalle due equazioni ricaviamo $t_1,t_2$ in funzione di $t_3=x$; otteniamo
${(t_3=x),(t_2=-3x-y+a),(t_1=2x+2y-a):}" "$ formule (1)

Le tre $t_k$ devono essere positive o nulle e deve valere l'altra limitazione, quindi dobbiamo avere
${(x>=0), (-3x-y+a>=0),(2x+2y-a>=0),((-3x-y+a)+5/2(2x+2y-a)+6x<=b):}->{(x>=0),(y<=-3x+a),(y>=-x+a/2),(y>=x+3a-2b):}$

Sul piano cartesiano, le prime tre disequazioni dicono che dobbiamo essere all'interno del triangolo di vertici $A(a/4,a/4), B(0,a),C(0,a/2)$. L'ultima dice che dobbiamo essere al di sopra di una retta $r$ che, restando parallela a se stessa, si abbassa all'aumentare di $b$; passa per A se $b=3/2a$, passa per B se $b=a$ e passa per C se $b=5/4a$. Osservando il disegno e ricordando che volevamo la $y$ accettabile più bassa possibile, distinguiamo due casi:
- se $a<b<5/4a$ la soluzione è l'intersezione di $r$ con l'asse $y$;
- se $5/4a<b<3/2a$ la soluzione è l'intersezione di $r$ con la $y=-x+a/2$
Sostituendo le coordinate (x,y) nelle formule (1) otteniamo i tempi desiderati. Non ho fatto i calcoli, facili ma noiosetti.

[Senzacervello]

Grazie infinite per la risposta.

... temo che una vera risposta tecnica sarebbe incomprensibile per il proponente; do una risposta a livello liceale.

Timore ben riposto visto che nella vita mi occupo di tutt'altro

Premesse
- Intendo che in frasi come "consuma "x1" unita' di carburante" sia sottinteso "al secondo".

Ovviamente e' riferito al consumo per unita' di tempo

Dalle due equazioni ricaviamo $t_1,t_2$ in funzione di $t_3=x$; otteniamo
${(t_3=x),(t_2=-3x-y+a),(t_1=2x+2y-a):}" "$ formule (1)

Chiedo venia, ma qui sono perso. Da quali due equazioni? Ammetto senza vergogna che il mio diploma liceale andrebbe stracciato senza indugi. Le sarei grato se potesse spiegarmi meglio questo passaggio.

Grazie per la pazienza

[giammaria]

Le due equazioni sono

${(y=t_1+t_2+t_3), (t_1+2t_2+4t_3=a):}$

Se fai i calcoli, con $t_3=x$, trovi i miei risultati.
P.S. Qui nel forum ci diamo tutti del tu, non del Lei.

[Senzacervello]

Le due equazioni sono

${(y=t_1+t_2+t_3), (t_1+2t_2+4t_3=a):}$

Se fai i calcoli, con $t_3=x$, trovi i miei risultati.
P.S. Qui nel forum ci diamo tutti del tu, non del Lei.

Grazie per l'indicazione, ma temo che dovro' rinunciare alla soluzione. Probabilmente mi sono assunto un compito che va oltre le mie reminiscenze scolastiche. Passero' le indicazioni a qualcuno del nostro piccolo entourage sperando che la memoria altrui si dimostri migliore della mia

Edit: Forse mi sono sottovalutato e devo editare di nuovo rispetto a poco fa. I passaggi di seguito sono corretti?

Se pongo $t_3=x$ e provo a ricavare $t_2$ nella prima equivalenza, ottengo che $t_2=y-x-t_1$. Andando a sostituire nella seconda equazione ho

$2t_2=a-t_1-4x$

quindi

$2(y-x-t_1)=a-t_1-4x$

$2y-2x-2t_1=a-t_1-4x$

$-t_1=a-2y-2x$

$t_1=2y+2x-a$

[giammaria]

Sì, è giusto ed infatti ottieni il mio stesso risultato; per avere $t_2$ ti basta sostituirlo nella tua $t_2=....$. Io avevo trovato più comodo ricavare $t_1$dalla prima equazione e sostituirlo nella seconda senza spostarne gli addendi (c'è qualche calcolo in meno), ma anche il tuo metodo va bene.