[其他] 線性規劃 地圖著色

看板Math作者 (Latog2013)時間8年前 (2016/04/12 10:19), 編輯推噓1(1推 0噓 5→)
留言6則, 3人參與, 最新討論串1/1
台灣地圖著色，將台灣本島每個縣市著色， 相鄰的縣市需著不同的顏色，且要用最少的顏色畫完地圖。 使用線性規劃求解 這樣的題目要如何解? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.33.72.206 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1460427590.A.271.html
→
04/12 11:26, , 1F
四色定理？
04/12 11:26, 1F
推
04/12 11:51, , 2F
圖著色是整數規劃問題
04/12 11:51, 2F
→
04/12 12:18, , 3F
好像要用0 1去設 只是不清楚限制式該怎麼列
04/12 12:18, 3F
→
04/12 17:58, , 4F
對每個 (頂點,顏色) 做一個 binary indicator
04/12 17:58, 4F
→
04/12 17:58, , 5F
根據著色的定義去列限制式
04/12 17:58, 5F
→
04/12 17:59, , 6F
對頂點 v, 顏色 c, x(v,c)=1 若且唯若 v 著顏色 c
04/12 17:59, 6F
‣ 更多 LATOG2013 的文章
文章代碼(AID): #1N35j69n (Math)