algo problème d'optimisation (trajet)

Version imprimable

16/06/2006, 16h47
gugumon

algo problème d'optimisation (trajet)

Bonjour,
Je prépare (enfin j'essaye) un examen de programmation.
Cependant je bloque sur un exercice non résolu, ayant peu d'expérience j'aimerai avoir votre avis afin de m'éclairer...Voici l'énoncé :

"On vous demande d'écrire un programme qui dira quels autostoppeurs il faut prendre pour arriver au plus vite à une destination"

on dispose des données suivantes :

on utilise deux tableaux (réel) Pi[i] donnant le % de niveau (si négatif c une descente) pendant L[i] (en km)
exe: si P[0]=2,00 et L[0]=120 =>on monte de 2 % pendant 120 km.

Le long du parcours sont postés N autostoppeur aux km (positif et croissant) a[i] et leur destination d[i].
exe: a[0]=24 d[0]=83 ==>autostoppeur au km 24 descend de la voiture au km 83.
La vitesse se calcul comme suit : vp-((pv+t)*p[i]) ou
vp =vitesse à plat (par exe 10)
pv=poid à vide (par ex 4)
t=nbr d'autostoppeur
p[i]=correspond à la monté ou descente.

Si la vitesse passe en dessous de vm (vitesse à pied exe 4) alors les autostoppeurs sortent de la voiture et la poussent pour assurer la vitesse de vm si il sont en nombre>=P[i].

C'est un problème d'optimisation. Je ne sais pas comment le résoudre, faut-il le représenter par un graphe ? Et dans ce cas utilisé un algorithme de programmation dynamique (genre bellman kabala ou dijkstra) ou utiliser une technique de programmation gloutonne??? Si quelqu'un peut m'aider je le remercie d'avance.
:cry:
16/06/2006, 18h22
Graffito

Bonjour,

La solution "bien bourrine" consiste à traiter toutes les solutions, à calculer le temps de trajet pour chacune et à prendre le meilleur.
Trouver "toutes" les solutions, c'est envisager pour chaque auto-stoppeur rencontré (et en cas de place disponible) si on le prend ou pas.

Cette approche se traduit par un arbre binaire de solutions. Une première optimisation (mais on peut faire mieux) consiste à ne pas refaire le calcul pour les sous-arbres déjà rencontrés, c'est à dire lorsque la voiture arrive au même choix (on prend ou non le nouvel autostoppeur avec les mêmes passagers à bord).
19/06/2006, 15h36
FrancisSourd

Je ne comprends pas bien cette contrainte:

Citation:

Envoyé par gugumon

Si la vitesse passe en dessous de vm (vitesse à pied exe 4) alors les autostoppeurs sortent de la voiture et la poussent pour assurer la vitesse de vm si il sont en nombre>=P[i].

Que font les occupants si la vitesse passe en dessous de vm mais que les autostoppeurs sont moins de P[i]?
19/06/2006, 15h41
FrancisSourd

Un autre question: peut-on débarquer un auto-stoppeur avant qu'il ait atteint son arrivée?
22/06/2006, 14h55
gugumon

si la vitesse passe en dessous de vm et que les occupants sont en nbr< p[i] alors la voiture s'arrête, on est bloqué. On ne peut pas débarquer un autostoppeur avant son d[i] (destination de l'autostoppeur en km).

J'ai essayé de résoudre le problème en utilisant la méthode "branch and bound" avec un arbre binaire. Le problème est exponentiel. On peut envisager d'économiser du temps calcul en mesurant une borne (par exemple au départ le trajet sans prendre d'autostoppeur) et de comparer le résultat à chaque noeud (si on dépasse la borne inutile de continuer), si on trouve un résultat meilleur on remplace la borne. Au niveau mémoire, on risque (dans le pire des cas) de se retrouver avec 2 * 2 exposant n - 1 noeuds (n étant les étapes de notre trajet, par exemple à chaque a[i],d[i],p[i] par ordre croissant). Voilà si vous avez une meilleur idée...
22/06/2006, 17h35
10_GOTO_10

Citation:

Envoyé par gugumon

Si la vitesse passe en dessous de vm (vitesse à pied exe 4)...

Change de bagnole. Une voiture qui ne dépasse pas 4 km/h, à mon avis, tu t'es fait avoir.

Citation:

Envoyé par gugumon

vp-((pv+t)*p[i])

La différence de vitesse est totalement proportionelle à la pente. Moi, je prendrais tous les auto-stoppeurs dont l'altitude de départ est supérieure à l'altitude d'arrivée, quelle que soient les dénivelées intermédiaires (conservation de la quantité de travail => on sera troujours gagnant dans ce cas). En première approximation (c'est vrai que l'histoire de faire pousser complique un peu).

[EDIT]Je dis n'importe nawak. Ca fera économiser l'essence peut-être, mais le temps, c'est pas évident du tout. Bon, oubliez tout ce que je viens de dire...[/EDIT]