s*****i
发帖数: 32 | 1 有一个gym，用block表示。里面有健身器材，还有障碍物。让找一个最佳的位
置放置椅子，使得椅子到所有健身器材的曼哈顿距离最短。
有障碍物，应该是NP hard。难道写一个brute force吗？这题的考点在哪里？ |
t********e
发帖数: 344 | |
k****s
发帖数: 16 | 3
kmeans 肯定不work啊。 mean用不了，还有障碍物。
距离肯定得用A* search吧.
我觉得应该
1. 选个好初始点
2. 算出到各个器材的距离 （用A*）
3. 然后新的cost function是到所有器材距离的和。
4. 再看4个可移动的方向哪个可以减少cost function （新的距离应该不需要重新计算）
5. repeat 4， 直到cost function不减少，则停止。
应该不保证收敛到全局最优。
【在 t********e 的大作中提到】
: k means?
|
l*********3
发帖数: 26 | 4
这道题不是NP-HARD的。
暴力法：建一个shortest path map。可以用Dijskstra算法。然后对每个点计算其到每
个器材所在点的距离。找最小值。
暴力法时间复杂度：shortest path map: n个点，每个O(nlog n)，总共O(n^2log n)。
【在 s*****i 的大作中提到】
: 有一个gym，用block表示。里面有健身器材，还有障碍物。让找一个最佳的位
: 置放置椅子，使得椅子到所有健身器材的曼哈顿距离最短。
: 有障碍物，应该是NP hard。难道写一个brute force吗？这题的考点在哪里？
|
s*****i
发帖数: 32 | 5 谢谢！原贴已改。
要写Dijskstra吗？这道题是不是Dijskstra比A*更合适。这两种感觉都算是brute
force，没有什么巧妙之处，难道这题的考点就是看是否记住这两种算法了吗？看来得
练习一下了。不知大牛们也没有什么别的高见？
【在 l*********3 的大作中提到】
:
: 这道题不是NP-HARD的。
: 暴力法：建一个shortest path map。可以用Dijskstra算法。然后对每个点计算其到每
: 个器材所在点的距离。找最小值。
: 暴力法时间复杂度：shortest path map: n个点，每个O(nlog n)，总共O(n^2log n)。
|
q****m
发帖数: 177 | 6 比较confuse. 有了障碍物后两个点新的距离怎么定义？
【在 s*****i 的大作中提到】
: 有一个gym，用block表示。里面有健身器材，还有障碍物。让找一个最佳的位
: 置放置椅子，使得椅子到所有健身器材的曼哈顿距离最短。
: 有障碍物，应该是NP hard。难道写一个brute force吗？这题的考点在哪里？
|
l****f
发帖数: 6 | 7 难道不是健身器材bounding box的中点？ |
p********n
发帖数: 165 | 8 抛个砖：
A*算法的核心是点到点求最短距离，不是点到面。而且需要好的heuristic function，
即使是在矩阵中找点对点最短距离也不一定是最好算法。
这个题，假设gym为n^2 matrix，k个器械。 用Dijkstra计算每个器械到非障碍物的距
离，复杂度为k*n^2*log(n),其中log(n)为maintain 一个priority queue的复杂度，
queue里最多的元素不可能是n^2而是n。
然后iterate 一遍matrix，找出离k个器械距离和最小的一个element，复杂度为n^2.
所以最后复杂度为 O(k*n^2*log(n))
当然这个题两个相邻点的距离都是uniform的话，可以不用Dijkstra,而用Breath-First
Search，复杂度可以进一步降低到O(k*n^2). |
j*********n
发帖数: 34 | |
l*********1
发帖数: 936 | |
|
|
l*********1
发帖数: 936 | 11 用dijkstra over kill
【在 s*****i 的大作中提到】
: 谢谢！原贴已改。
: 要写Dijskstra吗？这道题是不是Dijskstra比A*更合适。这两种感觉都算是brute
: force，没有什么巧妙之处，难道这题的考点就是看是否记住这两种算法了吗？看来得
: 练习一下了。不知大牛们也没有什么别的高见？
|
j*********n
发帖数: 34 | 12 请问大牛，正确的做法是什么？
【在 l*********1 的大作中提到】
: fail
|
l****f
发帖数: 6 | |
p********n
发帖数: 165 | 14 修过AI课的有很多都会把。
【在 l****f 的大作中提到】
: google里估计也没几个会A*
|
S*******w
发帖数: 24236 | 15 修过也记不得了。
【在 p********n 的大作中提到】
: 修过AI课的有很多都会把。
|
