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.