最大限度地减少运输时间

Question

[底部更新（包括解决方案源代码）]

我有一个具有挑战性的业务问题，计算机可以帮助解决。

沿着山区流淌着一条蜿蜒的长河，水流湍急。沿着河流的某些部分是环境敏感的土地，适合种植需求量非常高的特定类型的稀有水果。一旦田间工人收获水果，时钟就开始滴答作响，将水果送到加工厂。尝试将水果送到上游或陆地或空中是非常昂贵的。到目前为止，将它们运送到工厂的最具成本效益的机制是下游仅由河流恒流供电的集装箱。我们有能力建造10个加工厂，并且需要将这些工厂放在河边，以尽量减少水果在运输过程中花费的总时间。然而，水果可能需要很长时间才能到达最近的下游植物，但这段时间直接损害了它们的售价。实际上，我们希望尽量减少到最近的相应下游工厂的距离总和。植物可以位于水果接入点下游 0 米处。

问题是：为了利润最大化，如果我们找到了32个水果种植区，我们应该在河上游建造多远的加工厂，这些区域与河底上游的距离是（以米为单位）：10, 40, 90, 160, 250, 360, 490, ...（n^2）*10 ...9000、9610、10320？

[希望所有旨在解决这个问题以及创造类似问题和使用场景的工作都有助于提高对软件/商业方法专利的破坏性和窒息性的认识并引起民众的抵制（无论这些专利在任何地方被认为是合法的）。

更新

---

更新1：忘了补充：我相信这个问题是这个问题的一个特例。

Update2：我编写的一种算法在几分之一秒内给出了答案，我相信它相当不错（但它在样本值中还不稳定）。我稍后会提供更多细节，但简短如下。将植物以相等的间距放置。循环遍历所有内部工厂，在每个工厂中，您可以通过测试其两个邻居之间的每个位置来重新计算其位置，直到在该空间内解决问题（贪婪算法）。因此，您可以优化工厂 2 保持 1 和 3 固定。然后工厂 3 持有 2 和 4 固定...当你到达终点时，你循环回来并重复，直到你进入一个完整的循环，每个加工厂重新计算的位置停止变化。同样在每个周期结束时，您尝试将彼此拥挤且彼此靠近水果堆的加工厂移动到一个有水果堆的区域。有很多方法可以改变细节，从而产生确切的答案。我还有其他候选算法，但都有故障。[我稍后会发布代码。正如Mike Dunlavey在下面提到的，我们可能只是想要"足够好"。

要了解什么是"足够好"的结果：

10010 total length of travel from 32 locations to plants at 
{10,490,1210,1960,2890,4000,5290,6760,8410,9610}

更新3：mhum首先给出了正确的确切解决方案，但（尚未）发布程序或算法，因此我编写了一个产生相同值的程序或算法。

/************************************************************
This program can be compiled and run (eg, on Linux):
$ gcc -std=c99 processing-plants.c -o processing-plants
$ ./processing-plants
************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//a: Data set of values. Add extra large number at the end
int a[]={
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
};
//numofa: size of data set
int numofa=sizeof(a)/sizeof(int);
//a2: will hold (pt to) unique data from a and in sorted order.
int *a2;
//max: size of a2
int max;
//num_fixed_loc: at 10 gives the solution for 10 plants
int num_fixed_loc;
//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.
//FIX: to be dynamically sized.
int xx[1000000];
//xx_last: how much of xx has been used up
int xx_last=0;
//SavedBundle: data type to "hold" memoized values needed (total traval distance and plant locations) 
typedef struct _SavedBundle {
    long e;
    int xx_offset;
} SavedBundle;
//sb: (pts to) lookup table of all calculated values memoized
SavedBundle *sb;  //holds winning values being memoized
//Sort in increasing order.
int sortfunc (const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}
/****************************
Most interesting code in here
****************************/
long full_memh(int l, int n) {
    long e;
    long e_min=-1;
    int ti;
    if (sb[l*max+n].e) {
        return sb[l*max+n].e;  //convenience passing
    }
    for (int i=l+1; i<max-1; i++) {
        e=0;
        //sum first part
        for (int j=l+1; j<i; j++) {
            e+=a2[j]-a2[l];
        }
        //sum second part
        if (n!=1) //general case, recursively
            e+=full_memh(i, n-1);
        else      //base case, iteratively
            for (int j=i+1; j<max-1; j++) {
                e+=a2[j]-a2[i];
            }
        if (e_min==-1) {
            e_min=e;
            ti=i;
        }
        if (e<e_min) {
            e_min=e;
            ti=i;
        }
    }
    sb[l*max+n].e=e_min;
    sb[l*max+n].xx_offset=xx_last;
    xx[xx_last]=ti;      //later add a test or a realloc, etc, if approp
    for (int i=0; i<n-1; i++) {
        xx[xx_last+(i+1)]=xx[sb[ti*max+(n-1)].xx_offset+i];
    }
    xx_last+=n;
    return e_min;
}
/*************************************************************
Call to calculate and print results for given number of plants
*************************************************************/
int full_memoization(int num_fixed_loc) {
    char *str;
    long errorsum;  //for convenience
    //Call recursive workhorse
    errorsum=full_memh(0, num_fixed_loc-2);
    //Now print
    str=(char *) malloc(num_fixed_loc*20+100);
    sprintf (str,"n%4d %6d {%d,",num_fixed_loc-1,errorsum,a2[0]);
    for (int i=0; i<num_fixed_loc-2; i++)
        sprintf (str+strlen(str),"%d%c",a2[ xx[ sb[0*max+(num_fixed_loc-2)].xx_offset+i ] ], (i<num_fixed_loc-3)?',':'}');
    printf ("%s",str);
    return 0;
}
/**************************************************
Initialize and call for plant numbers of many sizes
**************************************************/
int main (int x, char **y) {
    int t;
    int i2;
    qsort(a,numofa,sizeof(int),sortfunc);
    t=1;
    for (int i=1; i<numofa; i++)
        if (a[i]!=a[i-1])
            t++;
    max=t;
    i2=1;
    a2=(int *)malloc(sizeof(int)*t);
    a2[0]=a[0];
    for (int i=1; i<numofa; i++)
        if (a[i]!=a[i-1]) {
            a2[i2++]=a[i];
        }
    sb = (SavedBundle *)calloc(sizeof(SavedBundle),max*max);
    for (int i=3; i<=max; i++) {
        full_memoization(i);
    }
    free(sb);
    return 0;
}

Answer 1

让我给你一个简单的大都会-黑斯廷斯算法的例子。假设你有一个状态向量 x，和一个拟合优度函数 P（x），它可以是你想写的任何函数。

假设您有一个可用于修改向量的随机分布 Q，例如 x' = x + N(0, 1) * sigma ，其中 N 是大约 0 的简单正态分布，sigma 是您选择的标准差。

p = P(x);
for (/* a lot of iterations */){
  // add x to a sample array
  // get the next sample
  x' = x + N(0,1) * sigma;
  p' = P(x');
  // if it is better, accept it
  if (p' > p){
    x = x';
    p = p';
  }
  // if it is not better
  else {
    // maybe accept it anyway
    if (Uniform(0,1) < (p' / p)){
      x = x';
      p = p';
    }
  }
}

通常，它的老化时间可能为 1000 个循环，之后您开始收集样品。再过10,000个周期后，样本的平均值就是你作为答案的。

它需要诊断和调整。通常绘制样本，您正在寻找的是稳定（移动不多）且具有高接受率（非常模糊）的"模糊毛盘"图。您可以使用的主要参数是西格玛。如果西格玛太小，情节将是模糊的，但它会四处游荡。如果它太大，绘图不会模糊 - 它将有水平段。通常，起始向量 x 是随机选择的，并且通常会选择多个起始向量，以查看它们是否最终位于同一位置。

没有必要同时改变状态向量 x 的所有分量。您可以循环浏览它们，一次改变一个，或者一些这样的方法。

此外，如果您不需要诊断图，则可能不需要保存样本，而只需动态计算平均值和方差即可。

在我熟悉的应用程序中，P（x） 是概率的度量，它通常在对数空间中，因此它可以从 0 到负无穷大变化。然后要执行"可能接受"步骤，它是(exp(logp' - logp))

Answer 2

除非我犯了错误，否则以下是确切的解决方案（通过动态编程方法获得）：

N  Dist  Sites
2  60950 {10,4840}
3  40910 {10,2890,6760}
4  30270 {10,2250,4840,7840}
5  23650 {10,1690,3610,5760,8410}
6  19170 {10,1210,2560,4410,6250,8410}
7  15840 {10,1000,2250,3610,5290,7290,9000}
8  13330 {10,810,1960,3240,4410,5760,7290,9000}
9  11460 {10,810,1690,2890,4000,5290,6760,8410,9610}
10 9850  {10,640,1440,2250,3240,4410,5760,7290,8410,9610}
11 8460  {10,640,1440,2250,3240,4410,5290,6250,7290,8410,9610}
12 7350  {10,490,1210,1960,2890,3610,4410,5290,6250,7290,8410,9610}
13 6470  {10,490,1000,1690,2250,2890,3610,4410,5290,6250,7290,8410,9610}
14 5800  {10,360,810,1440,1960,2560,3240,4000,4840,5760,6760,7840,9000,10240}
15 5190  {10,360,810,1440,1960,2560,3240,4000,4840,5760,6760,7840,9000,9610,10240}
16 4610  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,7290,8410,9000,9610,10240}
17 4060  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,7290,7840,8410,9000,9610,10240}
18 3550  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,6760,7290,7840,8410,9000,9610,10240}
19 3080  {10,360,810,1210,1690,2250,2890,3610,4410,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
20 2640  {10,250,640,1000,1440,1960,2560,3240,4000,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
21 2230  {10,250,640,1000,1440,1960,2560,3240,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
22 1860  {10,250,640,1000,1440,1960,2560,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
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}
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}
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}
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}
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}
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}
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}
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}
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}
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}