作者:
eggy1018 (羅密æèˆ‡è±¬éŽå¤œ)
2018-09-24 20:55:00因为是要用tsp的问题解Hamilton cycle, 所以是由Hamilton cycle reduce到 TSP,reduces 后的new graph G’一定存在Hamilton cycle, 令原来Hamilton cycle 的问题为G(V,E) -> G’(V,E’), 其中E是完全图的边。 因为Hamiltoncycle 存在G中,所以令里面的edge weight=0(即原来属于E的边), 其他的为1。 因此解完TSP的同时,因为Hamilton cycle 的边在E中,又因为E的edge weight=0, 所以cost为0, 若不为0则表示没Hamilton cycle因为可以用poly time Algo 验证,加上可以由Hamilton cycle reduced to TSP,所以TSP是NP complete