1701009594
我和数学有约：趣味数学及算法解析 [:1701004256]
1701009595
我和数学有约：趣味数学及算法解析 8.2 盲人下山
1701009596
1701009597
【问题】何谓“盲人下山”？
1701009598
1701009599
【分析】
1701009600
1701009601
所谓“盲人下山”就是一个盲人处于山上的某一点x0，要走到谷底，该盲人要如何处理。
1701009602
1701009603
由于盲人看不到山势的变化，因此他只能根据脚下局部地区的变化选择一个前进的方向，然后做探测性移动。很自然地，这一方向应是下降方向，盲人沿着该方向探测移动，走到山在该方向的最低点并停止在这点，然后在新的位置重新寻找方向，继续进行探测性移动。
1701009604
1701009605
按这种方式，可以期待盲人最终到达山谷的最低点。
1701009606
1701009607
在此我们选取一个函数来模拟一座山峰，函数如下：
1701009608
1701009609
1701009610
1701009611
1701009612
于是盲人下山问题就变得触手可得，可以直接由图形进行模拟盲人下山问题。
1701009613
1701009614
1701009615
编写MATLAB程序绘制函数如下：
1701009616
1701009617
clc,clear,close all %清屏和清除变量 warning off %消除警告 %盲人下山 figure(‘color’,[1,1,1]) %设置图形背景为白色 ezmesh(‘8*x1^2+9*x2^2-8*x1*x2-12*x1-6*x2’,[-2,4,-2,4]) %曲面绘制 view([-24.5 2]); %图形视角 grid off %不显示网格 axis off %不显示坐标轴
1701009618
1701009619
运行程序输出图形如图8-3所示。
1701009620
1701009621
1701009622
1701009623
1701009624
图8-3 模拟山峰
1701009625
1701009626
如图8-3所示，对于该函数图像，可以等效为很多个等值线。盲人下山问题即可简化为盲人在不同的等值线上的运动轨迹，为了较为清晰地模拟盲人下山的随机性，采用鼠标随机选点，大家可以任意选取属于自己的下山路径，具体的编程如下：
1701009627
1701009628
clc,clear,close all %清屏和清除变量 warning off %消除警告 %盲人下山 a=-2;b=4; xmin=a;xmax=b;ymin=a;ymax=b; x1=linspace(xmin,xmax,100); %等分区间 x2=linspace(ymin,ymax,100); %等分区间 [X1,X2]=meshgrid(x1,x2); %数据栅格化 [Z,DZ1,DZ2]=jt(X1,X2); %调用函数 axis([xmin xmax ymin ymax]); axis equal plot([1.46808510638298],[1.148936170212776],‘o’) %画图 axis([xmin xmax ymin ymax]); %坐标轴设置 hold on %图形保持句柄 disp(‘鼠标左键选取等高线’) %显示字符串 disp(‘停止下山’) %显示字符串 button=1; x=[];y=[]; while button==1 [xi,yi,button]=ginput(1); %鼠标选点 plot([xi],[yi],‘r.’,‘markersize’,10); %画点图 hold on; %图形保持句柄 [zi,dz1,dz2]=jt(xi,yi); %调用函数 v=zi; contour(X1,X2,Z,[v v],’-‘); %等高线图 axis([xmin xmax ymin ymax]); %坐标轴设置 x=[x,xi];y=[y,yi]; H_line2=plot(x,y); set(H_line2,‘color’,‘red’,‘linewidth’,2); %设置线宽和线的颜色 xt=xi-dz1;yt=yi-dz2; H_line=plot([xi xt],[yi yt],‘k:’,‘linewidth’,1); %画图 end
1701009629
1701009630
运行程序输出图形如图8-4所示。
1701009631
1701009632
1701009633
1701009634
1701009635
图8-4 盲人下山的路径
1701009636
1701009637
盲人起点如图8-4所示中的小圆圈点，图8-4中的线表示等高度线，红色的粗实线表示盲人选择的下山路径，当然也可以选择如图8-5和图8-6所示的下山路径。
1701009638
1701009639
1701009640
当然对于这个函数而言，给定一个初始点（x，y）和一个目标点（0，0），是存在一条最优路径的。
1701009641
1701009642
1701009643