TLA  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 CBC         192 : 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             192 :     if (num_gene > 0)
      49             192 :         tour[0] = (Gene) 1;
      50                 : 
      51             960 :     for (i = 1; i < num_gene; i++)
      52                 :     {
      53             768 :         j = geqo_randint(root, i, 0);
      54                 :         /* i != j check avoids fetching uninitialized array element */
      55             768 :         if (i != j)
      56             546 :             tour[i] = tour[j];
      57             768 :         tour[j] = (Gene) (i + 1);
      58                 :     }
      59             192 : }
      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 */