Misez p'tit, Optimisez - N°77 - En route pour Les Spectacles

[C.Ret]

Bonjour à toutes et à tous.

Plus qu'une semaine pour organiser mon voyage à Paris pour participer aux 19ième minipoketicaires.



je n'ai aucune confiance dans le système de navigation embarqué de mon véhicule. Et les panneaux d'indicateur de direction fiables de plus en plus rares. J'aurais nettement préféré que mon itinéraire soit calculé par des gens sérieux.


Par ailleurs je ne compte pas m'embarrasser de bagages lourds ou encombrant. l'idéal serait qu'un de mes pockets me permette de trouver l'itinéraire le plus adapté à mon déplacement et m'aide à en réduire les coûts.

Le challenge proposé pour ce Miser Petit Optimiser est de m'indiquer comment exploiter au mieux l'une ou l'autre de nos Calculettes, Pocket ou Autre Assistant Numérique pour déterminer que devra être mon itinéraire sans utiliser Google Map et autres Mappy.

J'espère ainsi pourvoir utiliser l'un des ces équipements pour me rendre à mon rendez-vous.
Je compte sur votre expertise et ingéniosités pour me proposer un système qui exploitera au mieux les capacités de nos calculettes afin de me fournir :

• - le kilométrage de l'itinéraire le plus court possible depuis LUXEMBOURG.
  - le temps de parcours minimal de l'itinéraire le plus rapide.
  - le coût de l'itinéraire le plus économique en tenant compte de la consommation de mon véhicule et des éventuels péages,

Mon véhicule consomme en moyenne 5.2 l aux 100.km d'un mélange spécifique diesel que j'obtiens en ce moment au prix forfaitaire de 1.128 €/l.

En fonction des capacité de votre système, d'autres informations subsidiaires pourront être fournies en option, mais cela ne sera qu'un bonus.

Evidemment, un maximum d'information supplémentaires sont attendues sur les calculettes graphiques et autres monstres actuels,

Inversement, pour les dispositifs les plus anciens, on comprendra qu'un code ne puisse fournir qu'un minimum d'information.
Mais c'est tout le charme d'untel exercice; chacun des trois résultats attendus pourra très facilement faire l'objet de trois codes différents.



Dans le même esprit, vos codes pourront être ou non paramétriques et servir ou non à d'autre véhicule, utilisant d'autre carburant, occasionnant d'autres coûts et parcourant d'autres cartes !



Je déplie ci-dessous ma carte routière où figure les axes et villes que je connais ainsi que les distances, temps de parcours et éventuel péages :

mpo77map.gif (211.92 Kio) Vu 10324 fois

[zpalm]

Un joli MPO mais qui n'a de petit que le nom... tu risques de ne pas arriver à temps aux prochains minipocketicaires

[dprtl]

Dans leur cursus, de nombreux étudiants en informatique ont implémenté un jour le fameux algorithme de Dijkstra. Il reste très utilisé aujourd'hui dans les protocoles de routage du type IS-IS ou OSPF.

[C.Ret]

Un joli MPO mais qui n'a de petit que le nom... tu risques de ne pas arriver à temps aux prochains minipocketicaires

Si si j'y serai à temps, il ne faut pas que j'oublie mon HP-41C en partant

[jxano]

Cinquante-et-une arêtes ! Joli graphe.

Avec mon fx-730P équipé d'une RP-8, je peux me permettre une implantation peu économe en mémoire. Le nombre d'étapes est-il minimal ? Si oui, un parcours en largeur sera le plus indiqué, sinon on ira en profondeur...

[C.Ret]

Toutes les astuces sont les bienvenues...
... ce qui compte est de bien expliquer ce que l'on fait.
A la limite, rien n'oblige à programmer un truc. Un algo et une feuille de papier, une quatre opération M+ M- MR ey un crayon sont , à la limite, recevable.

Le graph est grand (je me suis un peu emporté sur ce coup là !)

C'est la principale difficulté (je m'emporte souvent), le graphe est grand pour une calculette. Mais rien n'oblige à le mémoriser ! On peut faie "bosser" l'utilisateur qui sait le lire

