Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 17th, 2012  |  syntax: None  |  size: 7.15 KB  |  hits: 19  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. Minimizing time in transit
  2. 10010 total length of travel from 32 locations to plants at
  3. {10,490,1210,1960,2890,4000,5290,6760,8410,9610}
  4.        
  5. /************************************************************
  6. This program can be compiled and run (eg, on Linux):
  7. $ gcc -std=c99 processing-plants.c -o processing-plants
  8. $ ./processing-plants
  9. ************************************************************/
  10.  
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14.  
  15. //a: Data set of values. Add extra large number at the end
  16.  
  17. int a[]={
  18. 10,40,90,160,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240,99999
  19. };
  20.  
  21. //numofa: size of data set
  22.  
  23. int numofa=sizeof(a)/sizeof(int);
  24.  
  25. //a2: will hold (pt to) unique data from a and in sorted order.
  26.  
  27. int *a2;
  28.  
  29. //max: size of a2
  30.  
  31. int max;
  32.  
  33. //num_fixed_loc: at 10 gives the solution for 10 plants
  34.  
  35. int num_fixed_loc;
  36.  
  37. //xx: holds index values of a2 from the lowest error winner of each cycle memoized. accessed via memoized offset value. Winner is based off lowest error sum from left boundary upto right ending boundary.
  38. //FIX: to be dynamically sized.
  39.  
  40. int xx[1000000];
  41.  
  42. //xx_last: how much of xx has been used up
  43.  
  44. int xx_last=0;
  45.  
  46. //SavedBundle: data type to "hold" memoized values needed (total traval distance and plant locations)
  47.  
  48. typedef struct _SavedBundle {
  49.     long e;
  50.     int xx_offset;
  51. } SavedBundle;
  52.  
  53. //sb: (pts to) lookup table of all calculated values memoized
  54.  
  55. SavedBundle *sb;  //holds winning values being memoized
  56.  
  57. //Sort in increasing order.
  58.  
  59. int sortfunc (const void *a, const void *b) {
  60.     return (*(int *)a - *(int *)b);
  61. }
  62.  
  63. /****************************
  64. Most interesting code in here
  65. ****************************/
  66.  
  67. long full_memh(int l, int n) {
  68.     long e;
  69.     long e_min=-1;
  70.     int ti;
  71.  
  72.     if (sb[l*max+n].e) {
  73.         return sb[l*max+n].e;  //convenience passing
  74.     }
  75.     for (int i=l+1; i<max-1; i++) {
  76.         e=0;
  77.         //sum first part
  78.         for (int j=l+1; j<i; j++) {
  79.             e+=a2[j]-a2[l];
  80.         }
  81.         //sum second part
  82.         if (n!=1) //general case, recursively
  83.             e+=full_memh(i, n-1);
  84.         else      //base case, iteratively
  85.             for (int j=i+1; j<max-1; j++) {
  86.                 e+=a2[j]-a2[i];
  87.             }
  88.         if (e_min==-1) {
  89.             e_min=e;
  90.             ti=i;
  91.         }
  92.         if (e<e_min) {
  93.             e_min=e;
  94.             ti=i;
  95.         }
  96.     }
  97.     sb[l*max+n].e=e_min;
  98.     sb[l*max+n].xx_offset=xx_last;
  99.     xx[xx_last]=ti;      //later add a test or a realloc, etc, if approp
  100.     for (int i=0; i<n-1; i++) {
  101.         xx[xx_last+(i+1)]=xx[sb[ti*max+(n-1)].xx_offset+i];
  102.     }
  103.     xx_last+=n;
  104.     return e_min;
  105. }
  106.  
  107. /*************************************************************
  108. Call to calculate and print results for given number of plants
  109. *************************************************************/
  110.  
  111. int full_memoization(int num_fixed_loc) {
  112.     char *str;
  113.     long errorsum;  //for convenience
  114.  
  115.     //Call recursive workhorse
  116.     errorsum=full_memh(0, num_fixed_loc-2);
  117.     //Now print
  118.     str=(char *) malloc(num_fixed_loc*20+100);
  119.     sprintf (str,"n%4d %6d {%d,",num_fixed_loc-1,errorsum,a2[0]);
  120.     for (int i=0; i<num_fixed_loc-2; i++)
  121.         sprintf (str+strlen(str),"%d%c",a2[ xx[ sb[0*max+(num_fixed_loc-2)].xx_offset+i ] ], (i<num_fixed_loc-3)?',':'}');
  122.     printf ("%s",str);
  123.     return 0;
  124. }
  125.  
  126. /**************************************************
  127. Initialize and call for plant numbers of many sizes
  128. **************************************************/
  129.  
  130. int main (int x, char **y) {
  131.     int t;
  132.     int i2;
  133.  
  134.     qsort(a,numofa,sizeof(int),sortfunc);
  135.     t=1;
  136.     for (int i=1; i<numofa; i++)
  137.         if (a[i]!=a[i-1])
  138.             t++;
  139.     max=t;
  140.     i2=1;
  141.     a2=(int *)malloc(sizeof(int)*t);
  142.     a2[0]=a[0];
  143.     for (int i=1; i<numofa; i++)
  144.         if (a[i]!=a[i-1]) {
  145.             a2[i2++]=a[i];
  146.         }
  147.     sb = (SavedBundle *)calloc(sizeof(SavedBundle),max*max);
  148.     for (int i=3; i<=max; i++) {
  149.         full_memoization(i);
  150.     }
  151.     free(sb);
  152.     return 0;
  153. }
  154.        
  155. N  Dist  Sites
  156. 2  60950 {10,4840}
  157. 3  40910 {10,2890,6760}
  158. 4  30270 {10,2250,4840,7840}
  159. 5  23650 {10,1690,3610,5760,8410}
  160. 6  19170 {10,1210,2560,4410,6250,8410}
  161. 7  15840 {10,1000,2250,3610,5290,7290,9000}
  162. 8  13330 {10,810,1960,3240,4410,5760,7290,9000}
  163. 9  11460 {10,810,1690,2890,4000,5290,6760,8410,9610}
  164. 10 9850  {10,640,1440,2250,3240,4410,5760,7290,8410,9610}
  165. 11 8460  {10,640,1440,2250,3240,4410,5290,6250,7290,8410,9610}
  166. 12 7350  {10,490,1210,1960,2890,3610,4410,5290,6250,7290,8410,9610}
  167. 13 6470  {10,490,1000,1690,2250,2890,3610,4410,5290,6250,7290,8410,9610}
  168. 14 5800  {10,360,810,1440,1960,2560,3240,4000,4840,5760,6760,7840,9000,10240}
  169. 15 5190  {10,360,810,1440,1960,2560,3240,4000,4840,5760,6760,7840,9000,9610,10240}
  170. 16 4610  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,7290,8410,9000,9610,10240}
  171. 17 4060  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,7290,7840,8410,9000,9610,10240}
  172. 18 3550  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,6760,7290,7840,8410,9000,9610,10240}
  173. 19 3080  {10,360,810,1210,1690,2250,2890,3610,4410,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  174. 20 2640  {10,250,640,1000,1440,1960,2560,3240,4000,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  175. 21 2230  {10,250,640,1000,1440,1960,2560,3240,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  176. 22 1860  {10,250,640,1000,1440,1960,2560,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  177. 23 1520  {10,250,490,810,1210,1690,2250,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  178. 24 1210  {10,250,490,810,1210,1690,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  179. 25 940   {10,250,490,810,1210,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  180. 26 710   {10,160,360,640,1000,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  181. 27 500   {10,160,360,640,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  182. 28 330   {10,160,360,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  183. 29 200   {10,160,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  184. 30 100   {10,90,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  185. 31 30    {10,90,160,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  186. 32 0     {10,40,90,160,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
  187.        
  188. p = P(x);
  189. for (/* a lot of iterations */){
  190.   // add x to a sample array
  191.   // get the next sample
  192.   x' = x + N(0,1) * sigma;
  193.   p' = P(x');
  194.   // if it is better, accept it
  195.   if (p' > p){
  196.     x = x';
  197.     p = p';
  198.   }
  199.   // if it is not better
  200.   else {
  201.     // maybe accept it anyway
  202.     if (Uniform(0,1) < (p' / p)){
  203.       x = x';
  204.       p = p';
  205.     }
  206.   }
  207. }
create a new version of this paste RAW Paste Data