W
wdl
Unregistered / Unconfirmed
GUEST, unregistred user!
怎末设计迷宫算法,我看了一个basic的,但看不懂,很抽象.那位能提供比较详细
的资料
的资料
D
denglt
Unregistered / Unconfirmed
GUEST, unregistred user!
你是否能说清楚点你所提出的问题。
S
shirker
Unregistered / Unconfirmed
GUEST, unregistred user!
你所提出的问题确实有的模糊，曾记得当时我遇到一个迷宫的问题，用的二唯数组
来表示迷宫：用"1"表示道路不通，用"0"表示通．如下
１ １ ０ １ １ １
０ ０ １ ０ １ １
１ ０ ０ ０ １ ０
１ ０ １ １ ０ ０
０ １ １ ０ １ １
１ ０ ０ １ １ ０
假设用上面的矩阵来表示迷宫(M[6][6]),"0"表示道路通，"1"表不通，为了运算的
方便，四周全用"1"包围，此时迷宫变成如下（M[7][7]):
１ １ １ １ １ １ １ １
１ １ １ ０ １ １ １ １
１ ０ ０ １ ０ １ １ １
１ １ ０ ０ ０ １ ０ １
１ １ ０ １ １ ０ ０ １
１ ０ １ １ ０ １ １ １
１ １ ０ ０ １ １ ０ １
１ １ １ １ １ １ １ １
此时迷宫的算法变得很容易理解了．
来表示迷宫：用"1"表示道路不通，用"0"表示通．如下
１ １ ０ １ １ １
０ ０ １ ０ １ １
１ ０ ０ ０ １ ０
１ ０ １ １ ０ ０
０ １ １ ０ １ １
１ ０ ０ １ １ ０
假设用上面的矩阵来表示迷宫(M[6][6]),"0"表示道路通，"1"表不通，为了运算的
方便，四周全用"1"包围，此时迷宫变成如下（M[7][7]):
１ １ １ １ １ １ １ １
１ １ １ ０ １ １ １ １
１ ０ ０ １ ０ １ １ １
１ １ ０ ０ ０ １ ０ １
１ １ ０ １ １ ０ ０ １
１ ０ １ １ ０ １ １ １
１ １ ０ ０ １ １ ０ １
１ １ １ １ １ １ １ １
此时迷宫的算法变得很容易理解了．
J
Jams
Unregistered / Unconfirmed
GUEST, unregistred user!
>>
C
cAkk
Unregistered / Unconfirmed
GUEST, unregistred user!
wdl:能把你的basic版本的代码给我一份吗? cakk2000@163.net
曹
曹晓钢
Unregistered / Unconfirmed
GUEST, unregistred user!
到底是走迷宫算法还是生成迷宫算法？
走迷宫就是深度优先；
或者我还用过别的方法，就是填死胡同。发现有一个点三面都是不能走的，就把它填掉，同时继续测试它附近的那个新的死胡同。
二者各有利弊。
生成迷宫，要看你是想生成什么样的。
走迷宫就是深度优先；
或者我还用过别的方法，就是填死胡同。发现有一个点三面都是不能走的，就把它填掉，同时继续测试它附近的那个新的死胡同。
二者各有利弊。
生成迷宫，要看你是想生成什么样的。
H
Hexi
Unregistered / Unconfirmed
GUEST, unregistred user!
>>
C
cytown
Unregistered / Unconfirmed
GUEST, unregistred user!
@_@
W
wdl
Unregistered / Unconfirmed
GUEST, unregistred user!
烦劳各位了!
我想求解的是生成算法.
只有一条通路,比较聪明,不会生成交叉分支.
我说的算法是一个外国人的,很有年头了,是我在图书馆翻倒的.
我们学校只有这样得书 :-<
相当难以理解,但我认为这是个好算法,无奈看不懂 :-<
那位想要,我下周给过来(一周一小时,多了不行money少)
我想求解的是生成算法.
只有一条通路,比较聪明,不会生成交叉分支.
我说的算法是一个外国人的,很有年头了,是我在图书馆翻倒的.
我们学校只有这样得书 :-<
相当难以理解,但我认为这是个好算法,无奈看不懂 :-<
那位想要,我下周给过来(一周一小时,多了不行money少)
W
wdl
Unregistered / Unconfirmed
GUEST, unregistred user!
金钱少,不能常上网,抱歉!!!
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
小case!
我高中时专搞这种问题(我是省奥林匹克竞赛一等奖 ^-^ (1992年)
那时 我用的是Turbo Pascal 6.0;大学时转向C/C++;
我是 Borland 公司 的 坚决拥护着, 最反感 "B.该死"的产品!
这个问题最简单的算法 有两个:
1. 深度优先搜索 (或者 搜索回朔: 如果要找最短路径,
需要遍历整个解空间
2. 宽度优先搜索:第一个解就是最优解.
(真累! )
1. dfs 递归算法
program dfs
var
a:array[1..n,1..m] of integer;
vx:array[1..4] of integer =[0,1,0,-1];
vy:array[1..4] of integer =[1,0,-1,0] ;
x,y:integer;
pathx,pathy :array[1..100] of integer;
procedure go(c:integer);
var i:integer;
begin
for i:=1 to 4do
if a[x+vx,y+vy]=1 and x,y 不出界 then
begin
x:=x+vx ;
y:=y+vy;
a[x,y]:=2;
pathx[c]:=x;
pathy[c]:=y;
if x=x0 and y=y0 then
输出解 { 或者 保存 较优解)
else
go(c+1);
a[x,y]=1;
x:=x-vx[c];
y:=y-vy[c];
end
begin
初始化 a {0 为墙, 12为路),x,y,
go(1);
输出 最优解;
end.
2. wfs
program wfs
type node=结点;
var q1,q2:node
begin
初始化 根节点, q1,q2;
repeat
从q1 中取出节点
for i:=1 to 4do
begin
生成子节点 t1 ,
如果已经到出口, 跳出
if t1 not in q2
append t1 to q1;
end
父节点 入 q2
until 队列空
如果找到解, 由最后一个节点上溯至根节点,
记下路径, 就是最优解.
释放 q1,q2;
end .
wfs 中 如果对q1 的入队次序加以优化, 即可
派生出其他算法 如 A 算法, A* 算法
手腕都酸了, 好意思不给我分数吗?
后记...........
好多年没写过这样的程序了,一时兴起, 写了这些算法;
这么多年了 一直用 RAD 工具 , 写的都是 豆腐快似的
程序, 在我的心目中 编程最大的乐趣在于设计了好的算法:
优美的, 简明的 , 高效的 算法;
现在的新一代程序员似乎
已经忘了什么是"算法"!
好怀念高中的Turbo Pascal 与 大学的 Turbo C/C++ !!
我高中时专搞这种问题(我是省奥林匹克竞赛一等奖 ^-^ (1992年)
那时 我用的是Turbo Pascal 6.0;大学时转向C/C++;
我是 Borland 公司 的 坚决拥护着, 最反感 "B.该死"的产品!
这个问题最简单的算法 有两个:
1. 深度优先搜索 (或者 搜索回朔: 如果要找最短路径,
需要遍历整个解空间
2. 宽度优先搜索:第一个解就是最优解.
(真累! )
1. dfs 递归算法
program dfs
var
a:array[1..n,1..m] of integer;
vx:array[1..4] of integer =[0,1,0,-1];
vy:array[1..4] of integer =[1,0,-1,0] ;
x,y:integer;
pathx,pathy :array[1..100] of integer;
procedure go(c:integer);
var i:integer;
begin
for i:=1 to 4do
if a[x+vx,y+vy]=1 and x,y 不出界 then
begin
x:=x+vx ;
y:=y+vy;
a[x,y]:=2;
pathx[c]:=x;
pathy[c]:=y;
if x=x0 and y=y0 then
输出解 { 或者 保存 较优解)
else
go(c+1);
a[x,y]=1;
x:=x-vx[c];
y:=y-vy[c];
end
begin
初始化 a {0 为墙, 12为路),x,y,
go(1);
输出 最优解;
end.
2. wfs
program wfs
type node=结点;
var q1,q2:node
begin
初始化 根节点, q1,q2;
repeat
从q1 中取出节点
for i:=1 to 4do
begin
生成子节点 t1 ,
如果已经到出口, 跳出
if t1 not in q2
append t1 to q1;
end
父节点 入 q2
until 队列空
如果找到解, 由最后一个节点上溯至根节点,
记下路径, 就是最优解.
释放 q1,q2;
end .
wfs 中 如果对q1 的入队次序加以优化, 即可
派生出其他算法 如 A 算法, A* 算法
手腕都酸了, 好意思不给我分数吗?
后记...........
好多年没写过这样的程序了,一时兴起, 写了这些算法;
这么多年了 一直用 RAD 工具 , 写的都是 豆腐快似的
程序, 在我的心目中 编程最大的乐趣在于设计了好的算法:
优美的, 简明的 , 高效的 算法;
现在的新一代程序员似乎
已经忘了什么是"算法"!
好怀念高中的Turbo Pascal 与 大学的 Turbo C/C++ !!
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
对于曹晓刚的 填胡同 算法, 我有一点补充:
如果碰到 "大厅" , 此算法酒会实失效
如 00000
11110
01110
01111
00000
如果碰到 "大厅" , 此算法酒会实失效
如 00000
11110
01110
01111
00000
E
Energy
Unregistered / Unconfirmed
GUEST, unregistred user!
>我是省奥林匹克竞赛一等奖??
哪一种
(Energy曾被那些题目搞的象猪一样笨）
哪一种
(Energy曾被那些题目搞的象猪一样笨）
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
Energy:
当然是信息学(计算机了);
多年不炼, 都忘光了!
-----------------------------
对于曹晓刚的 填胡同 算法, 我有一点补充:
如果碰到 "大厅" , 此算法酒会实失效
如 00000
11110
01110
01111
00000
找到大厅(四个相邻的1) , 填上一角即可
11 12
11 -> 11
当然是信息学(计算机了);
多年不炼, 都忘光了!
-----------------------------
对于曹晓刚的 填胡同 算法, 我有一点补充:
如果碰到 "大厅" , 此算法酒会实失效
如 00000
11110
01110
01111
00000
找到大厅(四个相邻的1) , 填上一角即可
11 12
11 -> 11
G
gongming
Unregistered / Unconfirmed
GUEST, unregistred user!
张国龙的算法很“经典”，但好像有点文不对题。
我有一个思路，先讲一讲，如果需要，程序以后再贴：
1 把“地图”边界染色。
二维数组的边缘被出入口分成两段，分别
染成“1”和“2”，其余元素均为“0”。
2 用另一数组储存各位置的权重。
“0”处为0，“1”或“2”处按所邻接
的“0”的个数配权。（邻接“0”的越
多，权重越大）
3 按权重随机取一不为“0”的元素，将其周围（随机找）
的“0”变为与自身相同的标志值。
应保证新生成的点一定与三个“0”邻接。
4 返回2 循环，直到无处可再生成新点为止。
5 非“0”处为“墙”，“0”处为通道，可以有“大
厅”。完成。
这个算法绝不经典，是我自己想出来的。
至于竞赛成绩，我就不说了。
我有一个思路，先讲一讲，如果需要，程序以后再贴：
1 把“地图”边界染色。
二维数组的边缘被出入口分成两段，分别
染成“1”和“2”，其余元素均为“0”。
2 用另一数组储存各位置的权重。
“0”处为0，“1”或“2”处按所邻接
的“0”的个数配权。（邻接“0”的越
多，权重越大）
3 按权重随机取一不为“0”的元素，将其周围（随机找）
的“0”变为与自身相同的标志值。
应保证新生成的点一定与三个“0”邻接。
4 返回2 循环，直到无处可再生成新点为止。
5 非“0”处为“墙”，“0”处为通道，可以有“大
厅”。完成。
这个算法绝不经典，是我自己想出来的。
至于竞赛成绩，我就不说了。
S
SuperMMX
Unregistered / Unconfirmed
GUEST, unregistred user!
好象大家搞错了，人家要的是 生成 算法
不是 求解 算法
不是 求解 算法
曹
曹晓钢
Unregistered / Unconfirmed
GUEST, unregistred user!
是啊，人家要得是生成算法。
BTW,我的那个笨算法，最后还是要用深度或者宽度搜索的，因为不管最后填成怎么
样，总要给出结果吧？所以，有大厅或者环路都无所谓。只不过是可以减少搜索的
开销罢了。其实仔细想一想，也不见得会节省。只有在多次岔路，就是岔路上还有岔
路的情况多次发生的时候，才稍微有点用，而且效率提高不多。
否则，甚至有可能效率下降。
生成算法么，可以用这个方法倒过来想，来挖路啊。
BTW,我的那个笨算法，最后还是要用深度或者宽度搜索的，因为不管最后填成怎么
样，总要给出结果吧？所以，有大厅或者环路都无所谓。只不过是可以减少搜索的
开销罢了。其实仔细想一想，也不见得会节省。只有在多次岔路，就是岔路上还有岔
路的情况多次发生的时候，才稍微有点用，而且效率提高不多。
否则，甚至有可能效率下降。
生成算法么，可以用这个方法倒过来想，来挖路啊。
W
wrench
Unregistered / Unconfirmed
GUEST, unregistred user!
生成迷宫嘛，先用随机数弄出一条路来，
然后在路上找几个点，随便弄点分支出来，
不知这样生成的迷宫合要求否？
要考试了，来不及写一个出来。
BTW,话说我高中时也是做这种题目长大的
然后在路上找几个点，随便弄点分支出来，
不知这样生成的迷宫合要求否？
要考试了，来不及写一个出来。
BTW,话说我高中时也是做这种题目长大的
G
gongming
Unregistered / Unconfirmed
GUEST, unregistred user!
补充几句：
关于上次的帖子：
1、在生成新“墙”的时候，应判断“前方”五个位置均为“0”。
2、如果需要有多条通路，可以在第一步时在中间加几个“3”、“4”之类。
3、若需要从迷宫中间走到外面，可以少一个入口，然后再“大厅”的中间加
个“-1”之类，生成新“墙”时注意一下就可以了。
关于上次的帖子：
1、在生成新“墙”的时候，应判断“前方”五个位置均为“0”。
2、如果需要有多条通路，可以在第一步时在中间加几个“3”、“4”之类。
3、若需要从迷宫中间走到外面，可以少一个入口，然后再“大厅”的中间加
个“-1”之类，生成新“墙”时注意一下就可以了。
L
LuckyGrass
Unregistered / Unconfirmed
GUEST, unregistred user!
我的主页上有一个生成迷宫的程序http://luckygrass.t500.net