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