今天我想介绍客座博主Seth DeLand，他在MathWorks的MATLAB产品营销团队工作。今天，Seth将讨论一些不同的优化技术，这些技术是他用于开发谜题书“Waldo在哪里?”的策略。

内容

有一个很好的在兰德尔·奥尔森的博客上发布上周，我们讨论了流行的益智书籍《沃尔多在哪里?》(原“哪里”Wally?在英国)。

小时候，我花了好几个小时翻阅我的收藏《沃尔多在哪里?》因此，我受到兰德尔帖子的启发，自己做了一些分析。如果我能证明，在过去的20年里，我学到了足够多的东西，可以有更好的策略来找到Waldo，那就太好了。

首先，我获取每本书中的Waldo位置的数据，并绘制这些点:

分= webread (“http://www.randalolson.com/wp-content/uploads/wheres-waldo-locations.csv”）;情节(pts.X pts.Y,‘*’）;

求最短路径

接下来我想做的是尝试重现兰德尔的一些结果。旅行推销员问题(穿过所有点的最短路径是什么?)总是很有趣。我使用了与最初文章相同的起点和终点，但采用了不同的方法来寻找解决方案。我没有使用遗传算法，而是选择将其表述为一个二进制编程问题，类似于这个例子．这种方法有两个优点:

让我们看看结果:

(顺序、路径长、输出)= shortestPathAToB([分。X pts.Y], 67);持有在情节(pts.X(秩序),pts.Y(顺序))

检查INTLINPROG优化求解器的输出，我们看到绝对差距为0，这意味着我们已经找到了可能的最短路径。

output.absolutegap

ans = 0

对最短路径的不同理解

解决旅行推销员问题是很好的，但是当您实际搜索Waldo时，您看到的是一个区域而不是一个点。这有点像你在页面上应用一个圆形蒙版，你可以看到圆圈内的所有东西。因此，这让我思考:如果我们试图找到最短路径，例如，如果沿着这条路径平移一个半径为“r”的圆，您将覆盖所有Waldo位置?这使问题变得有点复杂，因为我们必须计算从所有Waldo位置到构成路径的任意线段的距离。

我选择将其表述为一个非线性规划问题，其中的目标还是最小化总距离，我们添加了一个非线性约束，即所有Waldo点必须在路径上某个点的“r”范围内。最后一个问题的解决方案是一个很好的起点。这样我们就有足够的资金来解决这个问题。为了让事情变得有趣，我解出了4个不同的r值。

r = 0.25:0.25:1;分=分(顺序:);《不扩散核武器条约》=长度(pts.X);x0 = [pts.X;pts.Y];%初步猜测溶液磅= 0(2 *不扩散核武器条约》,1);%所有变量>= 0乌兰巴托=[13 *的(不扩散核武器条约》,1);8 * 1(不扩散核武器条约》,1)];% x变量<= 13,y变量<= 8选择= optimoptions (“fmincon”，．．.“算法”，“sqp”，．．.“显示”，“没有”，．．.“TolFun”1 e - 3,．．.“MaxFunEvals”1 e5);xopt = 0(长度(x0)、(r));fval = 0(1、长度(r));parfori = 1:长度(r) noncon = @ (x) nonlcon (x [pts.X, pts.Y] r(我));[xopt(:,我),fval (i)) = fmincon (x0 @objfcn ,[],[],[],[], 磅,乌兰巴托,noncon选项);结束图;为I = 1:length(r) subplot(2,2, I);drawPath (xopt(:,我),分,r (i));标题({['视图半径= 'num2str (r (i)));．．.［'路径长度= 'num2str (fval(我)]});结束

分析解决方案

正如预期的那样，随着“r”值的增加，路径的长度会减少。这是在视图半径为1的情况下遍历这条路径的动画:

当我们显式访问每个站点时，路径长度为58.8，当我们的半径为1时，路径长度为31.2。所以我们设法缩短了我们的搜索路径。看看这个路径，我将它描述为一个Z然后一个大写的Lambda，或者:

Z \λ$ $ $ $

这样就很容易记住了。我用于此分析的所有代码都可以在这GitHub库．

谁对找沃尔多有不同的想法?你们有图像处理大师尝试过解决这个问题吗?让我们知道在这里．

获取MATLAB代码

发布与MATLAB®R2015a