作者soheadsome (师大狗鼻哥)
看板Prob_Solve
标题[问题] 棋盘走路的问题
时间Thu Mar 13 01:46:47 2014
不好意思 这算半个作业文
题目的内容大概是
一个棋盘会给定起点和终点
然後棋盘上每一格都会有值
求起点到终点的所经过的最小值
我大概知道要用BFS来解决
但我想到说起点和终点会不固定
如果我刚好这次的iterate有两个以上相同的值
我应该是依贪婪的方式 选择离终点最近的
但我想是该直接去量两者之间的距离
还是应该直接选方位呢?
(若终点在左上 我应当选这次可走的最左或最上方为主)
这边卡了满久
希望有大大能帮忙解惑 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.122.216.115
1F：→ scwg:因为每一格会有不同权重, BFS 应该不够, 试试看最短路径 03/13 02:01
2F：→ scwg:i.e. Dijkstra 03/13 02:01
3F：推 s89162504:如果是棋盘的话纯Dijkstra很容易爆，要优化 03/13 10:20
4F：→ tkcn:可以说明一下为何会爆吗？棋盘有什麽特别？ 优化又是指什麽？ 03/13 12:19
5F：→ wasidada:a* 搜索 03/13 12:41
6F：→ soheadsome:因为作业是要比较bfs ids的效能 所以我想先做bfs 03/13 18:15
7F：→ EdisonX:我想顺便问一下，这题适合用动态规划做吗？ 03/13 22:24
8F：推 DJWS:为什麽要找最短路径? 不是要找棋盘最小值吗? 03/14 11:28
9F：→ soheadsome:的确是最小路径没错 我的说明不太清楚 03/14 14:29
10F：推 DJWS:如果是bfs/ids的话 那麽你应该是人工智慧的课程？ 03/14 16:19
11F：推 DJWS:这样的话应该就不会用到dijkstra了 dijkstra是图论的东西 03/14 16:22
12F：→ soheadsome:没错是ai的课 03/15 02:17