J'essaie de déterminer la stratégie de recherche optimale pour le problème indiqué ci-dessous.Stratégie de recherche optimale
Je dois rechercher un raster afin de localiser un objet avec une position inconnue.
Je suppose que la route optimale pour rechercher cet objet peut être résolue en utilisant TSP, s'il n'y a pas d'autres informations sur l'emplacement des objets. Dans ce cas, la probabilité de l'objet beeing dans une certaine grille est de 1/# numberOfGrids (figure 1) Uniform location distribution
Contrairement à ce « simple » mise Je suppose maintenant que nous avons des connaissances sur la probabilité de l'objet beeing dans une certaine grille (figure 2). À partir de n'importe quel point de ce raster, le processus de recherche s'arrête dès que l'objet est trouvé ou après que toutes les grilles ont été recherchées. Est-ce que quelqu'un connaît un algorithme pour résoudre de tels problèmes?
Merci pour votre réponse. Si je peux aller à n'importe quel point de trame à un coût constant, votre approche fonctionnera. Mais le coût (temps) de raster à raster n'est pas constant. En fait, il est directement proportionnel à la distance. Nous devons rechercher un objet dans la zone représentée sur la figure. Marcher du bord inférieur gauche au bord supérieur droit sans vérifier aucun raster entre les deux ne sera donc pas optimal, même si ces deux rasters ont la probabilité la plus élevée. – Niko
@Niko: Alors cela devient plus comme un problème de voyageur de commerce, et je chercherais une sorte d'approche heuristique. Par exemple, si la fonction de probabilité a un seul pic, il est évident de commencer par là, et de poursuivre vers l'extérieur par couches de probabilité descendante. S'il y a plus d'un pic, je considérerais descendre de l'un jusqu'à arriver au voisinage d'un autre, puis faire la même chose à partir de ce pic, et ainsi de suite. –
Merci encore Mike. Je parlais de ce problème avec un collègue travaillant sur la théorie des graphes et il proposait une approche similaire. Par conséquent, je vais suivre vos conseils et essayer une approche heuristique. Je pensais que "le chemin de recherche optimal" est une sorte de problème standard avec les algorithmes existants que je ne connais pas. Mais évidemment ce n'est pas aussi simple que ça :) – Niko