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 */
33void
34init_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 */
68City *
69alloc_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 */
86void
87free_city_table(PlannerInfo *root, City * city_table)
88{
89 pfree(city_table);
90}
91
92#endif /* CX || PX || OX1 || OX2 */
93