关于“一笔画问题”

xjzuo

由前面我的一个关于生成网格的帖子, 我又想到了另一个问题, 即“一笔画”问题。
      “一笔画”问题可以追溯到二百年前的一个著名问题：哥尼斯堡七桥问题。当时年仅20岁的大数学家欧拉经过思考发现: 能一笔画的图形只有两类：一类是所有的点都是偶点;另一类是只有二个奇点的图形。
注:一个顶点如果有偶数条边联结它，就称为偶点；如果有奇数条边联接它的，就称为奇点。

       一笔画问题的规律
1)凡是由偶点组成的连通图都可以一笔画成，画时可以从一个偶点出发，到这个偶点结束．
2)凡是只有两个奇点(其余均为偶点)的连通图一定可以一笔画成，画时必须以一个奇点为起点，另一个奇点为终点．

       显然,正方格子也是不能一笔画出的图形;但我们可以这样考虑:若允许重复,如何能用尽可能少的重复来画出正方格子呢? 这其实已经相当于是一个最短路问题了,就象我们常见到的邮递员路线问题(TSP).
       更进一步的研究可能就要涉及到图论了,常见的两种算法是Dijkstra算法和Floyd算法. 当然,现在也有不少人用GA(遗传算法)和SSA(模拟退火算法)研究过此类问题.

        如果对此问题有兴趣,欢迎大家参与讨论,可以试着找出一笔画问题的更多规律,也可以针对上面我提到的几个方面发表自己的见解或算法.
(另注:本贴也纯粹是引导大家参与讨论,提高大家学习的兴趣)

xjzuo

下面这段程序是利用Dijkstra算法求最短路径，可能学过计算数学的人会有一定印象，也希望那些参加数学建模竞赛的人能用得上。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all
clc
M=10000;
a(1,:)=[0,50,M,40,25,10]; %%%生成邻接矩阵
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
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=[index1,temp];
   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 编辑 ]

lxq

好象可以用于路径规划


正方格子也是不能一笔画出的图形?

正方格子的四个顶点不就是由两条线连接么?

xjzuo

to lxq: 谢谢参与讨论．你可以再看一下我的第一个帖子，正方格子(网格)不能一笔画，是因为存在3个以上的奇点．你说的恰好不是奇点，而是偶点．:@)
后来我想了一下，每增加两个奇点，我们就需要多画一笔，n对奇点，我们总共要画n笔．
所以算一下正方格子的奇点数目，我们就知道要很多笔才能画完正方格子．

[ 本帖最后由 xjzuo 于 2007-1-19 15:27 编辑 ]

lxq

稍微明白了点
开始以为是单个的格子

现在想知道 一笔画问题能否用于 机器人的路径规划呢?

n对奇点，我们总共要画n笔?

假如把N对奇点连在一起  就如2N个电线杠 它们之间的连线怎么算呢?

xjzuo

＂画时必须以一个奇点为起点，另一个奇点为终点＂．
当然，既然是最短路问题，显然我们应该连最短的(路)线．
对于网格，其实只要在边界(网格的奇点都在边界上)的每一对相邻奇点间连一根线就行了．

[ 本帖最后由 xjzuo 于 2007-1-19 15:58 编辑 ]

happy

这是一个挺有意思的问题，以前在看代数拓扑学的时候专门专门看过这个问题，不过时间长了忘得七七八八了

基本思路是：把问题用矩阵表述出来，然后计算每个点的度数，再统计奇点个数，最后搜索路线