bon, j'ai pas pris baucoup de temps à réflaichir sur le problème mais deux algo me vient à l'esprit:
- 1- une recherche sequenciel avec utilisation d'une liste tabou
2- un algorithme sequenciel en considerant la recherche sur une surface soit d'une boule ou d'un cube (la deuxième etant meilleur)
Explication des deux Algo
1- Recherche sequenciel avec utilisation d'une liste tabou:
On commence par la definition de la definition des classes suivantes (déclaré avec un pseudo langage, que je vien d'inventer pour l'occasion)
1
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
| type
// definition d'un point dans un espace 3D discret
T3DPoint=Classe
T3DPoint(unX, unY, unZ); // un constructeur de point 3D
X:Int
Y:Int
Z:Int
fin;
// definition d'une collection de points
T3DPoints=Classe
// Interface pour indexer les elements de la collection
fonction Count:Int; // le nombre de points dans la collection
fonction GetPoint(Index:Integer):T3DPoint;
function IndexOf(Point:T3DPoint):bool;
// un interface pour visiter la collection
procédure First; // aller au debut de la liste
fonction CurrentPoint:T3DPoint; // le point courant
procedure Next; // aller au point suivant
fonction EndOfCollection:bool; // indique si on a atteint la fin de la liste
// Interface pour manipuler le contenu de la collection
fonction Add(Point:T3DPoint):int;
fonction Remove(Point:T3DPoint):int;
procedure Clear;
procedure fusion(Points:T3DPoints); // pour integrer les elements de Points
fin; |
les classes de base etant declarée je passe à l'explication de l'algo.
on dispose de deux collections
CurrentPath, Tabou :T3DPoints
CurrentPath contient la liste des points à vister et Tabou contient l liste des points déja visités. on aurra aussi besoint d'une fonction donnant le voisinage d'un point; c'est à dire les 26 points entourant le point;
1
2
3
4
| fonction NeighborOf(point:T3DPoint):T3DPoints;
debut
// créer une CollectionResultat contenant les 26 points voisins
fin |
on commence à partir d'un point donné, si la nuance à été trouvé c'est bon (return point) sinon on prend la liste des points voisins et on l'ajoute à la collection CurrentPath, et le point visté est ajoute à la collection Tabou (Tabou joue le rôle d'une liste noire, les points qu'elle contient sont interdits de visite).
l'algo de recherche etant
1
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
| les variablesglobales
CurrentPath, Tabou de type T3DPoints
...
fonction FindNearest(Point:T3DPoint):T3DPoint
les variables locales
CurrentP de type T3DPoint
Sortie, Trouve de type bool
...
debut
CurrentPath.Clear;
CurrentPath.Add(Point)
CurrentPath.First;
Tanque (non Sortie) faire
CurrentP = CurrentPath.CurrentPoint
CurrentPath.Remove(CurrentP)
si Tabou.IndexOf(CurrentP) != -1 alors // si le point n'est pas interdit de visite
// on teste si le point en cours correspond à la nuance recherché
si GoodNuance(CurrentP) then
Trouve = vrai
sinon
Trouve = Faux
CurrentPath.Fusion(NeighborOf(CurrentP))
Fsi
FSI
Sortie = (CurrentPath.Count==0) ou (Trouve == vrai)
Ftanque
si Trouve alors
return CurrentP
sinon
return null
fsi
fin |
2- Recherche sur les surfaces de cubes englobants:
l'algo consiste à démarrer d'un point et de grossir le champ de recherche, j'usqu'à trouver le point; le champ de recherche n'est autre qu'une surface de cube de rayon R.
On utilise les deux classes T3DPoint, T3DPoints déclarées précédemment et une nouvelle fonction qui donne les points de la surface du cube de rayon R, centré sur un point P
1
2
3
4
5
6
7
8
9
10
11
12
13
| fonction PointsOfCube(Point:T3DPoint; Rayon:int):T3DPoints
les variables
i,j,k de type int
CubResultat de Type T3DPoints
DEBUT
POUR i allant de Point.X-Rayon jusqu'à Point.X+Rayon FAIRE
POUR j allant de Point.Y-Rayon jusqu'à Point.Y+Rayon FAIRE
POUR k allant de Point.Z-Rayon jusqu'à Point.Z+Rayon FAIRE
CubResultat.Add(new T3DPoint(i,j,k)) // ajouter le point
FPOUR
FPOUR
FPOUR
FIN |
a chaque fois on crée un champs de recherche un peu plus grand et qui entour l'ancien champ de recherche.
1
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
|
fonction FindNearest2(Point:T3DPoint):T3DPoint
les variables locales
CurrentPath de type T3DPoints // on a plus besoin de la liste Tabou
CurrentP de type T3DPoint
Sortie, Trouve de type bool
Ray de type int
...
debut
trouve
Ray = 0
Tanque (non Sortie) faire
CurrentPath := PointsOfCube(Point, Ray)
CurrentPath.First;
Tanque ((non trouve) et (non CurrentPath.EndOfCollection)) faire
CurrentP=CurrentPath.CurrentPoint
si CurrentP est la bonne nuance alors
trouve = vrai
sinon
trouve = faux
CurrentPath.Next
fsi
FTanque
Sortie := trouve ou (un teste pour eviter une explosion de memoire)
Ray++
FTanque
SI Trouve ALORS
return CurrentP
SINON
return null
FSI
fin |
ce deuxieme algo est plus efficace que le premier, mais si cela ne te suffis pas (j'en suis sure) alors cherche du coté des heuristiques, les algos de type A* (ou Branch and Bound en RO) se prêtent bien a ce genre de prob
===============================================
excuse moi pour ce pseudo code, c'est un melange d'algo de pascal et de C++. pour A* t'as le vieux google. et bonne prog
Algo de recherche dans un cube de couleur
Répondre avec citation
).
Partager