permutation combinational optimization swapping problem 以上三個應該是跟你要研究的問題有關的keywords 假如要找paper的話, 可從這著手. 不過基本概念與紙筆推演方法, 還是要從演算法打下基礎. ps.演算法或者作業研究(operation research)都是相關科目 解題有兩個方向: (a) 數字大的移動次數, 越少越好. (b) 可利用數字特別小的來當作swap助手. (如你後面這的例子) 從 (a) 的觀點出發的話 cost value 1 8 9 7 6 0 1 8 6 7 9 0 + 6 + 9 = 15 1 7 6 8 9 15+ 7 + 8 = 30 1 6 7 8 9 30+ 6 + 7 = 43 從 (b) 的觀點出發的話, 也就是數字定位之前都先用1放在該位置. 但是要先排好大的或小的, 就留給你去思考. 本例是先排好大的, 所以先把1放在第5個位置 cost value 1 8 9 7 6 0 6 8 9 7 1 0 + 1 + 6 = 7 6 8 1 7 9 7 + 1 + 9 = 17 6 8 7 1 9 17+ 1 + 7 = 25 6 1 7 8 9 25+ 1 + 8 = 34 1 6 7 8 9 34+ 1 + 6 = 41 但是再繼續思考解法下去的話, 什麼時候要用 (a), 什麼時候要用 (b)? 就變成了 heuristic search vs non-heuristic search 的派系鬥爭了. XD 小的太嫩了, 寫到這裡就好. :) ※ 引述《Starwindd (我是G爹)》之銘言： : 請教一下costed sort的作法... 一個頭兩個大... : 基本要求是這樣，給一串數字，用兩兩交換的方式來sort，但是每個sort要 : 花代價... : 例如 sort {3, 2, 1} : 先把 1,2 對調變成 {3, 1, 2} -> 代價為 1+2 =3 : 然後把 1,3 對調 {1, 3, 2} -> 代價為 1+3 =4 : 最後換 2,3 {1, 2, 3} -> 代價為 2+3 =5 => 總代價為 12 : 題目要求要找出最小代價的算法，以這題來說當然是 1 跟 3 直接對調，總代價 = 4 : 我一開始的想法是先sort找出最後的正確數列，然後從最小代價的數字組開始互換 : ，直到數列正確。例如 : 8124 -> 8214(3 cost) -> 8241(cost 5) -> 1248(cost 9) : 但是遇到數字跳很大的就出問題了，例如18976 : 我的作法會是 : 18976 -> 16978 (14) -> 16798 (16) -> 16789 (17) = 47 : 但正確的最小代價解法是 : 18976 -> 68971 (7) -> 68179 (10) -> 68719 (8) -> 61789 (9) -> 16789 (7) = 41 : 這樣的問題到底該怎麼解呢？ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.117.123.14