题目大意就是给定一个 n x m 的矩阵,矩阵只含 0 或者 1,其中 0 代表连通,1 代表阻断,给定任意矩阵内两点 A B 坐标,要求找出 A->B 的最短路径(假设是可达的),大家有什么好的思路吗,多多益善,谢谢了。(如果描述不清楚,还请提出。)
Talk is cheap,show your code!
1
classyk 2018-06-27 19:51:22 +08:00 via iPhone
这个不就是 Astar 算法吗
|
2
baiihcy 2018-06-27 19:55:16 +08:00
BFS 就能实现了吧
|
5
LawlietZ 2018-06-27 20:08:42 +08:00 via iPad
裸 dijksta 啊 超级简单。。。哪个公司的面试啊。。。
|
6
ayyll 2018-06-27 20:08:51 +08:00 via Android
@baiihcy bfs 解单源最短路吧。。他这任意两点 明显是多源 bfs 确定不会被询问哭? 所以 Floyd 吧
|
8
cbais7890 2018-06-27 20:27:49 +08:00 9
|
11
Parallel 2018-06-27 20:52:08 +08:00 2
题目描述的表示图的方式叫,邻接矩阵。针对这个题目,对应不同的查询需求,可以扯的有很多。
以下,n 为顶点数,e 为边数。 O(n^3) Floyd O(n^2) Dijkstra O(n*e) Bellman-ford O(e) SPFA |
12
ballshapesdsd 2018-06-27 20:53:09 +08:00
你们都审题了没有啊,怎么迪杰斯特拉都出来了
|
14
Parallel 2018-06-27 21:00:57 +08:00
@ballshapesdsd 哦,点开链接才看到完整的题目,理解题目有误。
|
16
takato 2018-06-27 21:07:09 +08:00
@ballshapesdsd 似乎好多人理解成了邻接矩阵。。。
其实是张迷宫图。。。 |
17
wannafly 2018-06-27 21:27:27 +08:00 via Android
@takato 当然可以。取决于你的 heuristic function 怎么取,比如退化成最简单的迷宫算法。
|
18
HiJ2017 2018-06-27 21:38:25 +08:00
这是很经典的数据结构题,当时教材上给了 BFS 和 DFS 两种解法
<数据结构教程>--李春葆 |
21
silhouette 2018-06-27 21:45:35 +08:00 via Android
floyd,模板题
|
24
wizardforcel 2018-06-27 22:15:31 +08:00
floyd 有点浪费了,它最后就要 distance[A][B]
|
25
takato 2018-06-27 22:29:56 +08:00
@wannafly 问题是如果退化了以后,状态数还是和 DFS,BFS 一样,那么这个 function 在这个例子中的意义在哪里?
当然我可以理解想做一个 Universal Algorithm/Model 的决心,但是也别忘了 overfit 的存在。 即如果只是要个 local minimum,你说的就是比较好的方法,但是源问题不是这样定义的。 |
26
JohnSmith 2018-06-27 22:37:27 +08:00 via Android
动规问题 刚做过
|
28
IceCola1 2018-06-27 22:48:20 +08:00
对于的矩阵转换为图,如果只是 0,1 的话,深搜或者广搜都可以,时间复杂度都是 OV2,如果有权重的话,用 Dijkstra,时间复杂度,OV2,如果有负权重的话,bellman-ford 算法 O(VE),如果所有点对都要输出的话,floyd 算法 O(V3)
|
29
Rico 2018-06-27 23:08:04 +08:00
可以参考我之前写的 A*算法,有动图 https://hogwartsrico.github.io/2016/03/11/AStarPathFinding/
|
30
lsmgeb89 2018-06-28 00:42:09 +08:00
bfs
|
32
Mirana 2018-06-28 01:24:40 +08:00
dp
|
33
jedihy 2018-06-28 01:37:01 +08:00
这种题目就真的不 show code 了,BFS 送分题。
|
35
wolegequ 2018-06-28 01:40:01 +08:00 via Android
还 talk is cheap 😅
|
36
jssyxzy 2018-06-28 01:58:24 +08:00
算法自己复习。
|
37
laxenade 2018-06-28 02:02:18 +08:00
leetcode 64 的变种?
|
38
xiadong1994 2018-06-28 02:05:21 +08:00
这种路径长度都相同的题,用不着 dijkstra,单纯的 BFS。另外面试一般不会考 Floyd 吧……
|
39
thedrwu 2018-06-28 02:37:31 +08:00
看需要查询几次。 是否需要“最”优解。 如果只考虑短时间内能简单实现的解法:
若查询一次可以如楼上用广搜。 若查询多次,整张 n×m 表一遍一遍的扫(递推),假设点 a->点 z, 每扫一遍更新上一歩的解(a->b->z 中的 b)和最优路径和歩数, 直到收敛。 空间只需要 O(n×m)。 |
40
wannafly 2018-06-28 03:01:23 +08:00 via Android
@takato 只要能保证 heuristic cost 算出来小于等于实际的 cost,那么就能保证得到的解是全局最优解。这种情况下也是能减少所要搜索的状态数量的。
|
41
greenmoon55 2018-06-28 08:18:02 +08:00
lc 675
|
42
shiyouming91 2018-06-28 08:25:41 +08:00
BFS+DP,用另一个同样大矩阵保存到达某个点的已知最少的步数,BFS 的每一步检查新矩阵中当前的位置是不是记录了更小或相等的步数。如果是就不再展开这个位置了,否则记录步数到这个位置。空间复杂度是 m*n+BFS 用的栈,我直觉觉得栈肯定比 m*n 小,可以忽略。时间复杂度没分析过,不够一般情况下不会太差。我的直觉是因为 BFS 的初期很容易剪掉相邻的分支,应该是 m*n 或者最多是 m*n*log(m*n)级别的
应该不是最快的解法,不过可扩展性很强,因为很容易处理经过每格格子的开销不一样的情况,以及类似战棋游戏里的移动力有限想知道哪些点是可达的情况,各种涂色的问题等等 总之在十年前之后的硬件条件下我会无脑用这种解法 |
43
p1094358629 2018-06-28 08:31:53 +08:00
我连题目都看不懂。。。A 为啥是 1,0 按照 XY 坐标不应该是 0,1 吗???
|
44
yxcoder 2018-06-28 08:48:32 +08:00
相对较短其实就算可以的了,最短的收益感觉不大
|
46
yylucifer 2018-06-28 09:12:13 +08:00
基本算法都不熟悉,还甩:Talk is cheap, show your code!
|
49
mbtfdwlx 2018-06-28 09:46:56 +08:00
如果两点之间权值都是定值 用 BFS 就可以了, 有权值的情况下 就可以考虑 Dijkstra SPFA A-star 都可以
|
50
q397064399 2018-06-28 09:49:16 +08:00
|
51
hisune 2018-06-28 09:58:05 +08:00
|
52
ioth 2018-06-28 09:58:49 +08:00
学校的题目用来面试,这公司技术了得。
|
53
kzzhr 2018-06-28 10:09:59 +08:00 via Android
都用矩阵存了,这不是 floyd 的标准模板么
|
54
jetyang 2018-06-28 10:41:16 +08:00
游戏里常用的算法,英雄 A 怎么走可以最快的攻击到英雄 B
|
55
stargazer 2018-06-28 12:06:42 +08:00
话说想起在爱奇艺面试的时候非让我手写出全部代码。。。。还是自己太渣。。。。
|
56
Jhonson OP @stargazer 你最终写出来了吗那,我当时是说出了利用距离来定夺,但是我只考虑了距离终点的距离,没有考虑起点,还用的是欧氏距离,最终啥都没写出来。
|
58
loryyang 2018-06-28 13:09:54 +08:00
首先想到的就是 BFS 打表,从 A 开始,一直广度搜索打表,更新步长,一直到接触到 B 就结束了
|
59
Solarest 2018-06-28 13:19:07 +08:00
Floyd 吧
|
60
yuriko 2018-06-28 13:53:46 +08:00
面试的话,能知道是广搜就行了吧……
就是试探你有没有基本的算法基础…… |
62
zzj0311 2018-06-28 14:32:11 +08:00 via Android
就是个 A*,哪那么多问题。。
|
64
lzhCoooder 2018-06-28 15:25:18 +08:00
dijksta 和 A*都可以啊,选哪个看实际情况,面试的话把这两个算法都说出来没毛病
|
65
salamanderMH 2018-06-28 15:59:34 +08:00
|
66
yao978318542 2018-06-28 17:03:19 +08:00
|
67
mogami18 2018-06-28 19:36:25 +08:00
floyd
|
68
zke1e 2018-06-28 19:52:25 +08:00
dijkstra 啊
|
69
maggch 2018-06-28 21:37:55 +08:00
这题边权都是 1,最优就是 BFS 了
|
70
maggch 2018-06-28 21:39:27 +08:00
Dijkstra 带 log ,Floyd 复杂度 n^3,做这题时间复杂度都非常的不优秀
|
72
LawlietZ 2018-06-28 23:29:09 +08:00
@yanaraika 与几几年有什么关系呢,退化不退化还是看数据吧,acm 里面不还是很多去使用 spfa 去做最短路的题。。当然我个人更倾向用队列优化的 Dij,SPFA 的 k 值是由算法中点的入队出队次数决定的,一般还是不容易直接降到 ne 吧
|
74
takato 2018-06-29 11:44:27 +08:00 via iPhone
|