banniere

Le portail francophone de la géomatique


Toujours pas inscrit ? Mot de passe oublié ?
Nom d'utilisateur    Mot de passe              Toujours pas inscrit ?   Mot de passe oublié ?

#1 Wed 10 April 2013 23:37

samdebest
Juste Inscrit !
Date d'inscription: 10 Apr 2013
Messages: 1

Chemin le moins couteux (least cost path)

Bonjour,
Je suis un débutant en programmation et dans mon cours je dois effectuer la programmation en python pour trouver le chemin le moins couteux à partir de données matricielles. J'essais d'abord de trouver le script au plus simple. J'ai ma matrice des coût et j'essais de trouver ma matrice distance coût. Je sais aussi, par exemple la cellule adjacente se calcul ainsi: moitié de la grandeur de la cellule X le cout de la cellule + la moitié de la grandeur de la cellule adjacente X le coût. Le problème est comment programmer ceci pour que ca fonctionne à la grandeur de mon tableau considèrent aussi que le chemin diagonale ce peut aussi, c-a-d (la moitié de la diagonale de la cellule dans le calcul).

Merci de bien vouloir m'aider un peu ou du moins m'éclairer.   
P.S. Avec des recherches j'ai vu qu'il faudrait utiliser une méthode en "arbre" avec l'algorithme A*, mais alors la je trouves cela très complexe avec mon niveau de programmation.

Sam

Hors ligne

 

#2 Thu 11 April 2013 09:43

MathieuR
Membre
Lieu: aix-en-provence
Date d'inscription: 16 Feb 2009
Messages: 1690
Site web

Re: Chemin le moins couteux (least cost path)

il existe déjà des modules permettant de réaliser cela. par exemple, sous QGIS/GRASS, le module r.cost


geodata au cerema et petits billets en géomatique

Hors ligne

 

#3 Fri 12 April 2013 12:28

Damien BEAUSEIGNEUR
Participant assidu
Lieu: meyzieu
Date d'inscription: 5 Sep 2005
Messages: 425

Re: Chemin le moins couteux (least cost path)

Soyons clair, il s'agit d'un exercice de cours, il faut donc comprendre la méthode de calcul de du chemin le moins couteux.

Donc comment partir du point A pour arriver en point B. avec une quasi... infinité de chemin possible. chaque point amène 8 directions possibles. certain de ces points n'ont jamais été accédé d'autres oui mais avec un cout supérieur ils seront donc remplacé... et d'autres avec un cout supérieur ou égal... donc à ne pas changer.

On progresse de point en point en partant du point de départ, en utilisant le moins cher des points accédés pour prochain point.

algorithme de base à creuser bien sur.

cordialement

Hors ligne

 

Pied de page des forums

Powered by FluxBB