www.gusucode.com > demos工具箱matlab源码程序 > demos/travel.m
function travel(action)
%TRAVEL Traveling salesman problem demonstration.
% This demo animates the solution of the
% so-called "Traveling Salesman" problem.
% The problem is to form a closed circuit of a
% number of cities while traveling the shortest
% total distance along the way.
%
% Use the "Cities" popup menu to determine the
% number of cities to be visited. The "Start"
% and "Stop" buttons control the animation. Cities
% are chosen completely at random.
% Ned Gulley, 6-21-93
% Copyright 1984-2014 The MathWorks, Inc.
% Information regarding the play status will be held in
% the axis user data according to the following table:
play = 1;
stop = -1;
if nargin < 1,
action = 'initialize';
end;
switch action
case 'initialize',
oldFigNumber = watchon;
figNumber = figure( ...
'Name',getString(message('MATLAB:demos:wrldtrv:fig_TravelTheTravelingSalesmanProblem')), ...
'NumberTitle','off', ...
'Visible','off', ...
'Color', [0 0 0]);
axes( ...
'Units','normalized', ...
'Position',[0.05 0.05 0.75 0.90], ...
'Visible','off', ...
'NextPlot','add');
text(0,0,getString(message('MATLAB:demos:wrldtrv:LabelPressStartToSeeTravelingSalesmanDemo')), ...
'HorizontalAlignment','center');
axis([-1 1 -1 1]);
% ===================================
% Information for all buttons
labelColor = [0.8 0.8 0.8];
yInitPos = 0.90;
xPos = 0.85;
btnWid = 0.10;
btnHt = 0.10;
% Spacing between the button and the next command's label
spacing = 0.05;
% ====================================
% The CONSOLE frame
frmBorder = 0.02;
yPos = 0.05-frmBorder;
frmPos = [xPos-frmBorder yPos btnWid+2*frmBorder 0.9+2*frmBorder];
h = uicontrol( ...
'Style','frame', ...
'Units','normalized', ...
'Position',frmPos, ...
'BackgroundColor',[0.50 0.50 0.50]);
% ====================================
% The START button
btnNumber = 1;
yPos = 0.90-(btnNumber-1)*(btnHt+spacing);
labelStr = getString(message('MATLAB:demos:shared:LabelStart'));
cmdStr = 'start';
callbackStr = 'travel(''start'');';
% Generic button information
btnPos = [xPos yPos-spacing btnWid btnHt];
startHndl = uicontrol( ...
'Style','pushbutton', ...
'Units','normalized', ...
'Position',btnPos, ...
'String',labelStr, ...
'Interruptible','on', ...
'Callback',callbackStr);
% ====================================
% The CITIES popup button
btnNumber = 2;
yPos = 0.90-(btnNumber-1)*(btnHt+spacing);
textStr = getString(message('MATLAB:demos:wrldtrv:LabelCities'));
popupStr = reshape(' 15 20 25 30 35 40 45 50 ',4,8)';
% Generic button information
btnPos1 = [xPos yPos-spacing+btnHt/2 btnWid btnHt/2];
btnPos2 = [xPos yPos-spacing btnWid btnHt/2];
popupHndl = uicontrol( ...
'Style','text', ...
'Units','normalized', ...
'Position',btnPos1, ...
'String',textStr);
btnPos = [xPos yPos-spacing btnWid btnHt/2];
popupHndl = uicontrol( ...
'Style','popup', ...
'Value',4, ...
'Units','normalized', ...
'Position',btnPos2, ...
'String',popupStr);
% ====================================
% The STOP button
btnNumber = 3;
yPos = 0.90-(btnNumber-1)*(btnHt+spacing);
labelStr = getString(message('MATLAB:demos:shared:LabelStop'));
% Setting userdata to -1 (= stop) will stop the demo.
callbackStr = 'set(gca,''Userdata'',-1)';
% Generic button information
btnPos = [xPos yPos-spacing btnWid btnHt];
stopHndl = uicontrol( ...
'Style','pushbutton', ...
'Units','normalized', ...
'Position',btnPos, ...
'Enable','off', ...
'String',labelStr, ...
'Callback',callbackStr);
% ====================================
% The INFO button
labelStr = getString(message('MATLAB:demos:shared:LabelInfo'));
callbackStr = 'travel(''info'')';
infoHndl = uicontrol( ...
'Style','push', ...
'Units','normalized', ...
'Position',[xPos 0.20 btnWid 0.10], ...
'String',labelStr, ...
'Callback',callbackStr);
% ====================================
% The CLOSE button
labelStr = getString(message('MATLAB:demos:shared:LabelClose'));
callbackStr = 'close(gcf)';
closeHndl = uicontrol( ...
'Style','push', ...
'Units','normalized', ...
'Position',[xPos 0.05 btnWid 0.10], ...
'String',labelStr, ...
'Callback',callbackStr);
% Uncover the figure
hndlList = [startHndl popupHndl stopHndl infoHndl closeHndl];
set(figNumber, ...
'Visible','on', ...
'UserData',hndlList);
watchoff(oldFigNumber);
figure(figNumber);
case 'start',
WNumber = watchon;
axHndl = gca;
figNumber = gcf;
hndlList = get(figNumber,'Userdata');
startHndl = hndlList(1);
popupHndl = hndlList(2);
stopHndl = hndlList(3);
infoHndl = hndlList(4);
closeHndl = hndlList(5);
set([startHndl closeHndl infoHndl],'Enable','off');
set(stopHndl,'Enable','on');
set(axHndl,'Userdata',play);
set(popupHndl, 'Enable', 'off');
% ====== Start of Demo
% Travel problem
% This is the main program for the Traveling Salesman Problem.
% This function makes use of the function INPOLYGON
% Lay down a picture of the United States for graphic appeal.
load usborder.mat x y;
% The file usborder.mat contains a map of the US in the variables
% x and y
cla;
plot(x,y,'Color','cyan');
axis off;
axis([-0.1 1.5 -0.2 1.2]);
hold on;
drawnow;
nptsStr = get(popupHndl,'String');
nptsVal = get(popupHndl,'Value');
npts = str2double(nptsStr(nptsVal,:));
set(popupHndl, 'Enable', 'off');
% ...else generate the random cities to visit
X = [];
Y = [];
% Use the INPOLYGON routine to help find cities
n = 0;
while n < npts,
nx = rand*1.4;
ny = rand;
if inpolygon(nx,ny,x,y)
X = [X; nx];
Y = [Y; ny];
n = n+1;
end;
end;
xy = [X Y];
% Calculate the distance matrix for all of the cities
distmatrix = zeros(npts);
for count1 = 1:npts,
for count2 = 1:count1,
x1 = xy(count1,1);
y1 = xy(count1,2);
x2 = xy(count2,1);
y2 = xy(count2,2);
distmatrix(count1,count2) = sqrt((x1-x2)^2+(y1-y2)^2);
distmatrix(count2,count1) = distmatrix(count1,count2);
end;
end;
% Generate an initial random path between those cities
p = 1:npts;
newxy = xy(p,:);
newxy = [newxy; newxy(1,:)];
xdata = newxy(:,1);
ydata = newxy(:,2);
watchoff(WNumber);
plot(xdata,ydata,'r.','Markersize',24);
plothandle = plot(xdata,ydata,'yellow','LineWidth',2);
axis off;
drawnow;
len = LocalPathLength(p,distmatrix);
lenhist = len;
while (ishghandle(axHndl) == 1) && (get(axHndl,'Userdata') == play)
drawnow;
drawFlag = 0;
% Try a point for point swap
% ========================
swpt1 = floor(npts*rand)+1;
swpt2 = floor(npts*rand)+1;
swptlo = min(swpt1,swpt2);
swpthi = max(swpt1,swpt2);
order = 1:npts;
order(swptlo:swpthi) = order(swpthi:-1:swptlo);
pnew = p(order);
lennew = LocalPathLength(pnew,distmatrix);
if lennew < len,
p = pnew;
len = lennew;
drawFlag = 1;
end;
% ========================
% Try a single point insertion
% ========================
swpt1 = floor(npts*rand)+1;
swpt2 = floor((npts-1)*rand)+1;
order = 1:npts;
order(swpt1) = [];
order = [order(1:swpt2) swpt1 order((swpt2+1):(npts-1))];
pnew = p(order);
lennew = LocalPathLength(pnew,distmatrix);
if lennew < len,
p = pnew;
len = lennew;
drawFlag = 1;
end
if drawFlag,
newxy = xy(p,:);
newxy = [newxy; newxy(1,:)];
xdata = newxy(:,1);
ydata = newxy(:,2);
if ~ishghandle(plothandle)
% If plothandle is not valid, figure may have been deleted.
% Bail out in that case.
return;
end
set(plothandle,'XData',xdata,'YData',ydata);
drawnow;
end;
% ========================
end;
if ~ishghandle(figNumber)
% If figNumber is not valid, figure may have been deleted. Bail out
% in that case.
return;
end
% ====== End of Demo
set([startHndl closeHndl infoHndl],'Enable','on');
set(stopHndl,'Enable','off');
set(popupHndl, 'Enable', 'on');
case 'info',
helpwin(mfilename)
end; % if strcmp(action, ...
function total = LocalPathLength(p,distmatrix)
% Calculate current path length for traveling salesman problem.
% This function calculates the total length of the current path
% p in the traveling salesman problem.
npts = size(p,2);
% This is a vectorized distance calculation
%
% We're creating two vectors: p and p([end 1:(end-1)]
% The first is the list of first cities in any leg, and the second
% is the list of destination cities for that same leg.
% (the second vector is an element-shift-right version of the first)
%
% We then use column indexing into distmatrix to create a vector of
% lengths of each leg which can then be summed.
total = sum(distmatrix((p-1)*npts + p([end 1:(end-1)])));