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

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

再次回溯

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