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 : : /*
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
6162 tgl@sss.pgh.pa.us 35 :CBC 1820 : init_tour(PlannerInfo *root, Gene *tour, int num_gene)
36 : : {
37 : : int i,
38 : : 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 : : */
3859 49 [ + - ]: 1820 : if (num_gene > 0)
50 : 1820 : tour[0] = (Gene) 1;
51 : :
52 [ + + ]: 4600 : for (i = 1; i < num_gene; i++)
53 : : {
54 : 2780 : j = geqo_randint(root, i, 0);
55 : : /* i != j check avoids fetching uninitialized array element */
56 [ + + ]: 2780 : if (i != j)
57 : 1600 : tour[i] = tour[j];
58 : 2780 : tour[j] = (Gene) (i + 1);
59 : : }
10492 bruce@momjian.us 60 : 1820 : }
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 */
|
