PostgreSQL Source Code  git master
geqo_recombination.c
Go to the documentation of this file.
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"
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
34 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  */
48  if (num_gene > 0)
49  tour[0] = (Gene) 1;
50 
51  for (i = 1; i < num_gene; i++)
52  {
53  j = geqo_randint(root, i, 0);
54  /* i != j check avoids fetching uninitialized array element */
55  if (i != j)
56  tour[i] = tour[j];
57  tour[j] = (Gene) (i + 1);
58  }
59 }
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 */
int Gene
Definition: geqo_gene.h:30
int geqo_randint(PlannerInfo *root, int upper, int lower)
Definition: geqo_random.c:36
void init_tour(PlannerInfo *root, Gene *tour, int num_gene)
void free_city_table(PlannerInfo *root, City *city_table)
struct City City
City * alloc_city_table(PlannerInfo *root, int num_gene)
int j
Definition: isn.c:74
int i
Definition: isn.c:73
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc(Size size)
Definition: mcxt.c:1304