ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: lee1892

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

[复制链接]

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-10-16 15:50 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖已被收录到知识树中,索引项:
本帖最后由 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、这种算法应该很适合应用在节点间互相限制的问题,如拉丁方阵、数独等等,其效率如何有待测试。

以上。

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-10-16 16:00 | 显示全部楼层
本帖最后由 lee1892 于 2013-10-16 16:38 编辑

另外,对神经网络算法加了些功能,方便学习,有兴趣的同学可以下载附件: 骑士巡逻问题 神经网络算法 Lee1892.rar (71.27 KB, 下载次数: 208)


参考动画:
Updated.gif

Updated-1.gif

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

TA的精华主题

TA的得分主题

发表于 2013-12-1 22:57 | 显示全部楼层
好帖子,收藏了,慢慢学习。

TA的精华主题

TA的得分主题

发表于 2014-11-11 21:54 | 显示全部楼层
lee1892 发表于 2013-10-16 16:00
另外,对神经网络算法加了些功能,方便学习,有兴趣的同学可以下载附件:

下载学习了,高深!

TA的精华主题

TA的得分主题

发表于 2015-4-25 18:58 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2016-4-25 10:08 | 显示全部楼层
这样的情况能不能做出10x10,11x11,12x12,13x13,14x14,类似数独的这种表格?谢谢

TA的精华主题

TA的得分主题

发表于 2016-4-25 10:16 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2016-5-29 01:22 | 显示全部楼层
高手在民间。。。。实在是高啊。

TA的精华主题

TA的得分主题

发表于 2016-8-11 16:29 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2018-3-5 22:47 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
7X7有为什么没有显示
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-29 00:09 , Processed in 0.047976 second(s), 8 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

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