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