Bonjour; Je travaille sur un projet de cartographie.
Je doit cartographier un territoire jusqu'a trouver un objet.
Le but est de trouver un objet très petit dans une surface très grande.
Je me doute qu'une solution serait de parcourir le territoire point par point mais je cherche une autre solution.
En effet, je dispose d'un outils d'exploration qui me permet de cibler une zone et explorer cette zone par point aléatoire.
Je m'explique, j'ai un "Moteur de recherche" qui place 5 sondes dans un rayon de 10 kilomètres dans une zone ciblé et restreinte. Ces sondes sont sensible au kilomètre on va dire. Si l'objet est détecter dans la zone, le jeu est gagné, si non, il faut explorer une autre zone. Voir ré-explorer la zone courante.
Je souhaiterais savoir vers quelles techniques je devrais m'orienter, si vous pouviez m'aider encore. Merci.

Regarde du côté des algos de biomimétique : ceux basés sur fourmis, principalement

Et bien merci encore rufo.    
 
Vu comme ça, ça n'a pas l'air bien compliqué.

procedure ACO_MetaHeuristic
    while(not_termination)
       generateSolutions()
       daemonActions()
       pheromoneUpdate()
    end while
  end procedure

 
Faut faire un graphe gradué ?  
Je pige rien au tuto de développez...  
Ca viendra.

Un graphe valué ou orienté peut être une solution aussi. Dans ce cas, un algo de type Voyageur du commerce pourrait convenir.

Ah oui, merci rufo, c'est "valué" les graphes.
 
Pour la solution, j'en sais rien, je demande.
La colonie de fourmis c'est pas justement une solution au problème du Voyageur de commerce ?
C'est ce qu'il ont l'air de dire chez developpez.

 
Pas du tout, les fourmis sont utilisées pour résoudre pleins de pbs, par ex le plus cours chemin. Mon prof de biomimétique m'avait même parlé, quand j'étais en école d'ingé, que Motorola (il me semble que c'est cette boîte) avait utilisé un algo à base de fourmis pour calibrer un laser.
 
http://fr.wikipedia.org/wiki/Algor [...] de_fourmis

Non, ça j'avais compris. Masi tu dis qu'un algorithme de type Voyageur du commerce serais une solution, c'est plutôt un problème, ... Résolut entre autre peut-être (voir les génétique) par les colonies de fourmis, non ?
Désolé pour l'embrouille.
 
J'ai trouvé un pseudo code pour le Voyageur de commerce.:
 

 
A la place des villes je vais mettre des "surface d'exploration" ...
A la place des fourmis je vais mettre des "sondes-à-phéromones"...
Mais encore...
je place mes quelques sondes aléatoirement dans une zone pour explorer les surfaces alentours.
Apparemment pour représenter la colonie de fourmis j'ai juste besoin de modéliser les chemins emprunté par une table de phéromone.  
 
J'ai vue un article titré sur l'optimisation continue... Ca compte si je dois effectuer cette recherche une nombre de fois indéterminé ?

 
Le pb du VDC a une "vraie" solution via un algo basé sur un graphe orienté. Un VDC peut se résoudre avec une colonie de fourmis mais ça sera une solution de type "heuristique".

Merci rufo.  
 
J'ai eu un peu de mal à comprendre "VDC".
 
Merci encore.    

Up, bonjour,
 
Je voudrait (finalement) implémenter cet algo, mais je ne sais comment adapter l'exemple sur le voyageur du commerce à mon problème. Déjà que je comprend à peine l'exemple...
 
Si vous avez du temps, serait il possible d'avoir votre aide ?   S'il vous plaît.

VDC : http://fr.wikipedia.org/wiki/Probl [...] e_commerce
 
Solution exacte à base d'optimisation linéaire, comme l'algo du simplex. Mais c'est vrai que c'est pas évident à mettre en oeuvre.
 
Pour ton pb, je pense qu'un algo à base de fournis serait le plus simple à implémenter et donnerait de bons résultats.
 
Après, ton histoire de sondes qui ont une certaine portée et à positionner à différents endroit pour trouver l'objet me fait penser que ton pb pour se rapporter à la question : comment couvrir (découvrir) un maximum de terrain en un minimum de changements de positions des sondes, le critère d'arrêt étant, l'une des sonde a trouvé l'objet.
 
Dans ce cas, un algo reposant sur les diagrammes de Voronoï pourrait être pas mal... http://fr.wikipedia.org/wiki/Diagramme_de_Vorono%C3%AF
Le seul truc, c'est qu'il semble que les diagrames de Vornoï, ce sont des cellules polygonales alors que tes sondes ont un rayonnement circulaire...
 
J'ai trouvé aussi ce cours : http://w3.bretagne.ens-cachan.fr/D [...] 6_algo.pdf

Merci rufo,  
 
Mes sondes ont un rayonnement carré, par contre elle ne serve qu'une seule fois.
Aussi, comme mes sondes sont en réalité des missiles, je dois pourvoir exclure la position du missile des cibles potentielle. Si non, il s'auto détruit ; Ce qui n'a aucun intérêt.
Quant à la terminaison de la recherche, c'est à l'utilisateur d'en décider, si non elle est continue.

Bonsoir,
 
Pourriez vous si vous savez me dire comment je peut déterminer Alpha dans l'ago de résolution du VDC ci-dessus ?
Sources : http://labo.algo.free.fr/pvc/algor [...] urmis.html
 
Et aussi, dans la définition de "Lmv la longueur du trajet calculé par la méthode du meilleur voisin ou une approximation"
C'est entre i et j pour toutes les paires de villes ?
 
Merci.

Bonjour,
 
Je reviens sur mon exploration de territoire.
 
Je cherche un lieu sur le globe. Je cherche plusieurs algo à implémenter, si je peux en implémenter au moins deux.
Donc ok grosso modo pour le VDC vous en auriez d'autre qui iraient bien ?
C'est pour un jeu.

Comme indiqué dans mes précédents post : algo génétique à base de fourmis (+phéromone) par ex.
 
Après, y'a tous les algos de plus court chemin...

Ok, je vais essayer de l'implémenter.

Ca c'est A* par exemple, je vais me régaler de le ré- écrire.

A* ou plus classique Dikjtra, ou Floyd...

Ok, merci rufo, je regarderai.