给定图G =（V, E）, 我们必须使用回溯法找到哈密顿回路。我们从任何说“ a”的任意顶点开始搜索。该顶点“ a”成为隐式树的根。我们局部解的第一个元素是要构造的哈密顿循环的第一个中间顶点。下一个相邻的顶点按字母顺序选择。如果在任何阶段任何任意顶点与顶点“ a”以外的任何顶点构成一个循环, 那么我们就说达到了死角。在这种情况下, 我们回溯一个步骤, 再次从选择另一个顶点开始搜索, 然后回溯部分中的元素。解决方案必须删除。如果获得了哈密顿循环, 则使用回溯的搜索成功。
示例：考虑图G中所示的曲线G =（V, E）。我们必须使用回溯法找到哈密顿回路。
文章图片
解决方案：首先, 我们从顶点“ a”开始搜索。这个顶点“ a”成为隐式树的根。
文章图片
接下来, 我们按顶点顺序（b, c, d）首先选择与“ a”相邻的顶点“ b”。
文章图片
接下来, 我们选择与“ b”相邻的“ c”。
文章图片
接下来, 我们选择与“ c”相邻的“ d”。
文章图片
接下来, 我们选择与“ d”相邻的“ e”。
文章图片
接下来, 我们选择与“ e”相邻的顶点“ f”。与“ f”相邻的顶点是d和e, 但它们已经访问过。因此, 我们得到了死胡同, 回溯了一步, 从部分解中删除了顶点“ f”。
文章图片
从回溯来看, 与“ e”相邻的顶点是b, c, d和f, 已经从中检查了顶点“ f”, 并且已经访问了b, c, d。因此, 我们又回溯了一步。现在, 与d相邻的顶点为e, 已经检查了e的f, 与“ f”的相邻顶点为d和e。如果’ e’ 顶点, 再次访问它们, 我们将进入死状态。因此, 我们再次回溯了一步。
现在, 与c相邻的是“ e”, 与“ e”相邻的是“ f”, 与“ f”相邻的是“ d”, 与“ d”相邻的是“ a”。在这里, 我们获得哈密顿循环, 因为除起始顶点“ a”以外的所有顶点仅被访问了一次。 （a-b-c-e-f -d-a）。
文章图片
文章图片
再次回溯
文章图片
【哈密??顿回路问题和回溯法】在这里, 我们已经生成了一个哈密顿电路, 但是也可以通过考虑另一个顶点来获得另一个哈密顿电路。
推荐阅读
- 子集和问题和回溯算法
- 动态规划与贪婪算法的区别
- 如何使用mod_evasive在Apache上防御DoS和DDoS（）
- 网站优化（减少服务器响应时间的7种方法）
- 在Linux服务器上监控网络带宽的最佳工具合集
- 17个Nmap命令以及Linux网络和系统管理员的示例
- 如何在Nginx中将HTTP重定向到HTTPS（分步指南）
- Tmux使用教程（如何安装和使用命令示例）
- 如何将CSV文件导入MySQL数据库（分步指南）