置頂
不是普通的8-puzzle問題
各位板友好
誠如標題所述，本人想要解一個題目
經過各種關鍵字找尋後，感覺跟8-puzzle很像
不過，題目不只是單純的「移動方塊成為指定排列模式」而已
例如：
0 5 8
7 4 3
2 6 1
這是一個puzzle（用0代表空格），我需要把1移動到左上角就好了
（其他順序啥的不考慮）
然而，所要求移動的方式必須是「總成本」（Cost）最小的那個方式
例如
<
5 0 8
7 4 3
2 6 1
這個狀態下，與剛剛的初始狀態比起來，移動了5，所以成本就是5
目前的想法偏向BFS或DFS（都是遞迴）
BFS→一直往左上的方向，每個方向都移動一次，走的時候慢慢加cost
DFS→一直往左上的方向，每次要移動時只選最小的數字
這樣一來，因為都是一直往左上，自然就把防止逆向的功能整併了
可是不知道要用哪個方式才是正確的...
（剛剛手算DFS，感覺不像很快就能算出正確答案...）
希望各位板友能提點一下這個題目，謝謝！
覺得很厲害，不太懂這個呢!!
會員登入
(先登入會員才能回覆留言喔!)