Discussion :

[mounak1991]

J'ai un jeu d'echecs a ma disposition, je veux aller de la case [1,1] jusqua la case [n,n]. Ma matrice est de taille [n,n]. Je nai la possibilite que de me deplacer horizontalement .et verticalement, le cout de chaque deplacement correspond a la difference entre la valeur absolue de la case actuelle sur laquelle je me situe et la case a partir dne laquelle je me suis deplace. Je veux trouver le chemin minimal pour aller de la case [1,1] jusqua [n,n] la complexite de lalgorithme doit etre polynomiale est ce que quelqun pourrait maider pour trouver une reponse a cette question, jai pense a Prim's mais je ne suis pas sure

[ToTo13]

...
Vu que tu ne peux te déplacer que horizontalement ou verticalement, quel est réellement le problème ?

Il te suffit de limiter tes déplacements aux sens qui augmentent l'ordonnée ou l'abscisse.
Dans ce cas tu ne peux qu'aller vers la case souhaitée et tous les chemins possibles auront le même coût : que tu fasses 1 mouvement de taille N ou N de taille 1, le coût est le même, ce sera 2(N-1).

[gpcbitnik38]

je suppose qu'il y a des pièces qui barre la route de ta tour sinon, comme le dit toto c'est pas très compliqué ^^.

le cout de chaque deplacement correspond a la difference entre la valeur absolue de la case actuelle sur laquelle je me situe et la case a partir dne laquelle je me suis deplace

je ne comprend pas bien, tes cases ou des valeurs ou tu parle simplement de leur position?
avec tes case tu peux construire un graphe orienté
sommet (1,1) est relié à 1,2 et 2,1; 1,2 est relié à 1,3 et 2,2 etc.. si une des cases est occupée elle n'apparait pas dans le graphe ( de meme si elle est inaccéssible, sinon ton graphe ne sera pas orienté)
ensuite tu utilise l'algorithme de Dijkstra (si tes cases on des valeurs tu pondère le poids des arretes par ces valeur)

[ToTo13]

si une des cases est occupée elle n'apparait pas dans le graphe

Rien n'est dit sur d'éventuels obstacles...

[mounak1991]

je peux me deplacer d'une case vers la droite ou d'une case vers le bas a chaque fois, le cout de chaque deplacement correspond a la valuer absolur de la difference entre les energie assignees aux deux cases, chaque case su jeu d'echec a une valeur qui correspond a son energie

[ToTo13]

je peux me deplacer d'une case vers la droite ou d'une case vers le bas a chaque fois, le cout de chaque deplacement correspond a la valuer absolur de la difference entre les energie assignees aux deux cases, chaque case su jeu d'echec a une valeur qui correspond a son energie

Chaque case n'a t-elle pas la même énergie ?

[mounak1991]

chaque case a une energie differente et le cout du deplacement correspond a la difference d'energie de deux cases consecutives (soit ver la droite soit vers le bas )

[gpcbitnik38]

chaque case a une energie differente et le cout du deplacement correspond a la difference d'energie de deux cases consecutives (soit ver la droite soit vers le bas )

En théorie des graphes, l'algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Il s'applique à un graphe connexe dont le poids lié aux arêtes est un réel positif.

source wikipedia

ça me semble particulièrement adapté a ton problème non?
tu construis ton graphe en fonction des règles de déplacement (pas de déplacement vers la gauche ou la droite ). Le poids de tes arêtes est la différence d'énergie entre tes 2 cases.
tu trouvera ainsi le chemin le plus court a coup sur.

[mounak1991]

oui mais dans mon case je suis seulement interessee par la distance de la case [1,1] a la case [8,8] alors que dijkstra donne la distance de la case [1,1] vers toutes les cases, donc je pense que Dijkstra est inapproprie il me donne la plus courte distance dune case a toutes les autres cases alors que je ne suis interessee que pas la distance de la premiere case vers la derniere case

[gpcbitnik38]

du coup j'ai pas du bien comprendre ton problème.


peut tu me dire sur cet exemple quel est le résultat que tu recherches

[mounak1991]

dans ce cas je peux construire un graphe dans lequel chaque edge entre deux nodes corresponds aux valeurs absolues des differences entre les nombre assignes a chaque graphe, je designe la premiere node a agauche en haut comme etant la source du graphe et je construis des edges de maniere a ce que chaque edge corresponde a la valeur absolue de la differences des valeurs assignees a chauqe node, ma source est la node 1, 1 et je veux me deplacer vers la node 3,3 je ne peux effectuer que des deplacement horzontaux et verticaux, je ne veux que la distance entre la node 1,1 et la node 3,3

excusez moi je ne connais pas les termes en francais pour node et edge donc jai utilise les terms en anglais, vous avez probablement compris de quoi je parlais merci

[Jedai]

oui mais dans mon case je suis seulement interessee par la distance de la case [1,1] a la case [8,8] alors que dijkstra donne la distance de la case [1,1] vers toutes les cases, donc je pense que Dijkstra est inapproprie il me donne la plus courte distance dune case a toutes les autres cases alors que je ne suis interessee que pas la distance de la premiere case vers la derniere case

Tu es obligé de calculer ces autres distances pour être certain d'avoir trouvé le bon chemin de toute façon, que ta fonction renvoie toutes ces distances ou simplement celle qui t'intéresse à la fin est un choix que tu feras. Donc oui, Dijkstra est adapté. Il y a des alternatives mais aucune qui te permette de calculer uniquement la distance entre ta case de départ et celle d'arrivée sans calculer au moins certaines des autres (les intermédiaires potentielles), si tu y réfléchis, tu comprendra pourquoi...

