Re: [問題] Costed Sorting 的演算法
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
討論串 (同標題文章)