作者jh961202 (阿電)
看板C_and_CPP
標題[問題] 不是普通的8-puzzle問題...
時間Mon Apr 18 23:57:38 2016
各位板友好，初次發文，請多指教
如有疏忽之處，還請提點
誠如標題所述，本人想要解一個題目，經過各種關鍵字找尋後，感覺跟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，感覺不像很快就能算出正確答案...）
希望各位板友能提點一下這個題目，謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.13.149
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1460995062.A.D2E.html
1F：推 IKAFIRE: 好A*不用嗎 04/19 00:03
這題並不是最短路徑...
※ 編輯: jh961202 (140.135.74.20), 04/19/2016 00:55:43
2F：→ IKAFIRE: 所要求移動的方式必須是「總成本」最小的那個方式 04/19 01:25
3F：→ IKAFIRE: 你確定這不是最短路徑 04/19 01:25
4F：→ bibo9901: A*最簡單就 BFS 用priority queue而已啊 04/19 01:40
5F：→ bibo9901: 你把"距離"改成你的"成本"就好了 04/19 01:41
6F：→ bibo9901: 而且8-puzzle其實很小, 窮舉都可以 04/19 01:42
7F：→ Sylveon: 做法跟上面大大一樣~ 把距離改成本就好了 04/19 02:43
8F：推 LPH66: 最短路徑這東西本質上就是由 A 到 B 的最短成本 04/19 06:27
9F：→ LPH66: 你這個問題也是由 A (起始) 到 B (1 在左上) 的最短成本 04/19 06:27
10F：推 Yshuan: BFS標準題 也才8格 不會TL 04/19 10:13