[parfor] Où puis-je l'utiliser correctement dans mon algorithme ?

**Globoxx** · 23/11/2013, 19h40

Bonsoir,

J'ai écris un algorithme qui permet, en gros, de trouver le point le plus proche de chaque point dans l'espace.
Le fait est que cet algorithme est lui-même imbriqué dans 2 boucles for. Au final le temps de calcul se compte en heures.
J'aimerais savoir où je pourrais utiliser [parfor] dans mon code.

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
 
% Algorithme
 
        VectorO = zeros(N,4);
        NormesO = zeros(N,1);
        All_Best_ways = zeros(N,1);
        Point = zeros(N,3);
 
        for i = 1 : N
            VectorO(i,1:3) = P(i,1:3) - Origine(1,1:3);
            NormesO(i) = sqrt((VectorO(i,1))^2+(VectorO(i,2))^2+(VectorO(i,3))^2);
        end
        Emplacement_Best_way = find(NormesO == min(NormesO(:)));
        if length(Emplacement_Best_way) ~= 1 % Si il y a plusieurs plus courts chemins
            Emplacement_Best_way(2:end) = []; % On ne prend que le premier
        end
        Best_way = min(NormesO);
        All_Best_ways(1) = Best_way;
        P(Emplacement_Best_way,4) = 1; % Le système est visité
        Point(1,:) = P(Emplacement_Best_way,1:3);
 
        if Point(1,:) == Terre(1:3) % Si la Terre est atteinte
            Jusqua_Terre = sum(All_Best_ways);
        end
 
        Vector = zeros(N-1,4);
        Normes = zeros(N-1,1);
        for j = 2 : N
            for i = 1 : N
                if i ~= Emplacement_Best_way
                    if P(i,4) == 0
                        Vector(i,1:3) = P(i,1:3) - P(Emplacement_Best_way,1:3);
                        Normes(i) = sqrt((Vector(i,1))^2+(Vector(i,2))^2+(Vector(i,3))^2);
                    else
                        Normes(i) = inf;
                    end
                else
                    Normes(i) = inf;
                end
            end
            Emplacement_Best_way = find(Normes == min(Normes(:)));
            if length(Emplacement_Best_way) ~= 1 % Si il y a plusieurs plus courts chemins
                Emplacement_Best_way(2:end) = []; % On ne prend que le premier
            end
            Best_way = min(Normes);
            All_Best_ways(j) = Best_way;
            P(Emplacement_Best_way,4) = 1; % Le système est visité
            Point(j,:) = P(Emplacement_Best_way,1:3);
 
            if Point(j,:) == Terre(1:3) % Si la Terre est atteinte
                Jusqua_Terre = sum(All_Best_ways);
                break % On arrête l'algorithme
            end
        end

Merci d'avance pour votre aide !

**Jerome Briot** · 25/11/2013, 12h02

Avant d'utiliser parfor, il y a quelques améliorations à apporter à ton code.

Le bloc suivant :

Code :

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

1
2
3
4
5
6
Emplacement_Best_way = find(Normes == min(Normes(:)));
if length(Emplacement_Best_way) ~= 1 % Si il y a plusieurs plus courts chemins
    Emplacement_Best_way(2:end) = []; % On ne prend que le premier
end
Best_way = min(Normes);
All_Best_ways(j) = Best_way;

devrait simplement s'écrire :

Code :

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

[All_Best_ways(j),Emplacement_Best_way] = min(Normes);

As-tu besoin des valeurs stockées dans Vector à la fin de ton code ?

Si ce n'est pas le cas, tu n'as pas besoin de lui attribuer une taille Nx3. Il suffirait de faire comme ceci :

Code :

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

1
2
Vector = P(i,1:3) - P(Emplacement_Best_way,1:3);
Normes(i) = sqrt(Vector(1)^2+Vector(2)^2+Vector(3)^2);

Pourquoi mets tu N-1 éléments dans la ligne suivante :

Code :

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

Normes = zeros(N-1,1);

Ne serait-ce pas plutôt N ?

Ensuite, tu remplis Normes avec des valeurs Inf. Initialise donc ce vecteur avec la fonction inf :

Code :

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

Normes = inf(N-1,1);

Ceci te permettra de simplifier la boucle interne sur i :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
for i = 1 : N
        if i ~= Emplacement_Best_way
            if P(i,4) == 0
                Vector(i,1:3) = P(i,1:3) - P(Emplacement_Best_way,1:3);
                Normes(i) = sqrt((Vector(i,1))^2+(Vector(i,2))^2+(Vector(i,3))^2);
            else
                Normes(i) = inf;
            end
        else
            Normes(i) = inf;
        end
    end

Ensuite, je ne suis pas certain que la condition suivante fasse ce que tu espères :

Code :

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

if Point(j,:) == Terre(1:3)

Je ferais plutôt

Code :

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

if all(Point(j,:) == Terre(1:3))

ou

Code :

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

if Point(j,1) == Terre(1) && Point(j,2) == Terre(2) && Point(j,3) == Terre(3)

**Globoxx** · 25/11/2013, 13h32

Merci beaucoup pour ta réponse !

J'ai donc simplifié mon code avec tes 3 premières propositions et cela fonctionne parfaitement.
Par contre, pour ce qui est d'écrire :

Code :

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

Normes = inf(N,1);

Mon code ne fonctionne plus correctement, après quelques itérations, la valeur de ligne i de All_Best_ways reste la même jusqu'à la fin.

Enfin, la condition :

Code :

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

if Point(j,:) == Terre(1:3)

Me permet de tester si le point j actuel se trouve à certaines coordonnées.
Si je mets un all, il va tester toutes les valeurs présentes dans Point et pas le point actuel non ?

