diff options
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_recombination.c')
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_recombination.c | 30 |
1 files changed, 20 insertions, 10 deletions
diff --git a/src/backend/optimizer/geqo/geqo_recombination.c b/src/backend/optimizer/geqo/geqo_recombination.c index d438a32f9af..f018902bed7 100644 --- a/src/backend/optimizer/geqo/geqo_recombination.c +++ b/src/backend/optimizer/geqo/geqo_recombination.c @@ -3,7 +3,7 @@ * geqo_recombination.c * misc recombination procedures * -* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_recombination.c,v 1.12 2003/11/29 22:39:49 pgsql Exp $ +* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_recombination.c,v 1.13 2004/01/23 23:54:21 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -19,6 +19,7 @@ /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */ #include "postgres.h" + #include "optimizer/geqo_random.h" #include "optimizer/geqo_recombination.h" @@ -32,7 +33,6 @@ * points on the tour and randomly chooses the 'next' city from * this array. When a city is chosen, the array is shortened * and the procedure repeated. - * */ void init_tour(Gene *tour, int num_gene) @@ -42,31 +42,43 @@ init_tour(Gene *tour, int num_gene) int next, i; + /* Fill a temp array with the IDs of all not-yet-visited cities */ tmp = (Gene *) palloc(num_gene * sizeof(Gene)); for (i = 0; i < num_gene; i++) - { - tmp[i] = (Gene) i + 1; /* builds tours "1 - 2 - 3" etc. */ - } + tmp[i] = (Gene) (i + 1); remainder = num_gene - 1; for (i = 0; i < num_gene; i++) { - next = (int) geqo_randint(remainder, 0); /* choose city between 0 - * and remainder */ + /* choose value between 0 and remainder inclusive */ + next = (int) geqo_randint(remainder, 0); + /* output that element of the tmp array */ tour[i] = tmp[next]; + /* and delete it */ tmp[next] = tmp[remainder]; remainder--; } + /* + * Since geqo_eval() will reject tours where tour[0] > tour[1], + * we may as well switch the two to make it a valid tour. + */ + if (num_gene >= 2 && tour[0] > tour[1]) + { + Gene gtmp = tour[0]; + + tour[0] = tour[1]; + tour[1] = gtmp; + } + pfree(tmp); } /* alloc_city_table * * allocate memory for city table - * */ City * alloc_city_table(int num_gene) @@ -77,7 +89,6 @@ alloc_city_table(int num_gene) * 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; @@ -86,7 +97,6 @@ alloc_city_table(int num_gene) /* free_city_table * * deallocate memory of city table - * */ void free_city_table(City *city_table) |