有人解释下DP解traveling salesman问题么？ - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 有人解释下DP解traveling salesman问题么？

相关主题
● 今天的一道google电面题目	● 来一题
● G面试题，很难	● 走迷宫的时间复杂度是多少？谢谢
● travelling salemen problem有什么好的解法吗？	● Google 电面面经
● 一个方阵途径问题，有点类似 travelling salesman problem	● splunk面经，攒人品
● 一道面试算法题	● 请问：解 Sudoku 可以用什么算法？
● boggle game是不是只有backtracking的解法？	● 微软面试题一道
● 写了一个Queens的backtrack 大牛帮我看看	● 一道算法问题求教。
● suduku solver这道题写代码有点难啊。	● 问一题

相关话题的讨论汇总
话题: dp话题: salesman话题: traveling话题: 解释话题: 问题

进入JobHunting版参与讨论

1

(共1页)

k********n 发帖数: 21	1 谢谢！
k********n 发帖数: 21	2 就是动态规划解货郎巡回问题？怎么动规呢？看了几个版本，都不是很清楚，复杂度还很高啊？这个问题的最低复杂度是多少呢？谢谢！【在 k********n 的大作中提到】 : 谢谢！
z*j 发帖数: 42	3 Co-ask. thanks TSP is in NPC? I can only think of backtracking.
h**6 发帖数: 4160	4 即使用DP，也只是把n!降为2^n*n^2 据说bound and branch很快
k********n 发帖数: 21	5 then how does DP work?? Thanks!

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 问一题	● 一道面试算法题
● 讨论一道图论题	● boggle game是不是只有backtracking的解法？
● 0/1 Knapsack问题Linear Space的算法可以实现Backtrack吗？	● 写了一个Queens的backtrack 大牛帮我看看
● 转一些我blog上以前总结题目的日记(二)	● suduku solver这道题写代码有点难啊。
● 今天的一道google电面题目	● 来一题
● G面试题，很难	● 走迷宫的时间复杂度是多少？谢谢
● travelling salemen problem有什么好的解法吗？	● Google 电面面经
● 一个方阵途径问题，有点类似 travelling salesman problem	● splunk面经，攒人品

相关话题的讨论汇总
话题: dp话题: salesman话题: traveling话题: 解释话题: 问题

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)