**Jerome Briot** · 25/11/2013, 14h02

Envoyé par Globoxx

Par contre, pour ce qui est d'écrire :

Code :

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

Normes = inf(N,1);

Mon code ne fonctionne plus correctement, après quelques itérations, la valeur de ligne i de All_Best_ways reste la même jusqu'à la fin.

Bizarre, il n'y a pas de raison à cela

Envoyé par Globoxx

Me permet de tester si le point j actuel se trouve à certaines coordonnées.

Essai ceci :

Code :

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

1
2
3
4
>> if [1 2 3] == [1 2 3], disp('OK'); end
OK
>> if [0 2 3] == [1 2 3], disp('OK'); end
>> if [1 4 5] == [1 2 3], disp('OK'); end

Le test ne vérifie que l'égalité des premières valeurs de chaque terme.
Il faut plutôt utiliser all ou any selon le besoin

Envoyé par Globoxx

Si je mets un all, il va tester toutes les valeurs présentes dans Point et pas le point actuel non ?

Il va seulement tester les valeurs à la ligne j

**Jerome Briot** · 25/11/2013, 14h07

Peux-tu poster le code avec les modifications ?

**Globoxx** · 25/11/2013, 17h13

Le voici :

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
 
% Algorithme
 
        NormesO = zeros(N,1);
        All_Best_ways = zeros(N,1);
        Point = zeros(N,3);
 
        for i = 1 : N
            VectorO = P(i,1:3) - Origine(1,1:3);
            NormesO(i) = sqrt((VectorO(1))^2+(VectorO(2))^2+(VectorO(3))^2);
        end
        Emplacement_Best_way = find(NormesO == min(NormesO(:)));
        if length(Emplacement_Best_way) ~= 1 % Si il y a plusieurs plus courts chemins
            Emplacement_Best_way(2:end) = []; % On ne prend que le premier
        end
        Best_way = min(NormesO);
        All_Best_ways(1) = Best_way;
        P(Emplacement_Best_way,4) = 1; % Le système est visité
        Point(1,:) = P(Emplacement_Best_way,1:3);
 
        if all(Point(1,:) == Terre(1:3)) % Si la Terre est atteinte
            Jusqua_Terre = sum(All_Best_ways);
        end
 
        Normes = zeros(N,1);
        for j = 2 : N
            for i = 1 : N
                if i ~= Emplacement_Best_way
                    if P(i,4) == 0
                        Vector = P(i,1:3) - P(Emplacement_Best_way,1:3);
                        Normes(i) = sqrt((Vector(1))^2+(Vector(2))^2+(Vector(3))^2);
                    else
                        Normes(i) = inf;
                    end
                else
                    Normes(i) = inf;
                end
            end
            [All_Best_ways(j),Emplacement_Best_way] = min(Normes);
            P(Emplacement_Best_way,4) = 1; % Le système est visité
            Point(j,:) = P(Emplacement_Best_way,1:3);
 
            if all(Point(j,:) == Terre(1:3)) % Si la Terre est atteinte
                Jusqua_Terre = sum(All_Best_ways);
                break % On arrête l'algorithme
            end
        end

Finalement all fonctionne très bien merci !
Mais pour le Normes = inf(N,1)... Je sèche.

**Jerome Briot** · 25/11/2013, 18h12

Envoyé par Globoxx

Mais pour le Normes = inf(N,1)... Je sèche.

Essaie comme ceci :

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
Normes = inf(N,1);
for j = 2 : N

    for i = 1 : N
        if i ~= Emplacement_Best_way
            if P(i,4) == 0
                Vector = P(i,1:3) - P(Emplacement_Best_way,1:3);
                Normes(i) = sqrt((Vector(1))^2+(Vector(2))^2+(Vector(3))^2);
            end
        end
    end
    
    [All_Best_ways(j),Emplacement_Best_way] = min(Normes);
    P(Emplacement_Best_way,4) = 1; % Le système est visité
    Point(j,:) = P(Emplacement_Best_way,1:3);
    
    if all(Point(j,:) == Terre(1:3)) % Si la Terre est atteinte
        Jusqua_Terre = sum(All_Best_ways);
        break % On arrête l'algorithme
    end
    
    Normes(:) = inf;
    
end

Sinon, de la même manière que pour Vector, as-tu besoin de stocker toutes les valeurs de Points ?

Si ce n'est pas le cas, tu pourrais remplacer :

Code :

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

1
2
3
4
5
6
    Point(j,:) = P(Emplacement_Best_way,1:3);
 
    if all(Point(j,:) == Terre(1:3)) % Si la Terre est atteinte
        Jusqua_Terre = sum(All_Best_ways);
        break % On arrête l'algorithme
    end

par

Code :

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

1
2
3
4
    if all(P(Emplacement_Best_way,1:3) == Terre(1:3)) % Si la Terre est atteinte
        Jusqua_Terre = sum(All_Best_ways);
        break % On arrête l'algorithme
    end

Pour finir, tu n'a pas reporter la modification sur la recherche de minimum dans la première partie du code :

Code :

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

1
2
3
4
5
6
Emplacement_Best_way = find(NormesO == min(NormesO(:)));
        if length(Emplacement_Best_way) ~= 1 % Si il y a plusieurs plus courts chemins
            Emplacement_Best_way(2:end) = []; % On ne prend que le premier
        end
        Best_way = min(NormesO);
        All_Best_ways(1) = Best_way;

Dernière remarque, tu devrais pouvoir éventuellement te passer de la fonction sqrt dans les calculs de la norme. Puisque la fonction est croissante, la recherche du minimum ne sera pas affectée.

