[问题] 棋盘走路的问题 soheadsome PTT批踢踢实业坊

[问题] 棋盘走路的问题

楼主: soheadsome (师大狗鼻哥) 2014-03-13 01:46:47

不好意思这算半个作业文
题目的内容大概是
一个棋盘会给定起点和终点
然后棋盘上每一格都会有值
求起点到终点的所经过的最小值
我大概知道要用BFS来解决
但我想到说起点和终点会不固定
如果我刚好这次的iterate有两个以上相同的值
我应该是依贪婪的方式选择离终点最近的
但我想是该直接去量两者之间的距离
还是应该直接选方位呢?
(若终点在左上我应当选这次可走的最左或最上方为主)
这边卡了满久
希望有大大能帮忙解惑谢谢

作者: scwg ( ) 2014-03-13 02:01:00

因为每一格会有不同权重, BFS 应该不够, 试试看最短路径i.e. Dijkstra

作者: s89162504 (阿本) 2014-03-13 10:20:00

如果是棋盘的话纯Dijkstra很容易爆，要优化

作者: tkcn (say) 2014-03-13 12:19:00

可以说明一下为何会爆吗？棋盘有什么特别？优化又是指什么？

作者: wasidada (dada) 2014-03-13 12:41:00

a* 搜索

楼主: soheadsome (师大狗鼻哥) 2014-03-13 18:15:00

因为作业是要比较bfs ids的效能所以我想先做bfs

作者: EdisonX (卡卡兽) 2014-03-13 22:24:00

我想顺便问一下，这题适合用动态规划做吗？

作者: DJWS (...) 2014-03-14 11:28:00

为什么要找最短路径? 不是要找棋盘最小值吗?

楼主: soheadsome (师大狗鼻哥) 2014-03-14 14:29:00

的确是最小路径没错我的说明不太清楚

作者: DJWS (...) 2014-03-14 16:19:00

如果是bfs/ids的话那么你应该是人工智能的课程？这样的话应该就不会用到dijkstra了 dijkstra是图论的东西

楼主: soheadsome (师大狗鼻哥) 2014-03-15 02:17:00

没错是ai的课

继续阅读

Re: [问题] 大地排关问题eieio Re: [问题] 大地排关问题bleed1979 Re: [问题] 大地排关问题tkcn Re: [问题] 大地排关问题bleed1979 [问题] 大地排关问题qaz00123 [问题] 画面最佳比率dlikeayu Re: [问题] 不能跟一样的人坐在一起的问题KOFXI [问题] 不能跟一样的人坐在一起的问题entryword [问题] 一元四次方程式sayitagain [问题] 最佳分配的问题jimshsu