#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
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
