VRPH
1.0
|
00001 00002 // // 00003 // This file is part of the VRPH software package for // 00004 // generating solutions to vehicle routing problems. // 00005 // VRPH was developed by Chris Groer (cgroer@gmail.com). // 00006 // // 00007 // (c) Copyright 2010 Chris Groer. // 00008 // All Rights Reserved. VRPH is licensed under the // 00009 // Common Public License. See LICENSE file for details. // 00010 // // 00012 00013 #include "VRPH.h" 00014 #define MODULUS 2147483647 00015 #define MULT 16807 00016 00017 // A collection of random seeds from Mathematica for the LCG - 00018 00019 static long long zrng[]= 00020 { 00021 1585898122, 977263903, 1405617513, 992686252, 18121536, 2063068841, 00022 754752318, 41984681, 105083035, 139298838, 185623219, 949931193, 00023 844017127, 220735746, 2086518219, 1159920248, 223790403, 521639770, 00024 383329278, 1351669096, 546508335, 241074248, 1250430659, 1360027002, 00025 2133008156, 801417619, 234137012, 820590974, 208037679, 762045751, 00026 1878813713, 238884113, 1183679960, 1043965154, 976700693, 2008340726, 00027 677399582, 1285359843, 1138040391, 468728879, 1173244317, 235237876, 00028 1232346133, 471001204, 1863659670, 1165359604, 1863730245, 00029 1039575367, 33196368, 447728821, 803148007, 732593271, 1682165068, 00030 1423782112, 2088550953, 936772830, 1669565296, 1410105093, 00031 1883854503, 157181746, 237269108, 530564635, 448848243, 286675281, 00032 363322466, 861763630, 825225764, 1406888526, 1616456635, 916354297, 00033 1567694919, 1200774035, 81218620, 54228387, 964954038, 392387524, 00034 1451979814, 2122793904, 1202721819, 628095876, 1098922114, 95833991, 00035 1140244378, 2013076662, 1482101325, 815732936, 154659849, 1575364612, 00036 1969394111, 2057580375, 2015360901, 1435017398, 1311586731, 00037 314500068, 162190131, 1309049839, 1760010706, 827285638, 554810512, 00038 942750612, 1888673353, 1658410347, 1535796884, 610141401, 1095089179, 00039 473990272, 1591707931, 1650890892, 2129059111, 409806116, 739034658, 00040 1074994661, 1150159741, 269214387, 1516429880, 1369667127, 00041 2122951567, 1536355824, 1947835842, 823114858, 2001677049, 243498667, 00042 438835589, 2084577438, 1778854242, 1589215500, 993105500, 1399779082, 00043 680250157, 987051556, 1597580442, 71887978, 974657481, 665567351, 00044 689482979, 1947413384, 1450689852, 1817370782, 1249183224, 94259407, 00045 1576903163, 194915665, 1059712692, 453727562, 2124585319, 1602930620, 00046 1142904759, 965673653, 246108792, 1654947015, 1878828492, 567267685, 00047 878355741, 881707113, 580077084, 901920333, 518339521, 1010914174, 00048 1742574627, 1097862854, 1000362984, 1022589700, 821089113, 00049 2040587093, 350389248, 322891321, 1159453516, 614435100, 485423061, 00050 580074455, 1038514233, 582690813, 1394060287, 1193771124, 2030353361, 00051 1331961065, 1091003721, 480683205, 172421798, 1314856444, 1020643186, 00052 161954324, 1198718865, 1108252489, 696760670, 1050697945, 871635855, 00053 485876747, 179770165, 2110038934, 1877118219, 1944112804, 889651228, 00054 1709232582, 1021461548, 1062416269, 1775284287, 1548647752, 00055 1468622131, 1501559878, 1641100862, 2043157460, 9225604, 516609908, 00056 1918652536, 890178664, 2139455918, 723888229, 380523573, 998128782, 00057 2122099165, 193945359, 1163177060, 496833754, 1752971070, 842393719, 00058 651771348, 357600681, 448174576, 1539044660, 1204659744, 526302849, 00059 1683442778, 2055374782, 2096711886, 1847065567, 2103775300, 00060 1867545195, 180757560, 756099417, 2122354186, 911394104, 377306975, 00061 1060803589, 1558009924, 1147998809, 30263572, 545721691, 1043063797, 00062 982875671, 170326373, 1003183201, 6932742, 567081165, 1339773006, 00063 668884182, 469588686, 1338125418, 1959613029, 1576328955, 1873529200, 00064 501967489, 85306291, 1735183136, 2001471533, 960275626, 130336187, 00065 1334655399, 1331594739, 345982965, 590996008, 1535438073, 1316368256, 00066 401559792, 122512210, 1415929389, 1011799313, 1869058634, 1064463722, 00067 1447264924, 474372764, 134983996, 1166979876, 2140794736, 1078919141, 00068 564009419, 1273245050, 212505753, 650918775, 1716276860, 1008717539, 00069 1491859263, 2098344229, 1700342627, 2098195790, 702806311, 430088402, 00070 1841775273, 873208521, 2015656192, 1659123069, 935557457, 1250857761, 00071 206689908, 1035486424, 410559828, 883746510, 1317520915, 1194730483, 00072 121224379}; 00073 00074 #if VRPH_ADD_ENTROPY 00075 static int initialized=0; 00076 #endif 00077 00078 00079 double lcgrand(int stream) 00080 { 00084 00085 long long zi; 00086 #if VRPH_ADD_ENTROPY 00087 // Add a time component to the RNG to get different 00088 // results on different runs. 00089 00090 if(!initialized) 00091 { 00092 time_t now; 00093 time(&now); 00094 srand((unsigned int)now); 00095 zrng[stream]+=rand(); 00096 00097 initialized=1; 00098 00099 } 00100 #endif 00101 00102 zi= zrng[stream]; 00103 00104 zrng[stream]=(MULT*zi) % MODULUS; 00105 //Update the state of the RNG 00106 00107 return((double)zrng[stream]/MODULUS); 00108 } 00109 00110 void random_permutation(int *perm, int n) 00111 { 00117 00118 int r, len, temp; 00119 00120 len = n-1; 00121 00122 while(len >= 0) 00123 { 00124 r= (int)( lcgrand(9) * n);//between 0 and n-1 inclusive 00125 if(r<0) 00126 r=0; 00127 if(r>n-1) 00128 r=n-1; 00129 temp=perm[len]; 00130 perm[len]=perm[r]; 00131 perm[r]=temp; 00132 len--; 00133 } 00134 00135 00136 return; 00137 } 00138 00139