Peux-tu aussi nous dire si ces modifications ont permis un gain de temps substantiel ?

**Globoxx** · 25/11/2013, 18h40

Toutes les améliorations que tu m'as données sont parfaites !
Merci à l'infini !
D'après mes premières observations, j'ai un gain de temps d'à peu près 10% sur l'ancienne version !
Maintenant que mon code est simplifié, m'est-il possible d'utiliser parfor ?

**Jerome Briot** · 25/11/2013, 18h45

Envoyé par Dut

Puisque la fonction est croissante, la recherche du minimum ne sera pas affectée.

Boulette... il faut impérativement que les valeurs contenues dans Vector soient supérieures à 1

**Jerome Briot** · 25/11/2013, 18h48

Euh... à quoi sert la boucle sur j ?

**Globoxx** · 25/11/2013, 19h00

La boucle j me sert ici :

Code :

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

[All_Best_ways(j),Emplacement_Best_way] = min(Normes);

Je pourrais m'en passer ?

**Jerome Briot** · 25/11/2013, 20h27

Envoyé par Globoxx

Je pourrais m'en passer ?

Finalement, non

Par contre je pense que la condition suivante n'est pas nécessaire :

Code :

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

if i ~= Emplacement_Best_way

Si je récapitule toutes les modifications, on a ceci :

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
% Algorithme
 
Normes = inf(N,1);
All_Best_ways = zeros(N,1);
Point = zeros(N,3);
 
for i = 1 : N
    Vector = P(i,1:3) - Origine(1,1:3);
    Normes(i) = sqrt(Vector(1)^2+Vector(2)^2+Vector(3)^2);
end
 
[All_Best_ways(1),Emplacement_Best_way] = min(Normes);
P(Emplacement_Best_way,4) = 1; % Le système est visité
Point(1,:) = P(Emplacement_Best_way,1:3);
 
if all(Point(1,:) == Terre(1:3)) % Si la Terre est atteinte
    Jusqua_Terre = All_Best_ways;
    break
end
 
Normes(:) = inf;
 
for j = 2 : N
 
    for i = 1 : N
        if P(i,4) == 0
            Vector = P(i,1:3) - P(Emplacement_Best_way,1:3);
            Normes(i) = sqrt(Vector(1)^2+Vector(2)^2+Vector(3)^2);
        end
    end
 
    [All_Best_ways(j),Emplacement_Best_way] = min(Normes);
    P(Emplacement_Best_way,4) = 1; % Le système est visité
    Point(j,:) = P(Emplacement_Best_way,1:3);
 
    Normes(:) = inf;
 
    if all(Point(j,:) == Terre(1:3)) % Si la Terre est atteinte
        Jusqua_Terre = sum(All_Best_ways);
        break % On arrête l'algorithme
    end
 
end

C'est bien ça ?

**Jerome Briot** · 25/11/2013, 20h32

Quel est l'ordre de grandeur de N ?

**Globoxx** · 25/11/2013, 20h44

Oui c'est tout à fait ça !

Et bien tout mon code est dans une boucle :

Code :

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

for N = 10:Nombre voulu

La valeur max de Nombre voulue est actuellement de 1100 mais pourra augmenter si je gagne en vitesse d'exécution.

**Jerome Briot** · 25/11/2013, 21h18

Essaie ceci :

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
All_Best_ways = zeros(N,1);
Point = zeros(N,3);
 
Vector = bsxfun(@minus,P(:,1:3),Origine(1,1:3));
Normes = sqrt(sum(Vector.^2,2));
 
[All_Best_ways(1),Emplacement_Best_way] = min(Normes);
P(Emplacement_Best_way,4) = inf; % Le système est visité
Point(1,:) = P(Emplacement_Best_way,1:3);
 
if all(Point(1,:) == Terre(1:3)) % Si la Terre est atteinte
    Jusqua_Terre = All_Best_ways;
    return
end
 
for j = 2 : N
 
    Vector = bsxfun(@minus,P(:,1:3),P(Emplacement_Best_way,1:3));
    Normes = sqrt(sum(Vector.^2,2)).*P(:,4);
 
    [All_Best_ways(j),Emplacement_Best_way] = min(Normes);
    P(Emplacement_Best_way,4) = inf; % Le système est visité
    Point(j,:) = P(Emplacement_Best_way,1:3);
 
    if all(Point(j,:) == Terre(1:3)) % Si la Terre est atteinte
        Jusqua_Terre = sum(All_Best_ways);
        break % On arrête l'algorithme
    end
 
end

**Globoxx** · 25/11/2013, 21h37

J'ai testé et il y a visiblement un problème, la condition

Code :

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

if all(Point(j,:) == Terre(1:3))

semble ne jamais être remplie.
Mais je ne comprends pas totalement ce code, je vais devoir le potasser.

Edit : A mon avis le problème vient de

Code :

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

Normes = sqrt(sum(Vector.^2,2)).*P(:,4);

**Jerome Briot** · 26/11/2013, 10h10

La fonction bsxfun remplace simplement ceci :

Code :

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

1
2
3
for n = 1:size(P,1)
    P(n,:) = P(:,n) - Origine;
end

Pour le reste, si j'ai bien compris l'algorithme, le code cherche à aller d'une origine vers la Terre en passant de proche en proche, c'est bien ça ?

Si c'est le cas, je te propose une version avec tri :

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
Vector = bsxfun(@minus, P, Origine);
Normes = sqrt(sum(Vector.^2, 2));
 
[best_ways,idx] = min(Normes);
 
Jusqua_Terre = best_ways;
 
