[Coursera] Design and Analysis of Algorithm, Part 2 [Week 5]

Shuang7 发表于 2013-10-12 00:30
我感觉自己也没有做什么优化，循环还是那么多层。。不知道区别是不是1:我只算到了n=24，你算了25？（这样 ...

我也是C++

你只算到24个城市，那怎么求出这题25个城市的最短路径？

我好像没用Gosper's Hack，我只通过combinatorial number system的计算方法把idx1换算到一个整型数组里面，数组里面保存的是这个{S}的所有城市编号，然后在这个数组里面遍历选j，再构成一个S-{j}的新数组，然后用这个包含S-{j}的数组通过combinatorial number system换算成新的idx2
这样计算就是A[0or1][idx1][j] = min(A[1or0][idx2][k])
感觉这里做繁了，耗时多

PS 版主忘记加学分了

圆梦梦剧场 发表于 2013-10-12 09:35
我也是C++

你只算到24个城市，那怎么求出这题25个城市的最短路径？

那怎么求出这题25个城市的最短路径？按照提示，可以把他们都画出来，然后分析一下哪个城市一定会在哪两个城市之间，然后把这个城市去掉了算，算完了再加回去。。

诶，再给我200M内存25个城市就出来了= =|