概率分布的最小EMD问题

概率分布的Earth Mover’s Distance背景

问题

概率分布的最小EMD问题
求解两个1维随机变量概率分布的最小Earth Mover’s Distance.
输入: 两个n维向量x和y，其中

输出: x到y的转变矩阵P，使得EMD§最小.
设计、分析并实现贪心算法求解概率分布的最小EMD问题.
（要求：在算法设计和分析部分说明如下内容：1）贪心策略；2）剩余子问题；3）贪心选择性；4）优化子结构）

贪心策略

剩余子问题

贪心选择性

优化子结构

伪代码

输入：两个n维向量x和y
输出：x到y的转变矩阵P

EMD(x,y)
	For  i←0  To  n-1  Do
	    j←i+1;
	    If  x[i] < y[i]
	        d0 ← y[i] - x[i];
	        While  j < n  &&  x[i] != y[i]
	             If  x[j] > y[j]
	                d1←x[j] - y[j];
	                If  d1 >= d0
	                    x[i]←x[i]+d0;  x[j]←x[j]-d0;  Pji←Pji+d0;
	                Else if  d1<d0
	                    x[i]←x[i]+d1;  x[j]←x[j]-d1;  Pji←Pji+d1;
	                    d0←d0-d1; j++;
	             Else if x[j] <= y[j]
	                 j++;
	    Else if x[i] > y[i]
	        d0 ← x[i] - y[i];
	        While  j < n  &&  x[i] != y[i]
	             If   x[j] > y[j]
	                 d1←y[j] - x[j];
	                 If  d1 < d0
	                     x[i]←x[i]-d1;  x[j]←x[j]+d1;  Pij←Pij+d1;
	                     d0←d0-d1; j++;
	                 Else if  d1<d0
	                     x[i]←x[i]-d0;  x[j]←x[j]+d0;  Pij←Pij+d0;
	            Else if x[j] >= y[j]
	                 j++;
	Return P;

程序的Java代码和结果数据

结果

最后得出的最小移动距离之和是2.4311（保留四位小数的结果）。
由于根据测试用例得到的结果是一个100100的矩阵，篇幅页面有限，所以就不全展示，只展示最左上角的99部分，其余的可见EMD_result.xls或者EMD_result.txt文件。（PS：如果要运行程序的话，还必须把jxl.jar包导入到工程文件里面，才可以运行，否则写入到.xls的函数saveToXlsFile()无法运行。）

结果分析

**根据我们构建的矩阵P，我们可以根据矩阵上不为0的点的值移动earth，从而使得x与y相等。
由于外层循环是n次，循环体最多循环n次，所以EMD算法的时间复杂度是O(n^2 )。由于使用了两个数组和一个二维数组，所以空间复杂度为O(n^2 )+O(n)=O(n^2 )。
**
PS:由于编辑公式实在太麻烦了，所以就截图啦，麻烦亲们了。

最后

以上就是怕孤单跳跳糖为你收集整理的贪心算法解决概率分布的最小EMD问题概率分布的最小EMD问题的全部内容，希望文章能够帮你解决贪心算法解决概率分布的最小EMD问题概率分布的最小EMD问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。