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