temp = P(idx,:);
P(idx,:) = P(1,:);
P(1,:) = temp;
 
if all(P(1,:) == Terre)
    return
end
 
for j = 2 : N
 
    Vector = bsxfun(@minus, P(j:end,:), P(j-1,:));
    Normes = sqrt(sum(Vector.^2, 2));
 
    [best_ways,idx] = min(Normes);
 
    Jusqua_Terre = Jusqua_Terre + best_ways;
 
    idx = idx+j-1;
 
    temp = P(idx,:);
    P(idx,:) = P(j,:);
    P(j,:) = temp;
 
    if all(P(j,:) == Terre)
        return
    end
 
end

Le code trie les points de proche en proche dans le tableau P

La vitesse d'exécution du code s'accélère au fur et à mesure car le nombre de distance à calculer est de plus en plus faible à chaque itération.

Je le test avec ce jeu de données :

Code :

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

1
2
3
4
5
N = 100;
P = rand(N,2);
Origine = rand(1,2);
idx = randperm(N);
Terre = P(idx(1),:);

On peut afficher le résultat avec :

Code :

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

1
2
3
4
figure
plot(P(:,1),P(:,2),'r*',Origine(1),Origine(2),'gd',...
    Terre(1),Terre(2),'bs',[Origine(1);P(1:j,1)],[Origine(2);P(1:j,2)],'m-')
axis equal

J'espère ne pas être trop à coté de la plaque

**Globoxx** · 26/11/2013, 18h30

Je comprends plus ou moins ton code mais il ne fonctionne pas chez moi car le reste de mon code, ainsi que mon jeux de données, sont différents et j'ai du mal à adapter le code à mes données.
Sinon tu as bien compris mon but !

Je vais te montrer mon script en entier, cela peut peut-être t'aider à encore mieux le comprendre ! Il s'agit de l'ancienne version mais améliorée :

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
clear all
tic
 
Terre = [500,500,500,0];
 
% Distance de toutes les exoplanètes recensées
Distance_from_Terre = [0,110.6,119.5,76.4,18.1,21.41,73.1,145,74.8,140,12.21,25,26.67,52.4,39.4,78.5,97.3,13.97,14.7,12.34,56.9,8.52,19.75,22,97.2,45.5,47.3,20.2,42.2,66,34.6,50,200,19.3,21.3,23.1,460,345,300,400,150,380,460,165,3.2,45,7.7,140,38.5,13.79,13,9.42,17.62,15.1,19.8,9.04,10.2,6.84,4.54,4.94,8.8,12.3,6.21,10.34,8.91,10.9,4.7,140,145,139,38,142.5,214,205,190,235,90,166,215,118,70,254,82,393,306,297,134,204,395,322,130,193,354,320,419,257,317,411,249,310,340,200,320,230,480,303,122,52.8,39.4,30.49,42,28.98,360,158,9.24,126,49.3,20.8,102,37.44,84.9,17.3,35.2,32.56,51.3,38.57,139,68.5,65.6,59,90,29,15.8,28,35,30.46,20.4,53.82,123.2,33,38,88.6,33.98,66.5,44.37,135,27.4,52.82,38.1,37.16,72.4,16.6,67.61,30,110,185,71,96,23.2,26.5,22.2,14.8,98.2,38,28.6,44.2,121.4,33.46,20.6,35.87,109.5,57.7,126,23.4,42.96,12.9,53.05,59.3,78.9,63,159,29.6,27.2,85.17,186,49.6,17.8,18.06,65.8,68.5,43,36.5,55.1,24.5,31.9,103.6,52.7,35.9,59.8,31.26,69,25.5,52,38,21.93,42.3,50,37.38,43.12,319,36.32,64.97,109,90,50.28,78.24,135,67.02,128,59,46.73,63.69,27,132,110,110.6,26.15,56,53,47,44.98,50,135,52.6,17.7,19.3,15.89,54.2,103,19.9,8.82,67,37.36,46.9,44.3,33,22.38,43.8,68.4,46.34,27,89.8,47.37,27,90.3,194,35.4,37.02,6.06,45,48.9,47,21.89,56,52.7,131,40.75,21.5,38,44,33.3,26.5,38,32.4,19.72,54.8,29.94,81.1,44.6,49,52.9,49.1,42,94,31.79,34.8,89.1,108.4,52,143,46.51,46.51,55,53.71,18.1,45.5,42.37,39.4,56.2,227,54.9,55,26.5,118.1,53.82,38.6,117.4,50.2,126,86,20.98,46.5,11,33,42.9,37.7,39.28,99.4,15.2,18.32,25.9,12.8,33.3,42.5,43.03,44,77.5,33.9,21.9,137,54.9,93.2,50.43,21.9,49,32.6,36,33.4,37.84,121.36,87.4,40.7,47.26,31.03,34.8,28,100,251,92,25.7,10.34,35.8,32.6,40.32,34.3,55,55.9,58,12.6,45.7,28.8,36,49.8,36.5,54.91,99,96.99,64.56,39,28.94,80.58,59.7,16.8,49,58.4,32.56,88.26,125,27.46,43.54,52.5,33.96,11.15,44.2,91,42.48,72.6,38.25,18.1,74.5,30.9,40,39.6,32.82,28.9,42.2,53,139,57.24,158,84,25.6,21.1,134,40.3,60.5,18,18,129,111,23,52.9,45,11,25.92,24,31.5,156.7,14.4,18.4,17.17,39.4,181,31.1,128.9,173,290,108,190,38.7,333,62.7,145,15.376,500,46.8,145,500,114,125,15.6,92.25,157,220,470,360,13.47,145,90,125,427,156,160,308,100,144,230,300,330,169,250,334,80,223,400,116,120,450,338,110,230,300,180,200,297,230,330,307,480,160,330,380,225,140,240,87,19.2,200,149,260,293,255,540,701,857,1330,730,550,980,800,1500,535,550,600,680,560,840,920,870,800,900,1150,1180,1200,1230,1310,1330,1340,1400,1499,1500,1510,1645,1950,2176,2250,2300,2700,3040,3300,3800,5100,5200,5700,5900,6000,6100,6500,7150,8500];
 
