声振论坛

 找回密码
 我要加入

QQ登录

只需一步,快速开始

查看: 2744|回复: 6

[综合讨论] 关于“一笔画问题”

[复制链接]
发表于 2007-1-18 13:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?我要加入

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

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

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

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

使用道具 举报

 楼主| 发表于 2007-1-18 18:55 | 显示全部楼层
下面这段程序是利用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 编辑 ]
发表于 2007-1-19 15:13 | 显示全部楼层
好象可以用于路径规划


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

正方格子的四个顶点不就是由两条线连接么?
 楼主| 发表于 2007-1-19 15:26 | 显示全部楼层

回复

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

[ 本帖最后由 xjzuo 于 2007-1-19 15:27 编辑 ]
发表于 2007-1-19 15:38 | 显示全部楼层
稍微明白了点
开始以为是单个的格子

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

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

假如把N对奇点连在一起  就如2N个电线杠 它们之间的连线怎么算呢?
 楼主| 发表于 2007-1-19 15:53 | 显示全部楼层
"画时必须以一个奇点为起点,另一个奇点为终点".
当然,既然是最短路问题,显然我们应该连最短的(路)线.
对于网格,其实只要在边界(网格的奇点都在边界上)的每一对相邻奇点间连一根线就行了.

[ 本帖最后由 xjzuo 于 2007-1-19 15:58 编辑 ]
发表于 2007-1-21 14:11 | 显示全部楼层
这是一个挺有意思的问题,以前在看代数拓扑学的时候专门专门看过这个问题,不过时间长了忘得七七八八了

基本思路是:把问题用矩阵表述出来,然后计算每个点的度数,再统计奇点个数,最后搜索路线
您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-11-14 06:03 , Processed in 0.060880 second(s), 17 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表