→ hwanger : 按照原po的敍述 ABC的index似乎不是各排各的 所以 09/30 23:29
→ hwanger : 想要minimize的式子 應該是 09/30 23:29
→ hwanger : sum of (A_ij+B_ij+C_ij)X_ij over all i != j 09/30 23:29
→ hwanger : 而此時domain應該是 09/30 23:29
→ hwanger : { X: i,j,k,h are distinct and X_ij=X_jk=X_kh=1, 09/30 23:29
→ hwanger : X_st=0 for all (s,t)!=(i,j),(j,k),(k,l) } 09/30 23:29
→ hwanger : domain的形狀太奇怪 可能不應該用線性規劃 而是用 09/30 23:38
→ hwanger : 離散的技巧 不過我目前也沒想到比較漂亮的手法 09/30 23:38
→ hwanger : 至少這一題只有4!=24個點 當考慮n! n夠小時 跑程式 09/30 23:38
→ hwanger : 暴力破解是ok的 09/30 23:38
→ hwanger : 想了一下 其實這是Travelling salesman problem的變 10/01 14:43
→ hwanger : 形 考慮5座城市 C0,C1,C2,C3,C4 其中C0和其他四座的 10/01 14:46
→ hwanger : 距離的0 而Ci和Cj的距離是(A_ij+B_ij+C_ij) (這裡要 10/01 14:47
→ hwanger : 注意的是因為取平方的關係 A_ij=A_ji B_ij=B_ji 10/01 14:49
→ hwanger : C_ij=C_ji 所以上述定義是well-defined的) 現在希望 10/01 14:51
→ hwanger : 從C0出發 每個城市都走過一遍並回到C0 問最短的走法 10/01 14:52
→ hwanger : 因為TSP是NP-complete problem 所以這題有極大的可 10/01 14:55
→ hwanger : 能是不行用整數規劃去處理的 10/01 14:55
→ hwanger : 或許可以參考TSP最新的研究進度 10/01 14:58
→ hwanger : 原po是從shortest Hamiltonian path in a weighted 10/02 21:27
→ hwanger : complete graph推到這個問題的嗎? 10/02 21:28
感謝您的回復，我在想看看離散數學的方式能不能找最佳解
這個是目前實務碰到的問題的簡化版
因為感覺跟之前看過作業研究的題目很像
但是又有點不同，才想確認看是否用錯方法哈
感覺這個問題跟TSP問題較相似，但是距離是多維而非原本的1維
※ 編輯: tokyo291 (125.227.214.67 臺灣), 10/05/2020 09:38:03
→ hwanger : ??? 我不太懂你多維的意思 所以A,B,C的index是各自 10/05 10:17
→ hwanger : 跑的嗎 那只要各自monotone就好了 根本就不需要TSP 10/05 10:18
→ hwanger : 就是因為不是各自跑 所以才變成TSP 冏 10/05 10:19
不是各自跑沒錯
那個多維的部分是想形容原本TSP的問題中不同城市間的距離(1維)變成多維
有點難形容@@
原本的TSP問題，只要考慮不同城市間的距離
但是我碰到的狀況除了考慮城市間的距離
還需要考慮城市間的人口數差、出生率差異、性別比、待職人數差異...等等
考慮這些東西來決定最佳路徑
※ 編輯: tokyo291 (125.227.214.67 臺灣), 10/05/2020 13:32:00
→ hwanger : 是不是指city i和city j的weight wij實際上是有一 10/05 15:23
→ hwanger : 堆的參數的函數 例如原例中 wij是Aij Bij Cij的函 10/05 15:23
→ hwanger : 數 10/05 15:23
→ hwanger : 應該是我摸不太清楚你多維的意思 囧 我不太能想像 10/05 15:23
→ hwanger : 多維的TSP XD 10/05 15:23
我用原本題目的說法嘗試說一次看看能不能表達我的意思哈
現在有10個樣本編號1~10(也就是10個城市)
每個樣本分別有ABCDE五種數值
ex:1號樣本的A=5、B=6、C=7、D=8、E=9
現在希望可以找出一個順序去牌這10個樣本
讓相鄰的樣本ABCDE的數值可以相差最少
如果只有A一個的話(每個城市的距離)，就可以看成是一般的TSP
然後我的想法是因為多了BCDE，就想成多維的城市距離的情況
以上是我的理解
如果有錯誤的觀念還希望能更正><
※ 編輯: tokyo291 (118.170.119.144 臺灣), 10/05/2020 22:55:05
→ hwanger : XD 如果只有A一個的話 雖然有違直覺 為了使排序完後 10/06 00:05
→ hwanger : 的 |A1-A2| + |A2-A3| +...+ |A9-A10|最小 或 10/06 00:07
→ hwanger : (A1-A2)^2 + (A2-A3)^2 +...+ (A9-A10)^2 最小 其實 10/06 00:08
→ hwanger : 排的依據就是將data increasing或decreasing的排 10/06 00:10
→ hwanger : 其實不用特別考慮TSP 冏 10/06 00:12
→ hwanger : 如果有ABCDE 5種數值的話 此時i號樣本和j號樣本的距 10/06 00:16
→ hwanger : 離 dij就可能可以定義成(Ai-Aj)^2 + (Bi-Bj)^2 + 10/06 00:18
→ hwanger : (Ci-Cj)^2+(Di-Dj)^2+(Ei-Ej)^2 此時才需要TSP 冏 10/06 00:22
抱歉我忘了強調一個需求前題
就是排序的目的是為了讓10個樣本排序後的散布能接近水平線
(排序後樣本點的折線圖接近水平)
所以必須避免排序後出現increasing或decreasing的結果
例如:目前有5個樣本，A的數值分別為5、6、7、8、9
排序成5、6、7、8、9或是9、8、7、6、5
相鄰的差會最小，但是散布的情況不是水平線
排成6、8、5、9、7(這邊先忽略相鄰最小的需求)會接近水平線
※ 編輯: tokyo291 (125.227.214.67 臺灣), 10/06/2020 08:31:05
→ hwanger : 所以是不是應該要再加一個額外條件 假設排完後 各自 10/06 09:24
→ hwanger : 線性迴歸的斜率為mA, mB, mC, mD, mE 然後希望前面 10/06 09:26
→ hwanger : 算出來的距離和D 及 mA^2+mB^2+mC^2+mD^2+mE^2能同 10/06 09:27
→ hwanger : 時越小越好 (還是其實只要求後者越小越好?) 不管怎 10/06 09:30
→ hwanger : 樣 其實已經不是TSP了 可能要重新定義問題然後從頭 10/06 09:32
→ hwanger : 分析方法了 冏 10/06 09:32
→ tokyo291 : 對，討論到後來發現已經不是TSP...碰到的這個問題太 10/06 16:13
→ tokyo291 : 複雜哈哈 10/06 16:14
→ hwanger : 雖然問題變複雜了 不過可以用的方法可能變多了 例如 10/06 23:22
→ hwanger : 只考慮mA^2+mB^2+mC^2+mD^2+mE^2的最小值的話 那分 10/06 23:22
→ hwanger : 析、線代、群表現論的技巧可能就可以用進來找解(或 10/06 23:24
→ hwanger : 找"夠好的"解) 10/06 23:24