→ buffalobill : 這個演算法完成，四色定理就算證明完成了 05/08 16:05
→ buffalobill : 反過來說即使四色定理證明了，可能還是找不到演算法 05/08 16:06
我叫AI寫了一個隨機產生地圖並可以手動著色的網頁
https://buffalobill-taiwan.github.io/map4c/
人工手動的話，要用四種顏色填滿一張地圖並不難
但是沒有一個「確定性」的方法
保證一定可以填滿
比如一開始我會想
先用A B兩色將地圖最外圈著完
第二圈用C D兩色
不斷交互下去
直到地圖著完
四色問題就搞定了
但實作上這招很快就卡死
因為第二圈甚至第一圈就會出現需要第三色的情形了XD
電腦可以暴力處理
比如DFS
．先對某個區塊著色
．再對下個區塊著色，並不與相鄰區塊同色
．直到所有區塊著色完畢
．若遇到有區塊無法著任何顏色
則「回退」至上一個區塊並著出另一個可能的顏色繼續下去
關鍵就在這個回退
回退代表不確定性
有沒有可能對某些圖來說
不管如何回退都無法著色完成呢？
需要一種無回退的演算法
它可以根據平面圖的相鄰關係與目前著色情況
確定出某個區塊一定可以著某個顏色
從而將問題不斷縮小直到著色完成
不需要靠回退去試出可種可能
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.148.94 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1778226295.A.150.html