/src/postgres/src/backend/optimizer/geqo/geqo_recombination.c
Line | Count | Source |
1 | | /*------------------------------------------------------------------------ |
2 | | * |
3 | | * geqo_recombination.c |
4 | | * misc recombination procedures |
5 | | * |
6 | | * src/backend/optimizer/geqo/geqo_recombination.c |
7 | | * |
8 | | *------------------------------------------------------------------------- |
9 | | */ |
10 | | |
11 | | /* |
12 | | * contributed by: |
13 | | * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= |
14 | | * * Martin Utesch * Institute of Automatic Control * |
15 | | * = = University of Mining and Technology = |
16 | | * * utesch@aut.tu-freiberg.de * Freiberg, Germany * |
17 | | * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= |
18 | | */ |
19 | | |
20 | | /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */ |
21 | | |
22 | | #include "postgres.h" |
23 | | |
24 | | #include "optimizer/geqo_random.h" |
25 | | #include "optimizer/geqo_recombination.h" |
26 | | |
27 | | |
28 | | /* |
29 | | * init_tour |
30 | | * |
31 | | * Randomly generates a legal "traveling salesman" tour |
32 | | * (i.e. where each point is visited only once.) |
33 | | */ |
34 | | void |
35 | | init_tour(PlannerInfo *root, Gene *tour, int num_gene) |
36 | 0 | { |
37 | 0 | int i, |
38 | 0 | j; |
39 | | |
40 | | /* |
41 | | * We must fill the tour[] array with a random permutation of the numbers |
42 | | * 1 .. num_gene. We can do that in one pass using the "inside-out" |
43 | | * variant of the Fisher-Yates shuffle algorithm. Notionally, we append |
44 | | * each new value to the array and then swap it with a randomly-chosen |
45 | | * array element (possibly including itself, else we fail to generate |
46 | | * permutations with the last city last). The swap step can be optimized |
47 | | * by combining it with the insertion. |
48 | | */ |
49 | 0 | if (num_gene > 0) |
50 | 0 | tour[0] = (Gene) 1; |
51 | |
|
52 | 0 | for (i = 1; i < num_gene; i++) |
53 | 0 | { |
54 | 0 | j = geqo_randint(root, i, 0); |
55 | | /* i != j check avoids fetching uninitialized array element */ |
56 | 0 | if (i != j) |
57 | 0 | tour[i] = tour[j]; |
58 | 0 | tour[j] = (Gene) (i + 1); |
59 | 0 | } |
60 | 0 | } |
61 | | |
62 | | /* city table is used in these recombination methods: */ |
63 | | #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2) |
64 | | |
65 | | /* |
66 | | * alloc_city_table |
67 | | * |
68 | | * allocate memory for city table |
69 | | */ |
70 | | City * |
71 | | alloc_city_table(PlannerInfo *root, int num_gene) |
72 | | { |
73 | | City *city_table; |
74 | | |
75 | | /* |
76 | | * palloc one extra location so that nodes numbered 1..n can be indexed |
77 | | * directly; 0 will not be used |
78 | | */ |
79 | | city_table = palloc_array(City, num_gene + 1); |
80 | | |
81 | | return city_table; |
82 | | } |
83 | | |
84 | | /* |
85 | | * free_city_table |
86 | | * |
87 | | * deallocate memory of city table |
88 | | */ |
89 | | void |
90 | | free_city_table(PlannerInfo *root, City * city_table) |
91 | | { |
92 | | pfree(city_table); |
93 | | } |
94 | | |
95 | | #endif /* CX || PX || OX1 || OX2 */ |