本文介绍了什么是动态规划算法寻找一个汉密尔顿的周期在图表中?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

什么是动态规划算法寻找一个汉密尔顿的周期在一个无向图?我看到的地方,存在一个算法为O(n * 2 ^ n)的时间complextity

What is dynamic programming algorithm for finding a Hamiltonian cycle in a undirected graph?I have seen somewhere that there exists a algorithm with O(n*2^n) time complextity

推荐答案

的确存在O(N2 )的动态编程查找汉密尔顿周期算法。这个想法,这是一个普遍的一种可以减少许多为O(n!)回溯的方法来为O(n 2 )或O(N2 )(在使用更多内存)的成本,是考虑的子是的设置与指定的终点的。

There is indeed an O(n2) dynamic-programming algorithm for finding Hamiltonian cycles. The idea, which is a general one that can reduce many O(n!) backtracking approaches to O(n2) or O(n2) (at the cost of using more memory), is to consider subproblems that are sets with specified "endpoints".

在这里,因为你想有一个周期,你可以在任何顶点开始。所以解决的,称之为 X 。子问题是:对于一个给定的取值顶点 v 取值,在那里开始 X 并办理取值的所有顶点的路径,从而结束在 v ?调用这个,比方说, POSS [S] [V]

Here, since you want a cycle, you can start at any vertex. So fix one, call it x. The subproblems would be: "For a given set S and a vertex v in S, is there a path starting at x and going through all the vertices of S, ending at v?" Call this, say, poss[S][v].

与最有活力的规划问题,一旦你定义的子问题,其余是显而易见的:遍历所有的2 设置任何增加为了顶点S,并在每个各V如S,可以计算 POSS [S] [V] 为:

As with most dynamic programming problems, once you define the subproblems the rest is obvious: Loop over all the 2 sets S of vertices in any "increasing" order, and for each v in each such S, you can compute poss[S][v] as:

POSS [S] [V] =(存在一些 U S中,使得POSS [S&负; {V}] [U]为True和边缘 U-> v 存在)

最后,有一个哈密顿圈当且仅当有一个顶点 v ,使得边缘 V-> X 存在且 POSS [S] [V] 为真,其中取值是集所有顶点(除 X ,这取决于你如何定义它)。

Finally, there is a Hamiltonian cycle iff there is a vertex v such that an edge v->x exists and poss[S][v] is True, where S is the set of all vertices (other than x, depending on how you defined it).

如果你只想确定是否存在与否,使实际的汉密尔顿的周期,而不是​​ POSS [S] [V] 存储实际 U ,使得有可能,而不是仅仅true或false;这样你可以追溯的路径在最后。

If you want the actual Hamiltonian cycle instead of just deciding whether one exists or not, make poss[S][v] store the actual u that made it possible instead of just True or False; that way you can trace back a path at the end.

这篇关于什么是动态规划算法寻找一个汉密尔顿的周期在图表中?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-09 17:00