Deux approches sont possibles;
- coder/mémoriser ma carte, ce qui rendra l'utilisation du code plus facile, mais rend le code spécifique à cette carte et consomme des octets (ce qui n'est pas l'idéal dans un MPO),
- faire en sorte que le code interroge l'utilisateur quie "entrera" rn quelque sorte la carte au cours du déroulement du code. Ce qui fera économiser de précieux octets et rendra le code utilisable sur n'importe quelle carte. Mais, l'opération devra peut-être être recommencée pour chaque détermination. Tant pis. Il y aura aussi quelques octets nécessaire pour soigner la présentation ou indiquer à l'utilisateur ce qu'attend le programme.

J'ai choisi la seconde solution. Mais rien n'interdit la première. Sauf peut-être la capacité mémoire ?

[jxano]

Je compte bien faire bosser la machine à ma place, c'est tout son intérêt.

Pour l'instant, la saisie de la carte est faite sous forme de tableau, et ma calculette est capable d'en déduire une liste triée de villes avec pour chacune la liste de ses voisines.

Après réflexion, le kilométrage paraît accessoire par rapport au coût et à la durée du voyage, selon la priorité que tu auras lors de ton départ. Il me semble opportun de connaître les villes à traverser, ainsi que le coût du voyage de durée minimale et la durée de celui le moins cher. Cela nous donnera des fourchettes pour choisir un itinéraire éventuel conciliant au mieux les deux priorités.

[C.Ret]

L'avantage d'avoir mémorisé la "carte"est que l'on peut faire les trois déterminations facilement et sans avoir à tout recommencer.

Je suis parti avec un Pocket moins puissant; la carte n'est pas mémorisée. Changer les priorités revient à recommencer la détermination et donc la "saisie" de la carte.

Mais c'est le Pocket qui fait avancer la détermination. A chaque pas, il indique la ville étape qui lui parait la plus judicieuse et demande à l'utilisateur de saisir les villes voisines en indiquant à chaque fois les km, temps et péage (pour la version la plus abouti - la version la plus 'optimisée' ne demande que le seul paramètre à optimiser )
Mais, il y a certainement d'autres façon de faire.

Je vais moi aussi essayer de "mémoriser" la carte dans mon Pocket. Il va falloir que je ruse un peu. Heureusement j'ai l'accessoire idéal pour cela :



Et si cet accessoire ne suffit pas, j'utiliserai celui-ci:



Ce sera 'automatique', mais juste un peu plus lent


P.S.: 'Mémoriser' ma carte en dur dans mon Pocket fait perdre l'intérêt principale de la méthode qui peut être utilisée pour tout déplacement et à partir de n'importe quelle carte.
Je vais essayer de faire un programme hybride en deux parties; la première qui 'mémorise' ma carte et la seconde qui l'analyse pour répondre à l'une ou l'autre des trois questions.

[jxano]

Je n'ai guère avancé dans mon code, sinon par l'ajout de la double multiplication qui transforme les kilomètres en euros.

Je m'oriente vers un parcours en largeur au départ de Luxembourg qui produira deux, voire trois arbres d'itinéraires optimaux, un selon chaque critère de coût, de temps et de distance. Il me faudra implanter une file d'attente et ajouter des colonnes de nombres à la liste des villes.

