图论算法基础之浅谈骑士巡逻问题（神经网络算法）与哈密顿路径

lee1892 · 发表于 2013-10-16 15:50

本帖最后由 lee1892 于 2013-10-17 08:57 编辑

结束之前

关于哈密顿路径：

其定义之前已经提到，对于普遍意义上而言的图，寻找哈密顿路径或是回路是一个NP完全（NP-Complete）问题，无论是有向图还是无向图。

有一些定理可以帮助判断其是否是存在哈密顿路径，比如：

Dirac：一个简单图，其顶点（Vertex）数量 n >=3，如果每个顶点的度（Degree，图论名词，不同于边 Edge）>= n/2，则存在哈密顿路径。

Ore：一个图，其顶点数量 n >=3，如果对于每一对邻接点对，其度之和 >= n，则存在哈密顿路径。

值得一提的是，旅行商问题的路径是一个特殊的哈密顿路径，参见会跑法师的帖子：http://club.excelhome.net/thread-688274-1-1.html

另外，与之相对应的欧拉路径（Eulerian Path），由著名的七桥问题衍生而来，即不重复的经过所有边的路径。

关于神经网络算法：

我也是初次接触这个，照着描述勉强作出来的。感觉：

1、收敛与否以及收敛速度与初始的随机值有很大关系，包括随机值的范围（0、1 貌似不是好的选择）和概率。

2、怀疑一次网络运行的结果，无论其是否收敛，能否作为下次运行时初始值的参考，以加速网络的收敛。如果确实有参考价值的话，那么就有点遗传的意思了。

3、这种算法应该很适合应用在节点间互相限制的问题，如拉丁方阵、数独等等，其效率如何有待测试。

以上。

lee1892 · 发表于 2013-10-16 16:00

本帖最后由 lee1892 于 2013-10-16 16:38 编辑

另外，对神经网络算法加了些功能，方便学习，有兴趣的同学可以下载附件：

骑士巡逻问题神经网络算法 Lee1892.rar (71.27 KB, 下载次数: 212)

参考动画：

补充内容 (2013-12-2 08:51):
附件中尝试次数标签和文本框在原位置有重复的两个，需要将上方的那个删除。

zhangweizhen · 发表于 2013-12-1 22:57

好帖子，收藏了，慢慢学习。

EXCEL江湖 · 发表于 2014-11-11 21:54

lee1892 发表于 2013-10-16 16:00
另外，对神经网络算法加了些功能，方便学习，有兴趣的同学可以下载附件：

下载学习了，高深！

汇铁 · 发表于 2015-4-25 18:58

没下载。路过。仰视。

tangbohucz · 发表于 2016-4-25 10:08

这样的情况能不能做出10x10，11x11,12x12,13x13,14x14,类似数独的这种表格？谢谢

天地有雪 · 发表于 2016-4-25 10:16

感谢楼主分享~~

risehub · 发表于 2016-5-29 01:22

高手在民间。。。。实在是高啊。

gprsfans1 · 发表于 2016-8-11 16:29

如何将各段链路读取到集合中，构造无向图。

LOSERKING · 发表于 2018-3-5 22:47

7X7有为什么没有显示

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

[原创] 图论算法基础 之 浅谈骑士巡逻问题（神经网络算法）与哈密顿路径

[原创] 图论算法基础之浅谈骑士巡逻问题（神经网络算法）与哈密顿路径