% Création aléatoires d'exoplanètes proches de la Terre (1-100 parsecs)
Extra_exo_proches = zeros(1,350);
for i=1:350
    x = 1+(100-1)*rand(1);
    Extra_exo_proches(1,i) = x;
end
 
% Création aléatoire d'exoplanètes éloignées de la Terre (100-500 parsecs)
Extra_exo_eloignees = zeros(1,160);
for i=1:160
    x = 100+(500-100)*rand(1);
    Extra_exo_eloignees(1,i) = x;
end
 
% Création aléatoire d'exoplanètes très éloignées (500-8000 parsecs)
Extra_exo_tres_eloignees = zeros(1,50);
for i=1:50
    x = 500+(8000-500)*rand(1);
    Extra_exo_tres_eloignees(1,i) = x;
end
 
% On ajoute toutes les exoplanètes extrapolées au vecteur initial
Distance_from_Terre = [Distance_from_Terre(1:length(Distance_from_Terre)),Extra_exo_proches(1:length(Extra_exo_proches)),Extra_exo_eloignees(1:length(Extra_exo_eloignees)),Extra_exo_tres_eloignees(1:length(Extra_exo_tres_eloignees))];
clear Extra_exo_proches Extra_exo_eloignees Extra_exo_tres_eloignees
 
% Brassage aléatoire du vecteur
x = randperm(length(Distance_from_Terre));
for i=1:length(Distance_from_Terre)
    Distance_from_Terre(1,i) = Distance_from_Terre(1,x(i));
end
 
%--------------------------------------------------------------------------------------------------
Nombre_exo = 800; % Le maximum vaut la longueur du vecteur Distance_from_Terre
Nombre_exo_min = 2; % Doit valoir minimum 2
nbrtour = 501; % Nombre impair obligatoire, minimum 3 pour avoir une moyenne
%--------------------------------------------------------------------------------------------------
 
All_Temps_Moyens_Jusqua_Terre = zeros(Nombre_exo,1);
h = waitbar(0,'Calculs en cours...'); % Initialisation de la barre de chargement
 