Une chose remarquable dans cette carte : si on ajoute des sommets à Rethel et à Soissons (là où des paires d'arcs se croisent), le graphe résultant n'est composé que de triangles, avec tous les arcs dans le même plan. J'imagine qu'on pourrait en faire une représentation graphique sans utiliser les coordonnées de la carte.

[jxano]

J'ai changé mon fusil d'épaule, et même de de fusil tout court, puisque j'ai troqué mon fx-730P contre un fx-880P, plus maniable et moins limité.

Aux erreurs de recopie près, j'ai implanté mon parcours en largeur et je connais désormais deux itinéraires optimaux.

Le plus rapide, en 5 h 1 min, pour un coût total, péage compris, de 36,92 euros : Luxembourg - Verdun - Reims - Meaux - Paris.

Le moins cher, à 22,79 euros, d'une durée de 6 h 9 min : Luxembourg - Verdun - Saint-Dizier - Sézanne - Meaux - Paris.

Le code n'est pas très long, et son exécution non plus, puisqu'il parcourt chacun des 22 sommets une fois, avec contrôle de ses voisins. Je le détaillerai dans un prochain message.

[C.Ret]

Ah! La description de l'algorithme ressemble comme deux gouttes d'eau à celui que j'utilise sur mes machines.

Par contre, je trouve des parcours aux statistiques sensiblement identiques :

- Itinéraire le plus court :

Code : Tout sélectionner

|LUXEMBO PARIS 341.7 5:17|  Luxembourg Paris    341.7 km   5h17min
|17L 26.94$  6.90p  64.67|  Consommation 17 litres
                            Coût estimé 26.94€ dont 6.90€ de péage
                            Vitesse moyenne 64.67 km/h
|LUXEMBO VERDUN CHALONS  |
|MEAUX PARIS             |  

- Itinéraire le plus rapide :

Code : Tout sélectionner

|LUXEMBO PARIS 383.4 5:11|  Luxembourg Paris    383.4 km   5h11min
|19L 30.98$  8.50p  73.96|  Consommation 19 litre
                            Coût estimé 30.98€ dont 8€50 de péage
                            Vitesse moyenne 73.96 km/h
|LUXEMBO VERDUN CHALONS  |
|SEZANNE EVRY PARIS      |  

- Itinéraire le plus économique:

Code : Tout sélectionner

|LUXEMBO PARIS 388.9 6:02|  Luxembourg Paris    388.9 km   6h02min 
|20L 22.81$  0.00p  64.45|  Consommation 20 litre
|LUXEMBO  VIRTON CHARLEV |  Coût estimé 22.81€ aucun péage
| LAON MEAUX  PARIS      |  Vitesse moyenne 64.45 km/h

Mais, il faut que je vérifie tout cela, je ne suis pas à l'abri d'une erreur de saisie (différente entre chaque détermination, car je dois à chaque fois recommencer les saisies pour chaque ville scrutée par l'algorithme.

Mais comme le signale jxano, chaque ville n'est examinée qu'une seule fois, ce qui rend les choses tout à fait réalisables.

J'ai également réussit à "mémoriser" la carte, ce qui ne prend pas tant de mémoire que cela en rusant un peu. En particulier, il faut bien 'préparer' l'ordre de la saisie pour que cela fonctionne sur PC-1211 et théoriquement sur HP-41C. Mais je dois encore adapter le code depuis celui du SHARP PC-1360 qui n'est pas encore parfaitement optimal mais qui a l'avantage d'afficher les informations bien formatées et permet un débogage plus aisé.

[caloubugs]

N'empêche, c'est joli.

Et proposer le problème du voyageur de commerce (connexe au problème de sommes de sous-ensembles, c'est un problème dit NP-Complet) en MPO alors qu'il n'existe pas d'algorithme de résolution à ce jour (excepté des algos qui travaillent en valeurs approchées pour être en temps polynomial), fallait oser
Pour 15 villes, c'est 43 milliards de chemins différents potentiels à regarder...

Intéressé du coup pour voir l'algo (faut que je m'y plonge aussi dès que j'en ai un peu le temps).

Si jamais vous trouvez un truc qui fonctionne direct, je pense que ça pourrait intéresser du monde, faudra déposer le brevet rapidement (avant TomTom and co)... C'est un coup à devenir super riche.

[jxano]

On ne s'intéresse pas au parcours complet de tous les sommets, mais aux minima entre deux sommets, ce qui est loin d'être NP-complet. De plus, on ne calcule pas plus d'une ligne de ce qui est présenté comme une matrice dans certains ouvrages.

Je vais détailler un peu mon algorithme. Les données sont sous la forme :

Code : Tout sélectionner

1000 DATA AMIENS,ST-QTIN,64,85.7,0,AMIENS,CPIEGNE,72,86.2,7.2
1002 DATA AMIENS,BVAIS,50,62.2,4,5,BVAIS,CPIEGNE,53,59,3,0
etc.
1050 DATA CH-MEZ,VIRTON,70,71.4,0

J'ai repris les abréviations adoptées sur 730 à cause de sa limitation de chaînes à sept caractères, et de toute façon, je n'aime pas afficher de trop longs trucs sur un petit écran. Ce sont tous les arcs du graphe, avec les deux villes-sommets, le temps de trajet en minutes, le kilométrage et le péage, nul si inexistant.

Avec ça, je vais construire une liste de villes (que j'ai triée, mais j'aurais pu me limiter à un tableau dédoublonné). Chaque ville est le départ d'une liste secondaire de ses voisines, chaînées dans un autre tableau. Les arcs seront mémorisés à la suite dans des tableaux simples. Avec la file de successeurs qui fera le coeur de l'algorithme, ce sera tout comme structures internes.

Code : Tout sélectionner

10 PRINT"MPO77: EN ROUTE DE LUXEMBOURG A PARIS": CLEAR
12 DIM K(50),C(50),T(50),N$(21),S(21,3*4+1),V(101,1),F(22)

La première partie du code (20 à 29) est une boucle qui alimente les tableaux simples, appelle deux fois par tour un sous-programme d'insertion en ordre et bâtit les listes secondaires avec les deux retours.

Code : Tout sélectionner

20 I=0:D0=-1:V=0
21 IF I=51 THEN GOTO 30
22 READ D$,A$,T(I),K(I),P:C(I)=K(I)*.052*1.128+P:PRINT CHR$(32+I);
24 Z$=A$:GOSUB 100:X=J
25 Z$=D$:GOSUB 100:Y=J
26 V(V,0)=X:V(V,1)=S(Y,1):S(Y,1)=V:V=V+1
27 V(V,0)=Y:V(V,1)=S(X,1):S(X,1)=V:V=V+1
29 I=I+1:GOTO 21

Pas de boucle FOR, elle ne ferait pas bon ménage avec les GOSUB. J'inclus les péages à la consommation pour avec un seul tableau en euros. La colonne 0 du tableau S et la variable D0 constituent le chaînage en ordre des villes ; la colonne 1 de S contient les débuts des suites de successeurs pour chaque sommet.

Code : Tout sélectionner

100 J=D0:A0=-1
101 IF J=-1 THEN GOTO 106
102 IF Z$=N$(J)THEN RETURN
103 IF Z$<N$(J)THEN GOTO 106
105 A0=J:J=S(J,0):GOTO 101
106 N$(N)=Z$:S(N,0)=J:S(N,1)=-1
107 IF A0<>-1 THEN S(A0,0)=N ELSE D0=N
109 J=N:N=N+1:RETURN

Nous avons trois notions : les sommets (villes,avec leurs noms), les arcs (avec les consommations, durées et longueurs) et les trajets d'une ville à l'autre, deux par arc. J'affiche ensuite les villes avec leurs successeurs pour m'assurer que l'âme de ma structure est en place.

Code : Tout sélectionner

30 I=D0
31 IF I=-1 THEN GOTO 40
32 PRINT N$(I);" :";:J=S(i,1)
33 IF J=-1 THEN PRINT"": GOTO 39
35 PRINT" ";N$(V(J,0));
38 J=V(J,1):GOTO 33
39 I=S(I,1):GOTO 31

Maintenant, le parcours en largeur depuis Luxembourg, nécessitant quantité de remises à zéro. Il s'agit de garnir le reste du tableau S avec tout un paquet de données numériques :

• colonne 2 : temps de parcours minimum (et pointage des villes parcourues) ;
• colonne 3 : coût pour le temps de parcours minimum ;
• colonne 4 : distance en km pour le temps de parcours minimum ;
• colonne 5 : ville précédente pour le temps de parcours minimum ;
• colonne 6 : temps de parcours pour le coût minimal ;
• colonne 7 : coût minimal ;
• colonne 8 : distance en km pour le coût minimal ;
• colonne 9 : ville précédente pour le coût minimal ;
• colonne 10 : temps de parcours pour la distance minimale ;
• colonne 11 : coût pour la distance minimale ;
• colonne 12 : distance en km minimale ;
• colonne 13 : ville précédente pour la distance minimale.

J'ai ajouté entre temps les kilométrages bruts.

Code : Tout sélectionner

40 FOR I=0TO21:S(I,2)=0:S(I,7)=0:S(I,12)=0:NEXT I:S(17,5)=-1:S(17,9)=-1:S(17,13)=-1:S(17,2)=.1:T=1:Q=0:F(0)=17
41 IF T=Q THEN GOTO 60
42 PRINT "DEP: ";:I=S(F(Q),1)
43 IF I=-1 THEN GOTO 59
44 J=V(I,0):K=INT(i/2):IF S(J,2)=0;GOTO 50
45 PRINT"(";N$(F(Q));" ";N$(J);")";
46 IF S(J,2)>S(F(Q),2)+T(K)THEN S(J,2)=S(F(Q),2)+T(K):S(J,3)=S(F(Q),3)+C(K):S(J,4)=S(F(Q),4)+K(K):S(J,5)=F(Q):PRINT"<T>";S(J,2);
47 IF S(J,7)>S(F(Q),7)+C(K)THEN S(J,6)=S(F(Q),6)+T(K):S(J,7)=S(F(Q),7)+C(K):S(J,8)=S(F(Q),8)+K(K):S(J,9)=F(Q):PRINT"<C>";S(J,7);
48 IF S(J,12)>S(F(Q),12)+K(K)THEN S(J,10)=S(F(Q),10)+T(K):S(J,11)=S(F(Q),11)+C(K):S(J,12)=S(F(Q),12)+K(K):S(J,13)=F(Q):PRINT"<K>";S(J,12);
49 PRINT"":GOTO 56
50 PRINT N$(F(Q));"->";N$(J);" T";T(K);" C";C(K);" K";K(K):F(T)=J:T=T+1
51 S(J,2)=S(F(Q),2)+T(K):S(J,3)=S(F(Q),3)+C(K):S(J,4)=S(F(Q),4)+K(K):S(J,5)=F(Q)
52 S(J,6)=S(F(Q),6)+T(K):S(J,7)=S(F(Q),7)+C(K):S(J,8)=S(F(Q),8)+K(K):S(J,9)=F(Q)
53 S(J,10)=S(F(Q),10)+T(K):S(J,11)=S(F(Q),11)+C(K):S(J,12)=S(F(Q),12)+K(K):S(J,13)=F(Q)
56 I=V(I,1):GOTO 43
59 Q=Q+1:GOTO 41

Voilà pour l'essentiel ; je ferai quelques compléments dans l'après-midi ou demain.

[C.Ret]

Je n'en dirai pas plus moi non plus pas beaucoup plus sur le forum avant la réunion de ce soir.

Pour comparaison, avec les travaux de jxano, je donne ma représentation de la carte.

Elle n'est pas sous forme de DATA, car non directement liée au code.
La carte peut être mémorisée préalablement ou au fur et à mesure des déterminations.

comme jxano, je ne mémorise que 6 ou 7 caractères pour désigner une ville (de façon à faciliter les affichages).

Comme remarqué ci-dessus, ma carte se compose de 22 villes et 51 liaisons. L'idée directrice est de ne 'mémoriser' chaque liaison qu'une seule fois.

Soit J et I les indices de deux villes connectée, liaison ne figure qu'une fois, soit à l'indice I, soit à l'indice J, mais jamais au deux.
Une liaison est mémoriser dans le I-ième registre mémoire sous la forme d'un nombre : jj.kkkkhmmpp qui permet de décrire la distance kkkk (en hectomètres), la durée du trajet (en h:mm) et l'éventuel montant du péage (en dizaines de centimes):


Voici un exemple de représentation de la carte optimisé pour réduire le nombre de colonnes nécessaire :

Code : Tout sélectionner

##:Localit pleagmnt  Liaisons1    Liaison2     Liaison2
J  V$( )*7 S( )      R( ,0)        R( ,1)       R( ,2)
01:VERDUN  ppp++++++  9.169023000 19.06451040o  0.
02:REIMS   ppp+++     1.120911299  8.097213100  0.
03:MEAUX   pp+++++    2.096110561 10.04751030o  0.
04:CHALONS pp+++      1.087805869  2.047703724  3.114314500
05:BEAUVAI pp++       0.           0.           0.
06:EVRY    pp++       3.068504922  0.           0.         
07:AMIENS  pp+        5.062205045 18.086211272  0.         
08:COMPIEG p++++++    3.060910500  5.059305300  7.086211272
09:LAON    p+++++     2.074005442  3.106012700  8.074810700
10:PARIS   p++++      5.099512333  6.033703700  8.084711200
11:SEZANNE p+++       3.074711000  4.059804600  6.110011916
12:METZ    p++        1.081005450  0.           0.         
13:CHARLEV +++++++    1.098513100  2.085410300  9.112013300
14:BASTOGN ++++      13.10111060o  0.           0.         
15:FOURMIE ++++       9.072211300 13.06991100o  0.         
16:LUXEMBO ++++       1.092113100 12.06380530o 14.07331050o
17:ST-DIZI ++++       1.076511200  4.062505200 11.09771130o 
18:ST-QUEN ++++       8.074510700  9.074810700 15.06351100o
19:VIRTON  ++++      13.07141100o 14.06180400o 16.05200490o
20:RAMBOUI +++        5.108015500  6.056605500 10.07101040o
21:GIVET   +++       13.05761040o 14.09171040o 15.06451080o
22:NANCY   +++        1.095712900 12.05910490o 17.09921160o 

Je vous laisse en excercice à comprendre comment retrouver la liste des villes et la description des liaisons autour de VERDUN et VIRTON:

Code : Tout sélectionner

|VERDUN:                 |    |VIRTON:                 |
|+REIMS   120.9 1:12 9$90|    |+VERDUN   64.5 1:04     |
|+CHALONS  87.8  :58 6$90|    |+CHARLEV  71.4 1:10     |
|+LAON    169.0 2:30     |    |+BASTOGN  61.8  :40     |
|+METZ     81.0  :54 5$00|    |+LUXEMBO  52.0  :49     |
|+CHARLEV  98.5 1:31     |    |+?_                     |
|+LUXEMBO  92.1 1:31 
|+ST-DIZI  76.5 1:12
|+VIRTON   64.5 1:04
|+NANCY    95.7 1:29
|+?_

La colonne S() contient un code numérique qui dans ce tableau permet d'expliquer l'optimisation de la mémorisation.
Dans le programme, S() est utilisé pour déterminer le "Score" d'une ville ainsi que la ville qui la précède dans l'itinéraire. S= aa.ssssss
Le score d'une ville est déterminé en fonction de ce que l'on cherche à minimiser; distance, durée, coût des péages, coût global ou toute combinaison de ces facteurs.
Ainsi, le "score S" est déterminé par une combinaison linéaire S = A * Km + B * H:mm + C*P$ge

L'algorithme est celui de Dijkstra, il parcourt la carte depuis la ville départ (dans cet m.p.o. c'est LUXEMBO) jusqu'à atteindre la ville arrivée (ie. PARIS) en scrutant à chaque pas la ville présentant le "score" minimal. Initialement, tous les "scores" des villes sont maximum (infini ; 9E99) Seul le score de la ville départ est mit à zéro.

Pour chaque ville scrutée, toutes les liaisons avec les villes environnantes sont examinées afin de déceler si l'une d'entre-elle permettra de "relaxer" un (ou plusieurs) scores des villes voisines. Si c'est le cas, le score des villes "relaxé" est mis à jour ainsi que la liaison vers la ville scrutée (l'ancienne liaison est effacée, elle conduisait à un itinéraire moins performant). les villes qui n'ont pas encore été rencontrées ont un "score" intial infini, qui ne manquera pas d'être modifié si l'on s'en rapproche.

Evidemment, le score est évalué à partir de la ville de départ (comme le stipule l'Algorithme de Dijsktra). Donc, chaque liaison prise en compte "dégrade" les scores au fur et à mesure de l'avancement car il n'y a pas de laision nulle ou négative. Hors on recherche le score minimal !! C'est tout le génie de cette méthode.
.
Par commodité, la colonne S() ne mémorise donc pas directement le "score", mais bel est bien le cumul des kilomètres, temps et péages depuis le départ sous une forme identique à celle des registres cartographiques (j'économise ainsi des lignes de codage et décodage). S(I) = aa.kkkkhmmpp où aa est l'indice de la ville précèdante dans l'itinéraire, kkkk est le cumul hectométrique, h:mm le temps cumulé et pp la somme des péages dûs.

Une fois cette étape réalisée, l'algorithme se poursuit en recherchant la prochaine ville à scruter, son score sera strictement supérieur à celui de la ville en cours et minimal. En effet, toutes les liaisons sont strictement positives, elles augmentent donc toutes les cumuls, les "scores" sont donc strictement croissants.

La détermination s'arrête une fois que l'algorithme s'apprête à scruter la ville arrivée (ici PARIS).
Chaque ville n'est scrutée qu'une seule fois, car une fois qu'il est minimal, son score ne peut plus diminuer.
Toutes les villes ne sont pas nécessairement scrutées, la détermination pouvant arriver à destination sans être passée par les villes dont le "score" n'a jamais était minimal.


Plusieurs versions sont en développement conjointement, ce qui me ralenti. En effet, je n'ai pas décidé si le format le plus adapté (pour obtenir un code MPO) est d'utiliser xx.kkkkhmmpp ou xx.kkkkmmmpp

Dans la version sans mémorisation de la carte, l'utilisateur renseigne les liaisons au fur et à mesure que le Pocket présente les villes scrutées. Pour indiquer que l'on est à destination, il suffit d'indiquer une liaison vers la ville scruté, ce qui met fin à la détermination en affichant les cumuls, statistiques et la liste des villes de l'itinéraire.

Dans la version avec mémorisation de la cartographie, l'utilisateur peut lancer une détermination automatique basée sur ce qui est mémorisé, ou détermination pas à pas afin d'éventuellement ajouter d'autres villes, liaisons ou indiquer une arrivée autre que celle préalablement indiquée.

[jxano]

Il manquait dans mon développement la façon d'exploiter les résultats du parcours en largeur.

L'algorithme de C.Ret s'arrête quand Paris est atteint, le mien s'arrête "faute de munitions", quand tous les sommets ont été visités et ses voisins contrôlés, ce sont ces contrôles qui permettent de déterminer les minima. On peut alors choisir la ville d'arrivée. Par exemple, pour aller à Rambouillet depuis Luxembourg, pour gagner 5 euros, il faut rallonger le voyage d'une heure trois-quarts !

On n'est pas forcé de commencer à Luxembourg non plus ; en ajoutant un INPUT en ligne 40, on lancerait l'algorithme depuis n'importe quel sommet.

Code : Tout sélectionner

60 INPUT"VILLE";V:X=INT(S(V,2)/60):Y=S(V,2)-60*X-.1:S(V,3)=INT(S(V,3)*100+.5)/100:I=V
61 PRINT"TEMPS MINIMAL:";X;"H";Y;", COUT:";S(V,3);",";S(V,4);"KM"
62 IF I=-1;GOTO 70
65 PRINT N$(I)," ";:I=S(I,5):GOTO 62
70 S(V,7)=INT(S(V,7)*100+.5)/100:X=INT(S(V,6)/60):Y=S(V,6)-X*60:I=V
71 PRINT"":PRINT"COUT MINIMAL :";S(V,7);"EN";X;"MIN,";S(V,8);"KM"
72 IF I=-1;GOTO 80
75 PRINT N$(I)," ";:I=S(I,9):GOTO 72
80 S(V,11)=INT(S(V,11)*100+.5)/100:X=INT(S(V,10)/60):Y=S(V,10)-X*60:I=V
81 PRINT"":PRINT"DIST MINI :";S(V,12);"KM EN";X;"H";Y;"MIN,";S(V,11);"EUR"
82 IF I=-1;GOTO 90
85 PRINT N$(I)," ";:I=S(I,13):GOTO 82
90 PRINT"":END

Les villes sont affichées dans l'ordre inverse, c'est dû au fait que chaque sommet "ne connaît" que ses précédents directs pour chaque priorité.

Pour la priorité de distance (que j'ai ajouté depuis mon message de samedi), mon algorithme donne un troisième itinéraire : Paris - Meaux - Châlons-en-Champagne - Verdun - Luxembourg, pour une distance minimale de 341,7 km, un coût de 26,94 euros et une durée de 5 h 17 min.