Branch data     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 */