Une fois que tu as implémenté Dijkstra, tu peux essayer A* pour améliorer légèrement les choses si tes coûts ne sont pas trop différents.

--
Jedaï

[ToTo13]

Tu peux faire un Dijkstra "limité".
Vu que tu n'as que deux direction de déplacement, tu sais que tu ne reviendras pas en arrière, donc tu peux limiter ton Dijkstra au rectangle [[1,1],[N,N]].

[mounak1991]

ah bon? je croyais que dijkstra etait oblige de calculer la distance a partir de la source vers toutes les autres cases intermediares pour pouvoir donner une reponse pour la destination qui nous interesse comment serait ce possible de limiter dijkstra au niveau de lalgorithme, devrais je modifier lalgorithme standard de Dijkstra? et quelle serait la complexite en terme de temps dans ce cas ? Merci

[Jedai]

Tu peux faire un Dijkstra "limité".
Vu que tu n'as que deux direction de déplacement, tu sais que tu ne reviendras pas en arrière, donc tu peux limiter ton Dijkstra au rectangle [[1,1],[N,N]].

Apparemment dans son cas [N,N] est la case au coin opposé de [1,1] alors ça ne va pas aider beaucoup...

ah bon? je croyais que dijkstra etait oblige de calculer la distance a partir de la source vers toutes les autres cases intermediares pour pouvoir donner une reponse pour la destination qui nous interesse comment serait ce possible de limiter dijkstra au niveau de lalgorithme, devrais je modifier lalgorithme standard de Dijkstra? et quelle serait la complexite en terme de temps dans ce cas ? Merci

Basiquement ce que Toto te dit, c'est que si tu as une matrice 10x10 et que tu dois aller de la case [1,1] à la case [3,5] par exemple, tu peux faire Dijkstra sur la sous-matrice 3x5 et avoir la garantie d'avoir la bonne réponse mais ça ne marche pas en fait, pas avec ton système de poids différents, il suffit de considérer la matrice suivante pour s'en convaincre :
01 10 20 30
01 20 05 30
05 05 05 05

Pour aller de la case (1,1) à la case (2,3), l'optimum est de sortir du rectangle en passant par (2,1) -> (3,1) -> (3,2) -> (3,3) -> (2,3) (coût 4).

excusez moi je ne connais pas les termes en francais pour node et edge donc jai utilise les terms en anglais

En français, on parle des sommets et des arêtes d'un graphe.

[mounak1991]

Je commence a avoir les idées plus claires Merci!!! les cases ne doivent pas forcement être distinctes! Donc, si je ne me trompe pas l'algorithme que vous avez propose consiste a repérer les cases dont les poids sont égaux et ensuite essayer de trouver une différence de valeur absolue minimale entre deux cases consécutives? Est ce que vous pourriez formuler une définition de cet algorithme en termes d'étapes qui doivent être suivies pour trouver le chemin avec cout minimal pour atterrir à la case [N,N]? Merci beaucoup

Quelle serait la nouvelle complexité en termes de temps dans cette nouvelle version de Dijkstra limite? et pourquoi Merci beaucoup pour votre aide!

[gpcbitnik38]

Description de l'algorithme

L'algorithme de Dijkstra est un algorithme de type glouton : à chaque nouvelle étape, on traite un nouveau sommet. Reste à définir le choix du sommet à traiter, et le traitement à lui infliger, bref l'algorithme...

Tout au long du calcul, on va donc maintenir deux ensembles :
•C, l'ensemble des sommets qui restent à visiter ; au départ C=S-{source}
•D, l'ensemble des sommets pour lesquels on connaît déjà leur plus petite distance à la source ; au départ, D={source}.

L'algorithme se termine bien évidemment lorsque C est vide.

Pour chaque sommet s dans D, on conservera dans un tableau distances le poids du plus court chemin jusqu'à la source, et dans un tableau parcours le sommet p qui le précède dans un plus court chemin de la source à s. Ainsi, pour retrouver un chemin le plus court, il suffira de remonter de prédécesseur en prédécesseur jusqu'à la source, ce qui pourra se faire grâce à un unique appel récursif (beaucoup moins coûteux que dans le cas de Floyd...).

Initialisation

Au début de l'algorithme, le chemin le plus court connu entre la source et chacun des sommets est le chemin direct, avec une arête de poids infini s'il n'y a pas de liaison entre les deux sommets. On initialise donc le tableau distances par les poids des arêtes reliant la source à chacun des sommets, et le tableau parcours par source pour tous les sommets.

ième étape

On suppose avoir déjà traité i sommets, parcours et distances contiennent respectivement les poids et le prédécesseur des plus courts chemins pour chacun des sommets déjà traités.

Soit s le sommet de C réalisant le minimum de distances[s]. On supprime s de C et on l'ajoute à D. Reste à mettre à jour les tableaux distances et parcours pour les sommets t reliés directement à s par une arête comme suit : si distances[s] + F(s,t) < distances[t], alors on remplace distances[t] par distances[s] + F(s,t) et parcours[t] par s... et c'est tout !

(n-2)ème étape

Au départ, il y a (n-1) sommets à visiter, mais comme on le verra ci-après, la dernière étape est inutile puisqu'elle n'apporte rien. Ainsi, dès la (n-2)ème étape, distances et parcours contiennent toute l'information nécessaire pour trouver des plus courts chemins de la source à chacun des autres sommets (car alors D=S):
•distances[s] est le poids du plus court chemin de la source à s
•parcours[t] est le prédécesseur de s dans un plus court chemin de la source à s

source : http://www.nimbustier.net/publicatio.../djikstra.html