关于“一笔画问题”
由前面我的一个关于生成网格的帖子, 我又想到了另一个问题, 即“一笔画”问题。“一笔画”问题可以追溯到二百年前的一个著名问题：哥尼斯堡七桥问题。当时年仅20岁的大数学家欧拉经过思考发现: 能一笔画的图形只有两类：一类是所有的点都是偶点;另一类是只有二个奇点的图形。
注:一个顶点如果有偶数条边联结它，就称为偶点；如果有奇数条边联接它的，就称为奇点。
一笔画问题的规律
1)凡是由偶点组成的连通图都可以一笔画成，画时可以从一个偶点出发，到这个偶点结束．
2)凡是只有两个奇点(其余均为偶点)的连通图一定可以一笔画成，画时必须以一个奇点为起点，另一个奇点为终点．
显然,正方格子也是不能一笔画出的图形;但我们可以这样考虑:若允许重复,如何能用尽可能少的重复来画出正方格子呢? 这其实已经相当于是一个最短路问题了,就象我们常见到的邮递员路线问题(TSP).
更进一步的研究可能就要涉及到图论了,常见的两种算法是Dijkstra算法和Floyd算法. 当然,现在也有不少人用GA(遗传算法)和SSA(模拟退火算法)研究过此类问题.
如果对此问题有兴趣,欢迎大家参与讨论,可以试着找出一笔画问题的更多规律,也可以针对上面我提到的几个方面发表自己的见解或算法.
(另注:本贴也纯粹是引导大家参与讨论,提高大家学习的兴趣) 下面这段程序是利用Dijkstra算法求最短路径，可能学过计算数学的人会有一定印象，也希望那些参加数学建模竞赛的人能用得上。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all
clc
M=10000;
a(1,:)=; %%%生成邻接矩阵
a(2,:)=;
a(3,:)=;
a(4,:)=;
a(5,:)=;
a(6,:)=zeros(1,6);
a=a+a';
pb(1:length(a))=0;
pb(1)=1;
index1=1;
index2=ones(1,length(a));
d(1:length(a))=M;
d(1)=0;
temp=1;
while sum(pb)<length(a)
tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+a(temp,tb));
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=;
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index;
end
d, index1, index2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[ 本帖最后由 xjzuo 于 2007-1-18 18:58 编辑 ] 好象可以用于路径规划
正方格子也是不能一笔画出的图形?
正方格子的四个顶点不就是由两条线连接么?
回复
to lxq: 谢谢参与讨论．你可以再看一下我的第一个帖子，正方格子(网格)不能一笔画，是因为存在3个以上的奇点．你说的恰好不是奇点，而是偶点．:@)后来我想了一下，每增加两个奇点，我们就需要多画一笔，n对奇点，我们总共要画n笔．
所以算一下正方格子的奇点数目，我们就知道要很多笔才能画完正方格子．
[ 本帖最后由 xjzuo 于 2007-1-19 15:27 编辑 ] 稍微明白了点
开始以为是单个的格子
现在想知道 一笔画问题能否用于 机器人的路径规划呢?
n对奇点，我们总共要画n笔?
假如把N对奇点连在一起就如2N个电线杠 它们之间的连线怎么算呢? ＂画时必须以一个奇点为起点，另一个奇点为终点＂．
当然，既然是最短路问题，显然我们应该连最短的(路)线．
对于网格，其实只要在边界(网格的奇点都在边界上)的每一对相邻奇点间连一根线就行了．
[ 本帖最后由 xjzuo 于 2007-1-19 15:58 编辑 ] 这是一个挺有意思的问题，以前在看代数拓扑学的时候专门专门看过这个问题，不过时间长了忘得七七八八了
基本思路是：把问题用矩阵表述出来，然后计算每个点的度数，再统计奇点个数，最后搜索路线
页:
[1]