for N = Nombre_exo_min:Nombre_exo
 
    All_Temps_Jusqua_Terre = zeros(nbrtour,1); % Contient nbrtour valeurs de Temps_Jusqua_Terre
 
    for n = 1:nbrtour
 
        % Création des vecteurs
 
        Vectors = zeros(N,3);
        for i = 1:N-1
            x= randn(1,3);
            norms= sqrt(sum(x.^2,2));
            x= bsxfun(@times,x,1./norms); % vecteurs normés
            x= x * Distance_from_Terre(i);
            Vectors(i,1:3) = x;
        end
 
        %-----------------------------------------------------------------------------------------------------------------------
        % Création des points
 
        P = zeros(N,4);
        for i = 1:N
            P(i,1:3) = Terre(1,1:3)+Vectors(i,1:3);
        end
 
        Origine = P(1+round((N-1)*rand(1)),1:3); % Détermination du point d'origine extraterrestre
 
        %---------------------------------------------------------------------------------------------------------------------
        % Algorithme
 
        Normes = inf(N,1);
        All_Best_ways = zeros(N,1);
 
        for i = 1 : N
            VectorO = P(i,1:3) - Origine(1,1:3);
            Normes(i) = sqrt((VectorO(1))^2+(VectorO(2))^2+(VectorO(3))^2);
        end
        [All_Best_ways(1),Emplacement_Best_way] = min(Normes);
        P(Emplacement_Best_way,4) = 1; % Le système est visité
 
        if all(P(1,1:3) == Terre(1:3)) % Si la Terre est atteinte
            Jusqua_Terre = sum(All_Best_ways);
        end
 
        Normes(:) = inf;
 
        for j = 2 : N
            for i = 1 : N
                if P(i,4) == 0
                    Vector = P(i,1:3) - P(Emplacement_Best_way,1:3);
                    Normes(i) = sqrt((Vector(1))^2+(Vector(2))^2+(Vector(3))^2);
                end
            end
            [All_Best_ways(j),Emplacement_Best_way] = min(Normes);
            P(Emplacement_Best_way,4) = 1; % Le système est visité
 
            if all(P(Emplacement_Best_way,1:3) == Terre(1:3)) % Si la Terre est atteinte
                Jusqua_Terre = sum(All_Best_ways);
                break % On arrête l'algorithme
            end
            Normes(:) = inf;
        end
 
        %---------------------------------------------------------------------------------------------------------------------
        % Calculs finaux
 
        Vitesse_vaisseau = 57600; % km/h (New Horizons, http://www.cidehom.com/question.php?_q_id=3471)   ou   129600000 km/h (Projet Daedalus, http://www.daviddarling.info/encyclopedia/D/Daedalus.html)
 
        Temps_Jusqua_Terre = (3.08567758 * 10^13 * Jusqua_Terre)/Vitesse_vaisseau; % en heures
        Temps_Jusqua_Terre = Temps_Jusqua_Terre/8765.82; % en années (8765.82 = nombre d'heures moyen dans une année)
        Temps_Jusqua_Terre = Temps_Jusqua_Terre/1000; % en millénaires
        Temps_Jusqua_Terre = Temps_Jusqua_Terre/1000; % en millions d'années
 
        % Il me faudra encore ajouter le temps de terraformation à 50% des systèmes
        % et le temps de destruction des ressources sur chaque système
 
        % On ancre n fois les résultats
        All_Temps_Jusqua_Terre(n,1) = Temps_Jusqua_Terre;
    end
 
    %------------------------------------------------------------------------------------------------------------------
    % Trier les résultats en ordre croissant
    All_Temps_Jusqua_Terre = sort(All_Temps_Jusqua_Terre);
 
    % Calcul de la médiane
    Temps_Moyen_Jusqua_Terre = All_Temps_Jusqua_Terre((n+1)/2,1);
    All_Temps_Moyens_Jusqua_Terre(N,1) = Temps_Moyen_Jusqua_Terre;
 
    waitbar(N / Nombre_exo)
end
close(h) % Fermeture de la barre de chargement
 
for n = Nombre_exo_min:Nombre_exo
plot(Nombre_exo_min:n,All_Temps_Moyens_Jusqua_Terre(Nombre_exo_min:n,1));
drawnow
end
 
All_Temps_Moyens_Jusqua_Terre(All_Temps_Moyens_Jusqua_Terre == 0) = [];
 
clear norms x Vectors VectorO n h N Point Temps_Jusqua_Terre Jusqua_Terre All_Best_ways n nbrtour All_Temps_Jusqua_Terre Temps_Moyen_Jusqua_Terre ind i j Vector Emplacement_Best_way Normes Best_way P
toc

J'espère que ça peut aider !
Merci en tout cas !

Edit: J'ai réussi à adapter le code

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
 
Du_premier_coup = 0;
        Vector = bsxfun(@minus,P(:,1:3),Origine);
        Normes = sqrt(sum(Vector.^2, 2));
 
        [best_ways,idx] = min(Normes);
 
        Jusqua_Terre = best_ways;
 
        temp = P(idx,:);
        P(idx,:) = P(1,:);
        P(1,:) = temp;
 
        if all(P(1,:) == Terre)
            Du_premier_coup = 1;
        end
 
        if Du_premier_coup == 0
            for j = 2 : N
 
                Vector = bsxfun(@minus, P(j:end,:), P(j-1,:));
                Normes = sqrt(sum(Vector.^2, 2));
 
                [best_ways,idx] = min(Normes);
 
                Jusqua_Terre = Jusqua_Terre + best_ways;
 
                idx = idx+j-1;
 
                temp = P(idx,:);
                P(idx,:) = P(j,:);
                P(j,:) = temp;
 
                if all(P(j,:) == Terre)
                    break
                end
            end
        end

Pourrai-je enfin utiliser parfor ? Même si mon script est déjà nettement plus rapide !

**Jerome Briot** · 27/11/2013, 09h40

Il y a encore pas mal de chose à modifier

Les blocs comme celui-ci :

Code :

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

1
2
3
4
5
6
% Création aléatoires d'exoplanètes proches de la Terre (1-100 parsecs)
Extra_exo_proches = zeros(1,350);
for i=1:350
    x = 1+(100-1)*rand(1);
    Extra_exo_proches(1,i) = x;
end

se simplifie en

Code :

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

Extra_exo_proches = 1+(100-1)*rand(1,350);

Les indices ne sont pas nécessaires dans la ligne suivante :

Code :

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

1
2
% On ajoute toutes les exoplanètes extrapolées au vecteur initial
Distance_from_Terre = [Distance_from_Terre(1:length(Distance_from_Terre)),Extra_exo_proches(1:length(Extra_exo_proches)),Extra_exo_eloignees(1:length(Extra_exo_eloignees)),Extra_exo_tres_eloignees(1:length(Extra_exo_tres_eloignees))];

devient simplement :

Code :

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

1
2
% On ajoute toutes les exoplanètes extrapolées au vecteur initial
Distance_from_Terre = [Distance_from_Terre,Extra_exo_proches,Extra_exo_eloignees,Extra_exo_tres_eloignees];

Le bloc suivant (qui est d'ailleurs faux) :

Code :

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

1
2
3
4
5
% Brassage aléatoire du vecteur
x = randperm(length(Distance_from_Terre));
for i=1:length(Distance_from_Terre)
    Distance_from_Terre(1,i) = Distance_from_Terre(1,x(i));
end

devient :

Code :

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

1
2
3
% Brassage aléatoire du vecteur
x = randperm(length(Distance_from_Terre));
Distance_from_Terre = Distance_from_Terre(x);

Le bloc :

Code :

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

1
2
3
4
5
6
7
8
9
10
% Création des vecteurs
 
Vectors = zeros(N,3);
        for i = 1:N-1
            x= randn(1,3);
            norms= sqrt(sum(x.^2,2));
            x= bsxfun(@times,x,1./norms); % vecteurs normés
            x= x * Distance_from_Terre(i);
            Vectors(i,1:3) = x;
        end

devient :

Code :

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

1
2
3
4
5
6
% Création des vecteurs
 
x = rand(N,3);
norms = sqrt(sum(x.^2,2));
Vectors = bsxfun(@rdivide, x, norms);
Vectors = bsxfun(@times, x, Distance_from_Terre);

et enfin :

Code :

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

1
2
3
4
5
6
        % Création des points
 
        P = zeros(N,4);
        for i = 1:N
            P(i,1:3) = Terre(1,1:3)+Vectors(i,1:3);
        end

devient

Code :

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

1
2
3
        % Création des points
 
        P = bsxfun(@plus, Vectors, Terre)

L'utilisation de waitbar est très gourmande en temps de calcul.
Pour mesurer les performances de ton code, il est préférable de ne pas s'en servir.

Pour finir, tu inclus le tracé du graphique final dans la mesure du temps d'exécution de l'implémentation de ton algorithme.
Mais cela n'a rien à voir.
Déplace donc le toc juste à la fin de la boucle sur N

Fais les modifications, vérifie que tout fonctionne et post le nouveau code complet.

**Globoxx** · 27/11/2013, 17h41

Merci beaucoup, voici le code complet :

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
clear all
tic

Terre = [500,500,500];

% Distance de toutes les exoplanètes recensées
Distance_from_Terre = [110.6,119.5,76.4,18.1,21.41,73.1,145,74.8,140,12.21,25,47.9,26.67,52.4,39.4,78.5,97.3,13.97,14.7,12.34,56.9,8.52,19.75,22,97.2,45.5,47.3,20.2,42.2,66,34.6,50,200,19.3,21.3,23.1,460,345,300,400,150,380,460,165,3.2,45,7.7,140,38.5,13.79,13,9.42,17.62,15.1,19.8,9.04,10.2,6.84,4.54,4.94,8.8,12.3,6.21,10.34,8.91,10.9,4.7,140,145,139,38,142.5,214,205,190,235,90,166,215,118,70,254,82,393,306,297,134,204,395,322,130,193,354,320,419,257,317,411,249,310,340,200,320,230,480,303,122,52.8,39.4,30.49,42,28.98,360,158,9.24,126,49.3,20.8,102,37.44,84.9,17.3,35.2,32.56,51.3,38.57,139,68.5,65.6,59,90,29,15.8,28,35,30.46,20.4,53.82,123.2,33,38,88.6,33.98,66.5,44.37,135,27.4,52.82,38.1,37.16,72.4,16.6,67.61,30,110,185,71,96,23.2,26.5,22.2,14.8,98.2,38,28.6,44.2,121.4,33.46,20.6,35.87,109.5,57.7,126,23.4,42.96,12.9,53.05,59.3,78.9,63,159,29.6,27.2,85.17,186,49.6,17.8,18.06,65.8,68.5,43,36.5,55.1,24.5,31.9,103.6,52.7,35.9,59.8,31.26,69,25.5,52,38,21.93,42.3,50,37.38,43.12,319,36.32,64.97,109,90,50.28,78.24,135,67.02,128,59,46.73,63.69,27,132,110,110.6,26.15,56,53,47,44.98,50,135,52.6,17.7,19.3,15.89,54.2,103,19.9,8.82,67,37.36,46.9,44.3,33,22.38,43.8,68.4,46.34,27,89.8,47.37,27,90.3,194,35.4,37.02,6.06,45,48.9,47,21.89,56,52.7,131,40.75,21.5,38,44,33.3,26.5,38,32.4,19.72,54.8,29.94,81.1,44.6,49,52.9,49.1,42,94,31.79,34.8,89.1,108.4,52,143,46.51,46.51,55,53.71,18.1,45.5,42.37,39.4,56.2,227,54.9,55,26.5,118.1,53.82,38.6,117.4,50.2,126,86,20.98,46.5,11,33,42.9,37.7,39.28,99.4,15.2,18.32,25.9,12.8,33.3,42.5,43.03,44,77.5,33.9,21.9,137,54.9,93.2,50.43,21.9,49,32.6,36,33.4,37.84,121.36,87.4,40.7,47.26,31.03,34.8,28,100,251,92,25.7,10.34,35.8,32.6,40.32,34.3,55,55.9,58,12.6,45.7,28.8,36,49.8,36.5,54.91,99,96.99,64.56,39,28.94,80.58,59.7,16.8,49,58.4,32.56,88.26,125,27.46,43.54,52.5,33.96,11.15,44.2,91,42.48,72.6,38.25,18.1,74.5,30.9,40,39.6,32.82,28.9,42.2,53,139,57.24,158,84,25.6,21.1,134,40.3,60.5,18,18,129,111,23,52.9,45,11,25.92,24,31.5,156.7,14.4,18.4,17.17,39.4,181,31.1,128.9,173,290,108,190,38.7,333,62.7,145,15.376,500,46.8,145,500,114,125,15.6,92.25,157,220,470,360,13.47,145,90,125,427,156,160,308,100,144,230,300,330,169,250,334,80,223,400,116,120,450,338,110,230,300,180,200,297,230,330,307,480,160,330,380,225,140,240,87,19.2,200,149,260,293,255,540,701,857,1330,730,550,980,800,1500,535,550,600,680,560,840,920,870,800,900,1150,1180,1200,1230,1310,1330,1340,1400,1499,1500,1510,1645,1950,2176,2250,2300,2700,3040,3300,3800,5100,5200,5700,5900,6000,6100,6500,7150,8500];

% Création aléatoires d'exoplanètes proches de la Terre (1-100 parsecs)
Extra_exo_proches = 1+(100-1)*rand(1,350);

% Création aléatoire d'exoplanètes éloignées de la Terre (100-500 parsecs)
Extra_exo_eloignees = 100+(500-100)*rand(1,160);

% Création aléatoire d'exoplanètes très éloignées (500-8000 parsecs)
Extra_exo_tres_eloignees = 500+(8000-500)*rand(1,50);

% On ajoute toutes les exoplanètes extrapolées au vecteur initial
Distance_from_Terre = [Distance_from_Terre,Extra_exo_proches,Extra_exo_eloignees,Extra_exo_tres_eloignees];

clear Extra_exo_proches Extra_exo_eloignees Extra_exo_tres_eloignees

% Brassage aléatoire du vecteur
x = randperm(length(Distance_from_Terre));
Distance_from_Terre = Distance_from_Terre(x);

%--------------------------------------------------------------------------------------------------
Nombre_exo = 1100; % Le maximum vaut la longueur du vecteur Distance_from_Terre
Nombre_exo_min = 10; % Doit valoir minimum 2
nbrtour = 21; % Nombre impair obligatoire, minimum 3 pour avoir une moyenne
%--------------------------------------------------------------------------------------------------

All_Temps_Moyens_Jusqua_Terre = zeros(Nombre_exo,1);

for N = Nombre_exo_min:Nombre_exo

    All_Temps_Jusqua_Terre = zeros(nbrtour,1); % Contient nbrtour valeurs de Temps_Jusqua_Terre
    
    for n = 1:nbrtour
        
        % Création des vecteurs

        x = rand(N-1,3);
        norms = sqrt(sum(x.^2,2));
        Vectors = bsxfun(@rdivide, x, norms);
        Vectors = bsxfun(@times, x, Distance_from_Terre(1:N-1)');
        Vectors = [Vectors;0,0,0];

        %-----------------------------------------------------------------------------------------------------------------------
        % Création des points

        P = bsxfun(@plus, Vectors, Terre);
        
        Origine = 200+(600-200)*rand(1,3); % Plaçage de l'origine extraterrestre

        %---------------------------------------------------------------------------------------------------------------------
        % Algorithme
        
        Du_premier_coup = 0;
        Vector = bsxfun(@minus,P(:,1:3),Origine);
        Normes = sqrt(sum(Vector.^2, 2));

        [best_ways,idx] = min(Normes);

        Jusqua_Terre = best_ways;

        temp = P(idx,:);
        P(idx,:) = P(1,:);
        P(1,:) = temp;

        if all(P(1,:) == Terre)
            Du_premier_coup = 1;
        end
        
        if Du_premier_coup == 0
            for j = 2 : N

                Vector = bsxfun(@minus, P(j:end,:), P(j-1,:));
                Normes = sqrt(sum(Vector.^2, 2));

                [best_ways,idx] = min(Normes);

                Jusqua_Terre = Jusqua_Terre + best_ways;

                idx = idx+j-1;

                temp = P(idx,:);
                P(idx,:) = P(j,:);
                P(j,:) = temp;

                if all(P(j,:) == Terre)
                    break
                end
            end
        end

        %---------------------------------------------------------------------------------------------------------------------
        % Calculs finaux

        Vitesse_vaisseau = 57600; % km/h (New Horizons, http://www.cidehom.com/question.php?_q_id=3471)   ou   129600000 km/h (Projet Daedalus, http://www.daviddarling.info/encyclopedia/D/Daedalus.html)

        Temps_Jusqua_Terre = (3.08567758 * 10^13 * Jusqua_Terre)/Vitesse_vaisseau; % en heures
        Temps_Jusqua_Terre = Temps_Jusqua_Terre/8765.82; % en années (8765.82 = nombre d'heures moyen dans une année)
        Temps_Jusqua_Terre = Temps_Jusqua_Terre/1000; % en millénaires
        Temps_Jusqua_Terre = Temps_Jusqua_Terre/1000; % en millions d'années

        % Il me faudra encore ajouter le temps de terraformation à 50% des systèmes
        % et le temps de destruction des ressources sur chaque système

        % On ancre n fois les résultats
        All_Temps_Jusqua_Terre(n,1) = Temps_Jusqua_Terre;
    end

    %------------------------------------------------------------------------------------------------------------------
    % Trier les résultats en ordre croissant
    All_Temps_Jusqua_Terre = sort(All_Temps_Jusqua_Terre);

    % Calcul de la médiane
    Temps_Moyen_Jusqua_Terre = All_Temps_Jusqua_Terre((n+1)/2,1);
    All_Temps_Moyens_Jusqua_Terre(N,1) = Temps_Moyen_Jusqua_Terre;
    
    disp(N);
end
toc

for n = Nombre_exo_min:Nombre_exo
plot(Nombre_exo_min:n,All_Temps_Moyens_Jusqua_Terre(Nombre_exo_min:n,1));
drawnow
end

All_Temps_Moyens_Jusqua_Terre(All_Temps_Moyens_Jusqua_Terre == 0) = [];

clear Origine best_ways idx temp norms x Vectors n h N Du_premier_coup Temps_Jusqua_Terre Jusqua_Terre All_Best_ways n nbrtour All_Temps_Jusqua_Terre Temps_Moyen_Jusqua_Terre ind i j Vector Normes P

Tout fonctionne nickel mis à part :

Code :

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

1
2
3
4
5
6
7
 
% Création des vecteurs
 
x = rand(N,3);
norms = sqrt(sum(x.^2,2));
Vectors = bsxfun(@rdivide, x, norms);
Vectors = bsxfun(@times, x, Distance_from_Terre);

Je l'ai donc modifié un peu et ainsi il marche :

Code :

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

1
2
3
4
5
6
x = rand(N-1,3);
norms = sqrt(sum(x.^2,2));
Vectors = bsxfun(@rdivide, x, norms);
Vectors = bsxfun(@times, x, Distance_from_Terre(1:N-1)');
Vectors = [Vectors;0,0,0];

J'ai du rajouter un vecteur nul afin de placer la Terre.

Cependant cette méthode de création de vecteurs semble ralentir le code, peut-être n'est-t-il toujours pas correct ?

[parfor] Où puis-je l'utiliser correctement dans mon algorithme ?

MATLAB

Discussions similaires

Partager

Partager