- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
[底部更新(包括解决方案源代码)]
我有一个具有挑战性的业务问题,计算机可以帮助解决。
沿着山区流淌着一条蜿蜒的长河,水流湍急。沿着河流的某些部分是环境敏感的土地,适合种植需求量非常大的特殊类型的稀有水果。一旦田间劳动者收获了水果,时钟开始滴答作响,将水果送到加工厂。尝试将水果向上游或通过陆路或空中运送的成本非常高。到目前为止,将它们运送到工厂的最具成本效益的机制是在下游使用仅由恒流提供动力的容器。我们有能力 build 10 个加工厂,并且需要将它们选在河边,以尽量减少水果在运输过程中花费的总时间。水果可能需要很长时间才能到达最近的下游工厂,但这段时间直接影响了它们的销售价格。实际上,我们希望最小化到最近的各个下游工厂的距离总和。植物可以位于水果接入点下游 0 米处。
问题是:如果我们找到了32个水果种植区,那么为了利润最大化,我们应该在河流上游多建10个加工厂,这些种植区距离河底的上游距离是(以米为单位) ):10, 40, 90, 160, 250, 360, 490, ... (n^2)*10 ... 9000, 9610, 10320?
[希望解决此问题以及创建类似问题和使用场景的所有工作都有助于提高人们对软件/商业方法专利(无论是什么这些专利在某个地方可能被认为是合法的。]
更新
Update1:忘了补充:我相信这个问题是this one的特例.
更新 2:我编写的一种算法可以在几分之一秒内给出答案,我认为它相当不错(但它在样本值之间还不稳定)。稍后我将提供更多详细信息,但简短如下。将植物等间距放置。循环遍历所有内部植物,在每个植物处,您通过测试其两个邻居之间的每个位置来重新计算其位置,直到问题在该空间内得到解决(贪心算法)。因此,您优化了固定 1 和 3 的工厂 2。然后种植 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;
}
最佳答案
让我给你一个简单的例子 Metropolis-Hastings算法。假设您有一个状态向量 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 次循环后,样本的平均值就是您作为答案的结果。
它需要诊断和调整。通常会绘制样本,而您正在寻找的是稳定(不会移动太多)且接受率高(非常模糊)的“模糊毛毛虫”图。您可以使用的主要参数是 sigma。如果 sigma 太小,情节会模糊但会四处游荡。如果它太大,图就不会模糊——它会有水平线段。通常随机选择起始向量 x,并且通常会选择多个起始向量,以查看它们是否在同一个位置结束。
没有必要同时改变状态向量 x 的所有分量。您可以循环浏览它们,一次改变一个,或采用类似的方法。
此外,如果您不需要诊断图,则可能不需要保存样本,只需即时计算平均值和方差即可。
在我熟悉的应用程序中,P(x) 是概率的度量,通常在对数空间中,因此它可以在 0 到负无穷大之间变化。然后执行“可能接受”步骤是 (exp(logp' - logp))
关于algorithm - 最大限度地减少运输时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6017278/
我在一本书(Interview Question)中读到这个问题,想在这里详细讨论这个问题。请点亮它。 问题如下:- 隐私和匿名化 马萨诸塞州集团保险委员会早在 1990 年代中期就有一个绝妙的主意
我最近接受了一次面试,面试官给了我一些伪代码并提出了相关问题。不幸的是,由于准备不足,我无法回答他的问题。由于时间关系,我无法向他请教该问题的解决方案。如果有人可以指导我并帮助我理解问题,以便我可以改
这是我的代码 public int getDist(Node root, int value) { if (root == null && value !=0) return
就效率而言,Strassen 算法应该停止递归并应用乘法的最佳交叉点是多少? 我知道这与具体的实现和硬件密切相关,但对于一般情况应该有某种指南或某人的一些实验结果。 在网上搜索了一下,问了一些他们认为
我想学习一些关于分布式算法的知识,所以我正在寻找任何书籍推荐。我对理论书籍更感兴趣,因为实现只是个人喜好问题(我可能会使用 erlang(或 c#))。但另一方面,我不想对算法进行原始的数学分析。只是
我想知道你们中有多少人实现了计算机科学的“ classical algorithms ”,例如 Dijkstra's algorithm或现实世界中的数据结构(例如二叉搜索树),而不是学术项目? 当有
我正在解决旧编程竞赛中的一些示例问题。在这个问题中,我们得到了我们有多少调酒师以及他们知道哪些食谱的信息。制作每杯鸡尾酒需要 1 分钟,我们需要使用所有调酒师计算是否可以在 5 分钟内完成订单。 解决
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题? 更新问题,以便 editing this post 可以用事实和引用来回答它. 关闭 8 年前。 Improve
我开始学习 Nodejs,但我被困在中间的某个地方。我从 npm 安装了一个新库,它是 express -jwt ,它在运行后显示某种错误。附上代码和错误日志,请帮助我! const jwt = re
我有一个证书,其中签名算法显示“sha256rsa”,但指纹算法显示“sha1”。我的证书 SHA1/SHA2 的标识是什么? 谢谢! 最佳答案 TL;TR:签名和指纹是完全不同的东西。对于证书的强度
我目前在我的大学学习数据结构类(class),并且在之前的类(class)中做过一些算法分析,但这是我在之前的类(class)中遇到的最困难的部分。我们现在将在我的数据结构类(class)中学习算法分
有一个由 N 个 1x1 方格组成的区域,并且该区域的所有部分都是相连的(没有任何方格无法到达的方格)。 下面是一些面积的例子。 我想在这个区域中选择一些方块,并且两个相邻的方块不能一起选择(对角接触
我有一些多边形形状的点列表,我想将其包含在我页面上的 Google map 中。 我已经从原始数据中删除了尽可能多的不必要的多边形,现在我剩下大约 12 个,但它们非常详细以至于导致了问题。现在我的文
我目前正在实现 Marching Squares用于计算等高线曲线,我对此处提到的位移位的使用有疑问 Compose the 4 bits at the corners of the cell to
我正在尝试针对给定算法的约束满足问题实现此递归回溯函数: function BACKTRACKING-SEARCH(csp) returns solution/failure return R
是否有包含反函数的库? 作为项目的一部分,我目前正在研究测向算法。我正在使用巴特利特相关性。在 Bartlett 相关性中,我需要将已经是 3 次矩阵乘法(包括 Hermitian 转置)的分子除以作
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
问题的链接是UVA - 1394 : And There Was One . 朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素并在最后停止:这需要 O(n^2) 时间。 我搜索了一种替代算法并
COM 中创建 GUID 的函数 (CoCreateGUID) 使用“分散唯一性算法”,但我的问题是,它是什么? 谁能解释一下? 最佳答案 一种生成 ID 的方法,该 ID 具有一定的唯一性保证,而不
在做一个项目时我遇到了这个问题,我将在这个问题的实际领域之外重新措辞(我想我可以谈论烟花的口径和形状,但这会使理解更加复杂).我正在寻找一种(可能是近似的)算法来解决它。 我有 n 个不同大小的容器,
我是一名优秀的程序员,十分优秀!