求助路径算法！

nyasen · 发表于 2015-5-19 17:00

本帖最后由 nyasen 于 2015-5-19 17:02 编辑

有一个迷宫，里面有12个房间，每个房间之间访问只能通过相邻的房间，才能进入。现在求教一个算法，可以获得任意房间之间访问，需要通过的房间编号。如从1号房间出发去5号房间，需要经过哪些房间？。可以不要求最短路径！

wzb5566 · 发表于 2015-5-19 17:55

这个问题看着很有意思，但是不知道怎么用vba解答，等高手！

lake2 · 发表于 2015-5-19 18:06

不求最短路径用穷举法就可以了

onlycxb · 发表于 2015-5-19 19:29

蚁群算法
下面文字来源于网络，主要使大家先了解一下蚁群算法，大致看一下即可，看的时候注意看一下蓝色部分的注解。

起源

蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

原理

各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐地更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。

　　为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。

然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！

yjh_27 · 发表于 2015-5-19 21:42

递归
列出全部路径

lee1892 · 发表于 2015-5-19 22:18

我以前出过一个主题贴有详细介绍
http://club.excelhome.net/thread-963987-1-1.html

yiyiyicz · 发表于 2015-5-20 06:26

1，做一个矩阵，行标、列标都是 1,2,3.。。。12
房间是相邻的为1，否则为0。比如行标1与列标4的交叉点为1（房间相邻）
2，对行中为1的列，再找为1的交叉点；检查这些交叉点所对应行中的1
反复几次，就可以找到路径了
这是直观的概念
数学中，可以通过矩阵变换和矩阵连乘，也就是有套路，可以找出路径。具体的可以看看离散数学的教材

香川群子 · 发表于 2015-5-20 08:37

根据楼主相邻房间表，拓扑画出各个房间的平面图：

香川群子 · 发表于 2015-5-20 08:54

yjh_27 发表于 2015-5-19 21:42
递归
列出全部路径

如果对递归进行路径筛选，防止冗余步骤，那么最短有效路径就只有1条：
1->4->5

做法很简单，仅需核对该路径节点是否已经在上一层递归中出现过。
如已经出现就排除。

nyasen · 发表于 2015-5-20 09:21

多谢诸位，我学习学习6楼的代码先

		自动登录	找回密码
密码			免费注册

[求助] 求助路径算法！

评分