最大限度地减少在途时间 [英] Minimizing time in transit
问题描述
[更新底部（包括解决方案的源$ C $ C ）]
我有一个具有挑战性的业务问题，一个计算机可以帮助解决。
随着山区流长蜿蜒的河流具有很强的电流。沿河的某些部分地块的环境敏感的土地适合种植特定类型的珍稀水果那是在非常高的要求。一旦外地劳工收获果实，时钟开始计时，以获得水果加工厂。这是非常昂贵的尝试和送水果上游或在陆地上或空气中。通过将它们运送到工厂迄今为止最符合成本效益的机制是在容器中河边的恒定电流驱动的单独的下游。我们要建设10个加工厂，并需要找到这些沿河最小化的总时间花费水果在运输过程中的能力。到达最近的下游工厂前的水果都需要多么漫长，但那个时候，直接伤害了在他们可以出售的价格。有效地，我们希望最小化的距离至最接近的各自的下游工厂的总和。植物可以位于从水果接入点少0米下游。
现在的问题是：为了实现利润最大化，有多少了河，我们应该建立10加工厂，如果我们发现有32水果种植区，其中亚太区域的距离，从河的底部上游是（以米为单位）： 10，40，90，160，250，360，490，......第（n ^ 2）* 10 ... 9000，9610，10320？
[希望所有的工作将朝着解决这一问题，并努力创造类似的问题和使用场景可以帮助提高认识，并产生对软件/商业方法专利的破坏和令人窒息的性质人民抵抗（以任何度这些专利可能会被认为是一个地方）内的法律。] 的
更新
UPDATE1：忘了补充：我认为这个问题是一个特例<一href="http://stackoverflow.com/questions/5167774/minimize-the-sum-of-errors-of-re$p$psentative-integers/5958885#5958885">this 之一。
UPDATE2：一个算法我写给人以几分之一秒的答案，而且我认为这是相当不错的（但它尚未稳定整个样本值）。以后我会提供更多的细节，但短期如下。将植物在相等的间距。周期在所有的地方，在每个工厂您可以通过它的两个邻国之间的测试每一个位置，直到问题得到空间（贪心算法）在解决重新计算其位置内的植物。所以你优化工厂2个控股1和3固定。然后，工厂3抱着2和4个固定的...当你到达终点，你循环回来，重复，直到你去一个完整的周期，每一个加工厂的重新计算的位置停止改变..还要在每个周期结束时，您尝试移动被拥挤彼此相邻，并且所有邻近彼此的水果转储到具有水果转储远的区域加工厂。有许多方法来改变所产生的细节，因此确切的答案。我还有其他候选算法，但所有有毛刺。 [我将在稍后发布code]正如迈克Dunlavey下文提到的，我们很可能只是想足够好。
要给出什么可能是一个足够好的结果一个想法：
旅游从32个到植物的10010总长度
{10,490,1210,1960,2890,4000,5290,6760,8410,9610}
UPDATE3：mhum第一次给了正确的精确解，但没有（还）发布程序或算法，所以我写了一起来能够产生相同的值
。 / ********* ***********************
这个程序可以编译和运行（例如，在Linux上）：
$ GCC -std = C99处理，plants.c -o处理，植物
$ ./processing-plants
************************************************** ********** /
＃包括＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
＃包括＆LT; string.h中＆GT;
//一：设定值数据。添加额外的大量在年底
诠释一个[] = {
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：数据集的大小
INT numofa = sizeof的（一）/的sizeof（int）的;
// A2：将举行（PT于）独特的数据来自一个和有序。
INT * A2;
//最大：A2尺寸
INT最大;
// num_fixed_loc：10给出了10个工厂的解决方案
INT num_fixed_loc;
// XX：持有A2索引值从memoized每个周期的最低误差的赢家。通过memoized偏移值进行访问。获奖者是根据开来左边界最小误差总和高达正确的终点线。
// FIX：将动态调整。
INT XX [百万]
// xx_last：多少XX已用完
INT xx_last = 0;
// SavedBundle：数据类型为持有memoized值需要（总traval距离和工厂位置）
typedef结构_SavedBundle {
龙辰;
INT xx_offset;
} SavedBundle;
//某人：（点报）所有计算值的查找表memoized
SavedBundle *某人; //拥有获奖的值被memoized
//排序按升序排列。
INT sortfunc（常量无效*一，常量无效* B）{
回报（*（INT *）A - *（INT *）B）;
}
/ ************
最有趣的code在这里
************ /
长full_memh（INT L，INT N）{
龙辰;
长e_min = -1;
INT TI;
如果（某人[L * MAX + N]。E）{
返回某人[L * MAX + N] .E; //方便传球
}
的for（int i = L + 1; I＆LT;最大-1;我++）{
E = 0;
//总和第一部分
对于（INT J = L + 1; J＆LT;我; J ++）{
E + = A2 [J] -A2 [L];
}
//总和第二部分
如果（N！= 1）//一般情况下，递归
E + = full_memh（I，N-1）;
否则//基本情况，反复
对于（INT J = I + 1; J＆LT;最大-1，J ++）{
E + = A2 [J] -A2 [I]
}
如果（e_min == - 1）{
e_min = E;
TI =我;
}
如果（E＆LT; e_min）{
e_min = E;
TI =我;
}
}
某人[L * MAX + N]。E = e_min;
某人[L * MAX + N] .xx_offset = xx_last;
XX [xx_last] = TI; //以后如果approp添加测试或realloc的，等等，
对（INT I = 0; I＆n种-1;我++）{
XX [xx_last +第（i + 1）] = XX [某人[TI *最大+（N-1）] xx_offset + I。];
}
xx_last + = N;
返回e_min;
}
/ ******************* ************
打电话来计算和打印结果的植物给定数量
************************************************** *********** /
INT full_memoization（INT num_fixed_loc）{
字符*海峡;
长errorsum; //为了方便
//调用递归主力
errorsum = full_memh（0，num_fixed_loc-2）;
//现在打印
STR =（字符*）malloc的（num_fixed_loc * 20 + 100）;
的sprintf（海峡，\ N％4d的％6d的{％D，num_fixed_loc-1，errorsum，A2 [0]）;
的for（int i = 0; I＆LT; num_fixed_loc-2;我++）
的sprintf（STR +的strlen（STR），％D％c的，A2 [XX [某人[0 * MAX +（num_fixed_loc-2）] xx_offset + I]。]中，（i＆所述; num_fixed_loc-3），？： '}'）;
的printf（％S，STR）;
返回0;
}
/ ******************* *
初始化并呼吁多种尺寸的株数
************************************************** /
INT主（INT X，焦炭** Y）{
INT吨;
INT I2;
的qsort（一，numofa，的sizeof（INT），sortfunc）;
T = 1;
的for（int i = 1; I＆LT; numofa;我++）
如果（A [1]！= A [1-1]）
牛逼++;
最大= T;
I2 = 1;
A2 =（INT *）malloc的（的sizeof（int）的* T）;
A2 [0] = A [0];
的for（int i = 1; I＆LT; numofa;我++）
如果（A [1]！= A [1-1]）{
A2 [I2 ++] = A [1];
}
SB =（SavedBundle *）释放calloc（的sizeof（SavedBundle），最大*最大值）;
的for（int i = 3; I＆LT; = MAX;我++）{
full_memoization（ⅰ）;
}
免费（某人）;
返回0;
}
除非我犯了一个错误，下面是详细的解决方案（通过的动态规划方法）：
ñDIST网站
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}
[Updates at bottom (including solution source code)]
I have a challenging business problem that a computer can help solve.
Along a mountainous region flows a long winding river with strong currents. Along certain parts of the river are plots of environmentally sensitive land suitable for growing a particular type of rare fruit that is in very high demand. Once field laborers harvest the fruit, the clock starts ticking to get the fruit to a processing plant. It's very costly to try and send the fruits upstream or over land or air. By far the most cost effective mechanism to ship them to the plant is downstream in containers powered solely by the river's constant current. We have the capacity to build 10 processing plants and need to locate these along the river to minimize the total time the fruits spend in transit. The fruits can take however long before reaching the nearest downstream plant but that time directly hurts the price at which they can be sold. Effectively, we want to minimize the sum of the distances to the nearest respective downstream plant. A plant can be located as little as 0 meters downstream from a fruit access point.
The question is: In order to maximize profits, how far up the river should we build the 10 processing plants if we have found 32 fruit growing regions, where the regions' distances upstream from the base of the river are (in meters): 10, 40, 90, 160, 250, 360, 490, ... (n^2)*10 ... 9000, 9610, 10320?
[It is hoped that all work going towards solving this problem and towards creating similar problems and usage scenarios can help raise awareness about and generate popular resistance towards the damaging and stifling nature of software/business method patents (to whatever degree those patents might be believed to be legal within a locality).]
UPDATES
Update1: Forgot to add: I believe this question is a special case of this one.
Update2: One algorithm I wrote gives an answer in a fraction of a second, and I believe is rather good (but it's not yet stable across sample values). I'll give more details later, but the short is as follows. Place the plants at equal spacings. Cycle over all the inner plants where at each plant you recalculate its position by testing every location between its two neighbors until the problem is solved within that space (greedy algorithm). So you optimize plant 2 holding 1 and 3 fixed. Then plant 3 holding 2 and 4 fixed... When you reach the end, you cycle back and repeat until you go a full cycle where every processing plant's recalculated position stops varying.. also at the end of each cycle, you try to move processing plants that are crowded next to each other and are all near each others' fruit dumps into a region that has fruit dumps far away. There are many ways to vary the details and hence the exact answer produced. I have other candidate algorithms, but all have glitches. [I'll post code later.] Just as Mike Dunlavey mentioned below, we likely just want "good enough".
To give an idea of what might be a "good enough" result:
10010 total length of travel from 32 locations to plants at
{10,490,1210,1960,2890,4000,5290,6760,8410,9610}
Update3: mhum gave the correct exact solution first but did not (yet) post a program or algorithm, so I wrote one up that yields the same values.
/************************************************************
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;
}
Unless I've made an error, here are exact solutions (obtained through a dynamic programming approach):
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}
这篇关于最大限度地减少在途时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
