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
| #include <iostream>
#include <stdlib.h>
#include <time.h>
struct Node
{
unsigned int id;
unsigned int cout;
};
static int node_compare(const void* _n1, const void* _n2)
{
const Node* n1 = (const Node*)_n1;
const Node* n2 = (const Node*)_n2;
if(n1->cout < n2->cout)
{
return -1;
}
else if(n1->cout > n2->cout)
{
return 1;
}
else
{
return 0;
}
}
static unsigned int numCalculs = 0;
static unsigned int srand_time = time(0);
static unsigned int calculer(unsigned int n1, unsigned int n2)
{
/* simule le calcul du coût de n1 a n2 */
numCalculs++;
srand(n1+n2^srand_time);
unsigned result = rand() & 0xffff;
// std::cout << n1 << ", " << n2 << " : " << result << std::endl;
return result;
}
// descend dans ce noeud, remplis result avec le chemin le plus avantageux
// retourne la longeur du meilleur chemin trouvé
static unsigned int descendre(unsigned int n, unsigned int profondeur, unsigned int max, Node* result)
{
Node enfants[256];
// pour chaque enfant, calcule le cout
for(int i = 0; i < 256; ++i)
{
enfants[i].id = (n << 8) + i;
enfants[i].cout = calculer(n, enfants[i].id);
}
// trie
qsort(enfants, 256, sizeof(Node), &node_compare);
// si on est au bout de la chaîne, alors forcément le meilleur chemin c'est le plus simple
if(profondeur == 3)
{
result[3] = enfants[0];
return enfants[0].cout;
}
else
{
// au mieux, on trouvera max
unsigned int longueur = max;
for(size_t i = 0; i < 256; ++i)
{
for(unsigned j = 0; j < profondeur + 1; ++j)
std::cout << " ";
std::cout << i << "(" << longueur << ") {" << enfants[i].cout << "}" << std::endl;
// si le cout de cet enfant est pire que le max deja trouvé, pas besoin de continuer
if(enfants[i].cout >= longueur)
break;
// sinon, descend dans cet enfant, voit si il y a un noeud plus avantageux que celui déjà trouvé
Node temp[4];
unsigned int cetteLongueur = enfants[i].cout + descendre(enfants[i].id, profondeur + 1, longueur - enfants[i].cout, temp);
if(cetteLongueur < longueur)
{
// on a trouvé un noeud encore meilleur, on installe ce résultat temporaire dans le final
longueur = cetteLongueur;
for(unsigned int p = profondeur+1; p < 4; ++p)
{
result[p] = temp[p];
}
result[profondeur] = enfants[i];
}
}
return longueur;
}
}
int main(int argc, char *argv[])
{
std::cout << "start" << std::endl;
unsigned int longueur = (unsigned)-1;
Node result[4];
for(unsigned int i = 0; i < 256; ++i)
{
std::cout << i << std::endl;
longueur = descendre(i, 0, longueur, result);
}
std::cout << "plus court chemin: " << result[0].id << "->" << result[1].id << "->" << result[2].id << "->" << result[3].id << std::endl;
std::cout << "cout:" << result[0].cout + result[1].cout + result[2].cout + result[3].cout << std::endl;
std::cout << "Nombre d'appels a calculer: " << numCalculs;
} |
Plus court chemin , Arborescence , ACO
Répondre avec citation
).
Envoyé par screetch
.
Partager