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