Line data    Source code

       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             :  */
      33             : void
      34         384 : init_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         384 :     if (num_gene > 0)
      49         384 :         tour[0] = (Gene) 1;
      50             : 
      51        1920 :     for (i = 1; i < num_gene; i++)
      52             :     {
      53        1536 :         j = geqo_randint(root, i, 0);
      54             :         /* i != j check avoids fetching uninitialized array element */
      55        1536 :         if (i != j)
      56        1092 :             tour[i] = tour[j];
      57        1536 :         tour[j] = (Gene) (i + 1);
      58             :     }
      59         384 : }
      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             :  */
      68             : City *
      69             : alloc_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             :  */
      86             : void
      87             : free_city_table(PlannerInfo *root, City * city_table)
      88             : {
      89             :     pfree(city_table);
      90             : }
      91             : 
      92             : #endif                          /* CX || PX || OX1 || OX2 */