Version imprimable
Bonjour à tous,
Je suis complètement novice dans l'élaboration d'algorithme. J'aimerais déterminer en fonction d'un nombre d'objet et de la surface d'un sol, obtenir un algorithme qui me permettrait d'obtenir toutes les conformations possibles dans lesquelles les objets serait éloignés au maximum les uns des autres tout en gardant une ambiguïté sur le chemin le plus court pour visiter tous les objets l'un après l'autre.
Merci d'avance pour vos réponse.
Bonjour,
Challenge difficile !
Juste pour fixer les idées,
- On est dans une surface rectangulaire ?
- On parle de combien d'objets, quel ordre de grandeur ?
- L'objectif est que les objets soit éloignés au max les uns des autres, ça paraît clair. Mais pourquoi parles-tu d'ambiguité ? Est-ce que ce mot est important ?
En effet la surface est rectangulaire et il y a 6 objets. J'aimerais obtenir un algorithme qui me permet d'avoir une conformation dans laquelle les objets sont éloignés au maximum les uns des autres, et l'ambiguïté est importante dans le sens ou j'aimerais qu'il n'y ai qu'une seule possibilité de trajet le plus court pour visiter chaque objet l'un après l'autre, mais que les autres possibilités de trajet diffèrent peu en terme de distance de ce trajet le plus court. Je ne sais pas si je suis très claire.
J'apporte des informations supplémentaire :
J'ai en fait 7 objets (je n'avais pas compté l'objet de départ), mon objet de départ est carré, fait 40cm*40cm. j'ai ensuite 6 autres objets rond de 6cm de diamètre. Et mon sol a une surface de 491cm*683cm.
il faut définir ce que tu appèles les objets éloignés les un des autres.
s'agit il de la somme des distance de chaque objet à l'autre?
s'agit il de la somme des distance de chaque objet au barycentre?
s'agit il de la somme des distance prises objet à objet le plus proche?
de manière générale, avoir le plus court chemin c'est contraire à éloigner les objets les uns des autres...
Je pense que j'intègre trop de paramètre. je pense qu'il faut que je commence avec plus simple. est ce que quelqu'un peut m'expliquer comment générer toutes les conformations possibles de mes 7 objets sur mon sol?
ton problème réfère à du 2d bin packing,
ce qui te permettra de placer tes objets de facon à ce qu'ils se chevauchent pas...
Après tu peux les faire bouger (en gérant les collisions par exemple) de façon à les écarter mais ca dépend de :
1 - comment l'algo a placé initialement tes objets
2 - comment tu définis l'éloignement entre tes objets
Bonsoir,
Quelques remarques suite à tes derniers messages :
- Les dimensions des objets n'ont aucune importance... il FAUT considérer que ce sont des points, ou des objets de 1mm x 1mm
- Recenser tous les emplacements possibles et imaginables est une étape inutile et excessivement coûteuse.
Essayons de le faire juste pour montrer l'inutilité de la démarche.
Je vais simplifier en prenant un quadrillage de ma pièce, je considère que la pièce est un damier, chaque carreau étant un carré de 6x6cm ( la taille de tes objets)
On a donc en gros un damier de 42 x 114 cases, soit 4788 cases.
Le nombre de façons de poser 7 objets sur 4788 cases, c'est environ 11395746842708900000000 possibilités ( 22 chiffres)
Clairement, tu ne vas pas explorer toutes ces possibilités.
Il y a tout un tas de combinaisons qui visiblement n'offrent aucun intérêt.
De façon évidente, on peut déjà mettre un objet à chaque coin de la pièce, puisqu'on veut maximiser le trajet le plus court.
Pour moi, on est dans le cadre 'algorithme du gradient'.
Je le formule avec mes mots :
Tu disposes les 7 objets au hasard dans la pièce.
Tu recherches le plus court chemin.
Tu prends l'objet n°1.
Tu analyses les 5 scénarios suivant : Que se passe-t-il si je déplace l'objet de 1 cm vers la droite, ou vers le haut ou vers le bas ou vers la gauche, ou si je ne bouge pas l'objet.
Et parmi ces 5 scénarios, tu gardes celui qui augmente le plus le trajet le plus court.
Puis même recherche, mais avec l'objet n°2, puis idem l'objet n°3 ... et ainsi de suite pour chaque objet.
Et indéfiniment, en prenant les 7 objets à tour de rôle.
Quand tu as fait 7 essais consécutifs, et que aucun de ces essais ne faisait augmenter notre longueur de trajet, c'est que tu as atteint un optimum.
Forcément, ce moment va arriver, mais il faudra peut être 50000 ou 100000 mouvements avant d'y arriver.
Problème possible : Cet algorithme t'amène à un optimum, mais c'est peut-être un optimum local.
Il faut donc faire tourner cet algorithme plusieurs fois, avec des situations de départ prises à chaque fois au hasard. Et si à chaque essai, on arrive à la même position, c'est très probablement parce que cette position est la meilleure.
j'ai du coup reconsidéré mes ambitions de départ. j'ai trouvé une fonction R qui permet d'obtenir 7 points aléatoires en fonction de ma surface rectangulaire définit au départ. Cette fonction me permet aussi d'obtenir les coordonnées x et y de chaque point, grâce a cela j'ai donc pu définir la longueur de chaque segment possible. Soit pour les objet A,B,C,D,E,F et G.(je code sous R)
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
Tout d'abord je pense que cette longue suite de calcul est simplifiable par une boucle, si quelqu'un a une astuce.
Ensuite j'aimerais savoir si quelqu'un pourrait m'aider à structurer une boucle permettant de calculer la distance de tous les trajets possibles en considérant le point A comme le point de départ et le point d'arrivée. En sachant qu'on ne doit passer qu'une seule fois par les autres points au cours d'un trajet.
ton problème est alors le classique tsp (travel salesman problem/ voyageur du commerce) qui est plutot assez documenté sur le net