Trouver le chemin le plus rapide possible

Question

J'ai un objet avec la largeur w et la hauteur h. L'objet doit trouver le chemin le plus rapide possible pour couvrir toute la zone en un minimum de temps. Pensez-y comme un bras robotisé qui a besoin de pulvériser un produit chimique sur toute la surface. Les régions noires sont des zones qui ne peuvent pas être traversées.

Dans l'image ci-dessus, le poids de l'objet h se déplace à travers une zone (la zone gris foncé sous-jacente est la zone qui a déjà été couvert). Je dois élaborer un algorithme qui détermine le chemin le plus rapide possible pour couvrir toute la zone si l'objet se déplace à une vitesse v et prend t secondes pour faire un tour de 90 degrés (ou t/90 pour chaque tour de 1 degré). L'objet peut se déplacer en dehors de la zone désignée.

L'objectif devrait être de minimiser le nombre de tours et de maximiser le mouvement linéaire. En supposant que j'ai toutes les mesures pour tout, comment pourrais-je commencer à programmer quelque chose qui puisse déterminer ce chemin?

Answer 1

[édité la réponse] Je suis désolé j'avais tort.

Pour moi, la meilleure solution serait un algorithme qui ressemble à ceci:

1. what is the smallest rectangle that covers the all area 
2. compute the time to 'paint it' from your starting position: 
    2.1 as you can go outside, just 
     2.1.1 calculate time if browsing by rows 
     2.1.2 if by column 
     2.1.3 if turning from outer to center 
     2.1.4 if turning from outer to center 
    2.2 decide what is the most efficient solution 
3. store this result 
4. subdivise the area in 2 smaller rectangles 
5. redo the same thing for the 2 and test various combination for the travel from rectangle 1 to 2 (obviously the starting pos on 2 is free) Always keep track that anything bigger than the cost of the first solution can be ignored 

Si je pouvais donner une estimation simple, ce n'est pas mathématiquement le plus rapide, mais une bonne solution est ce que la plupart AOI faire , fais juste le plus grand rectangle. Le problème dépend mathématiquement de beaucoup de variables, si t est important (souvent vrai pour les robots) alors la solution simple est probablement proche de la solution comme la solution avec le minimum de virage.

Déjà trouver la meilleure solution pour un rectangle est bon. alors est est une question de graphique (un graphique de rectangles, les connexions entre les graphiques sont un autre problème)

désolé je ne peux pas aider plus.