哈密​​顿回路问题和回溯法

给定图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)。

哈密​​顿回路问题
哈密​​顿回路问题

再次回溯

哈密​​顿回路问题

在这里, 我们已经生成了一个哈密顿电路, 但是也可以通过考虑另一个顶点来获得另一个哈密顿电路。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?