Header And Logo

PostgreSQL
| The world's most advanced open source database.

geqo_recombination.c

Go to the documentation of this file.
00001 /*------------------------------------------------------------------------
00002 *
00003 * geqo_recombination.c
00004 *    misc recombination procedures
00005 *
00006 * src/backend/optimizer/geqo/geqo_recombination.c
00007 *
00008 *-------------------------------------------------------------------------
00009 */
00010 
00011 /* contributed by:
00012    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
00013    *  Martin Utesch              * Institute of Automatic Control      *
00014    =                             = University of Mining and Technology =
00015    *  [email protected]  * Freiberg, Germany                   *
00016    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
00017  */
00018 
00019 /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
00020 
00021 #include "postgres.h"
00022 
00023 #include "optimizer/geqo_random.h"
00024 #include "optimizer/geqo_recombination.h"
00025 
00026 
00027 /*
00028  * init_tour
00029  *
00030  *   Randomly generates a legal "traveling salesman" tour
00031  *   (i.e. where each point is visited only once.)
00032  *   Essentially, this routine fills an array with all possible
00033  *   points on the tour and randomly chooses the 'next' city from
00034  *   this array.  When a city is chosen, the array is shortened
00035  *   and the procedure repeated.
00036  */
00037 void
00038 init_tour(PlannerInfo *root, Gene *tour, int num_gene)
00039 {
00040     Gene       *tmp;
00041     int         remainder;
00042     int         next,
00043                 i;
00044 
00045     /* Fill a temp array with the IDs of all not-yet-visited cities */
00046     tmp = (Gene *) palloc(num_gene * sizeof(Gene));
00047 
00048     for (i = 0; i < num_gene; i++)
00049         tmp[i] = (Gene) (i + 1);
00050 
00051     remainder = num_gene - 1;
00052 
00053     for (i = 0; i < num_gene; i++)
00054     {
00055         /* choose value between 0 and remainder inclusive */
00056         next = geqo_randint(root, remainder, 0);
00057         /* output that element of the tmp array */
00058         tour[i] = tmp[next];
00059         /* and delete it */
00060         tmp[next] = tmp[remainder];
00061         remainder--;
00062     }
00063 
00064     pfree(tmp);
00065 }
00066 
00067 /* alloc_city_table
00068  *
00069  *   allocate memory for city table
00070  */
00071 City *
00072 alloc_city_table(PlannerInfo *root, int num_gene)
00073 {
00074     City       *city_table;
00075 
00076     /*
00077      * palloc one extra location so that nodes numbered 1..n can be indexed
00078      * directly; 0 will not be used
00079      */
00080     city_table = (City *) palloc((num_gene + 1) * sizeof(City));
00081 
00082     return city_table;
00083 }
00084 
00085 /* free_city_table
00086  *
00087  *    deallocate memory of city table
00088  */
00089 void
00090 free_city_table(PlannerInfo *root, City *city_table)
00091 {
00092     pfree(city_table);
00093 }