|
|
49#
楼主 |
发表于 2017-3-31 17:27
|
只看该作者
来自：美国
永远的呱哥哥 发表于 2017-3-31 15:40
Dijstra对于这个问题并没有什么帮助啊，所有路线的权重都一样也不需要求最短路径，应该是salesman问题，不 ...
对的Dijkstra不可行，我一开始想用Dijkstra是感觉可以将每条直线上的格子数表示为权重，但是想了一分钟后发现这问题根本不是最短路径问题，因为你无论如何遍历你的路径长度永远等于25-障碍数，所以放弃了
然后拓扑排序的话有点interesting，我比较初步的想法是将每个转折点作为node分别用记录它们的入度和neighbor？就是neighbor数组求起来可能有点麻烦，一个点它对应的各个方向所有的临界点都是他的neighbor，不过，值得一试，就是时间复杂度可能还会是O（n^2）
动态规划是我码好dfs之后就想做的，但是有三个方面：一动态规划在2d网格上的时间复杂度很难优于n^2；二是动态规划只能告诉你从某点出发到某点是否可行，不能记录中间的决策，即转折点的坐标；三是楼主真的想不到状态转移方程会是哪样…… 我觉得光凭这几点还不足以ban掉动态规划，毕竟我一直没学好。。。
salesman我还真没想过，回头看看！！！
然后其实从时间复杂度角度分析的话，比o（n^2）优的无非两种，要么线性时间复杂度，这个绝对不可能，你肯定是要检查每个点的可能性，检查这个点的时间不可能为O（1）。那么另外一种就是O（nlogn）了。log(n)的话我只想到了binary search，但是这个问题完全看不出来和二分法有什么关系。。
我怀疑这题的最优时间复杂度就是O（n^2），明天去请教一下大神。。。 |
|
楼主: Sarisoul
发表于 2017-3-31 16:58
虽然看不懂！可是光看这么多字也觉得厉害啊！
