Debian Codegraph @

src/backend/optimizer/geqo/geqo_ox1.c

raw
1 /*------------------------------------------------------------------------
2 *
3 * geqo_ox1.c
4 *
5 * order crossover [OX] routines;
6 * OX1 operator according to Davis
7 * (Proc Int'l Joint Conf on AI)
8 *
9 * src/backend/optimizer/geqo/geqo_ox1.c
10 *
11 *-------------------------------------------------------------------------
12 */
13
14 /* contributed by:
15 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
16 * Martin Utesch * Institute of Automatic Control *
17 = = University of Mining and Technology =
18 * [email protected] * Freiberg, Germany *
19 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
20 */
21
22 /* the ox algorithm is adopted from Genitor : */
23 /*************************************************************/
24 /* */
25 /* Copyright (c) 1990 */
26 /* Darrell L. Whitley */
27 /* Computer Science Department */
28 /* Colorado State University */
29 /* */
30 /* Permission is hereby granted to copy all or any part of */
31 /* this program for free distribution. The author's name */
32 /* and this copyright notice must be included in any copy. */
33 /* */
34 /*************************************************************/
35
36 #include "postgres.h"
37 #include "optimizer/geqo.h"
38
39 #if defined(OX1)
40
41 #include "optimizer/geqo_random.h"
42 #include "optimizer/geqo_recombination.h"
43
44 /* ox1
45 *
46 * position crossover
47 */
48 void
49 ox1(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
50 City * city_table)
51 {
52 int left,
53 right,
54 k,
55 p,
56 temp;
57
58 /* initialize city table */
59 for (k = 1; k <= num_gene; k++)
60 city_table[k].used = 0;
61
62 /* select portion to copy from tour1 */
63 left = geqo_randint(root, num_gene - 1, 0);
64 right = geqo_randint(root, num_gene - 1, 0);
65
66 if (left > right)
67 {
68 temp = left;
69 left = right;
70 right = temp;
71 }
72
73 /* copy portion from tour1 to offspring */
74 for (k = left; k <= right; k++)
75 {
76 offspring[k] = tour1[k];
77 city_table[(int) tour1[k]].used = 1;
78 }
79
80 k = (right + 1) % num_gene; /* index into offspring */
81 p = k; /* index into tour2 */
82
83 /* copy stuff from tour2 to offspring */
84 while (k != left)
85 {
86 if (!city_table[(int) tour2[p]].used)
87 {
88 offspring[k] = tour2[p];
89 k = (k + 1) % num_gene;
90 city_table[(int) tour2[p]].used = 1;
91 }
92 p = (p + 1) % num_gene; /* increment tour2-index */
93 }
94 }
95
96 #endif /* defined(OX1) */