Discussion :

[Globoxx]

Bonsoir,

Je travaille sur un script qui simule la colonisation spatiale. Pour chaque planète colonisée, mon algorithme recherche ses 2 voisines les plus proches et les colonise, etc... Voici un schéma pour éclairer mes explications :


Mon problème, c'est : comment calculer tous les itinéraires ? Je calcule déjà toutes les normes séparant chaque planète mais par exemple, à l'étape N, j'aurai 2^N itinéraires différents. J'aimerais pouvoir ranger tous ces itinéraires dans une matrice mais je ne sais pas comment m'y prendre...

Voici mon algorithme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
        Vector = bsxfun(@minus,P(:,1:3),Origine);
        Normes = sqrt(sum(Vector.^2, 2));
 
        [best_ways(1),idx(1)] = min(Normes);
        Normes(idx(1)) = inf;
        [best_ways(2),idx(2)] = min(Normes);
 
        P(idx(1),4) = 1;
        P(idx(2),4) = 1;
 
        planete_visitee(1,:) = P(idx(1),:);
        planete_visitee(2,:) = P(idx(2),:);
        P(idx(1),:) = P(1,:);
        P(idx(2),:) = P(2,:);
        P(1,:) = planete_visitee(1,:);
        P(2,:) = planete_visitee(2,:);
 
        Planetes_visitees = [P(1,:);P(2,:)];
 
        if all(Planetes_visitees(1,1:3)) == all(Terre(1,1:3)) || all(Planetes_visitees(2,1:3)) == all(Terre(1,1:3))
            Terre_trouvee = true;
        end
 
 
        exposant = zeros(1,100);
        exposant(1) = 2;
 
        for i = 2:length(exposant)
        	exposant(i) = exposant(i-1)*2;
        end
 
        j = 1;
        k = 3;
        l = 1;
        while Terre_trouvee == false
 
            for i = 1:exposant(j)
                Vector = zeros(Indices(N),3);
 
                Vector(k:end,1) = P(exposant(j)+(k - exposant(j)):end,1) - P(l,1);
                Vector(k:end,2) = P(exposant(j)+(k - exposant(j)):end,2) - P(l,2);
                Vector(k:end,3) = P(exposant(j)+(k - exposant(j)):end,3) - P(l,3);
 
                Normes = sqrt(sum(Vector.^2, 2));
 
                [best_ways(1),idx(1)] = min(Normes(k:end));
                idx(1) = idx(1) + (k-1);
                Normes(idx(1)) = inf;
                [best_ways(2),idx(2)] = min(Normes(k:end));
                idx(2) = idx(2) + (k-1);
 
                P(idx(1),4) = 1;
                P(idx(2),4) = 1;
 
                planete_visitee(1,:) = P(idx(1),:);
                planete_visitee(2,:) = P(idx(2),:);
                P(idx(1),:) = P(k,:);
                P(idx(2),:) = P(k+1,:);
                P(k,:) = planete_visitee(1,:);
                P(k+1,:) = planete_visitee(2,:);
 
                Planetes_visitees = [Planetes_visitees;P(k,:);P(k+1,:)];
 
                if all(P(k,1:3)) == all(Terre(1,1:3)) || all(P(k+1,1:3)) == all(Terre(1,1:3))
                    Terre_trouvee = true;
                    break;
                end
 
                k = k+2;
                l = l+1;
            end
 
        j = j+1;
        end

Aide bienvenue !
Merci d'avance !

[DonQuiche]

Bonjour.

La bonne réponse est tout simplement qu'il ne faut pas chercher à calculer ou stocker cette masse exponentiellement croissante de trajectoires. La bonne question est donc : que cherches-tu à faire et comment le faire sans calculer l'ensemble des trajectoires ?

[Globoxx]

Oui en fait, à un moment donné, la Terre sera trouvée par mon algorithme. Et là je dois retracer le bon chemin, celui parcouru depuis la planète d'origine jusqu'à la Terre et calculer la longueur de ce chemin.

[DonQuiche]

Puisque tu fais un balayage le mieux est de stocker pour chaque planète l'identité d'une de ses prédécesseures, par exemple la première par laquelle elle a été ajoutée. Une fois le balayage fini tu reviendras en arrière, cela te donnera un des chemins possibles.

Si en revanche tu veux le plus court chemin, tu peux t'en approcher en choisissant à chaque étape la prédecesseure qui minimise la distance D(0 à N) + D(N à N+1). Pour ce faire il faudra stocker non seulement la prédecesseure mais en plus la distance du point de départ. C'est une optimisation locale et ça devrait donner un bon résultat pour ton problème.

Et si tu veux faire plus élaboré je t'invite à te renseigner sur les algorithmes de recherche du plus court chemin.

[Globoxx]

Merci beaucoup, je vais faire des tests avec ta proposition.

Edit : Cela fonctionne bien avec ta méthode de balayage. En fait chaque planète n'a qu'une seule prédécesseure. Merci en tout cas