《太極迷陣》通用解法

  今天為大家帶來的是太極迷陣通用解法,關卡通用解法一覽。這里匯總了太極迷陣的通用解法,感興趣的朋友一起來看看吧。

通用解法

  在這里給出n個點,m條線,任意線條件約束(例如線連的點必須連續),任意初始點a,任意終止點b的通解思路。

  黑白二色對應二進制0和1,則n個點對應於二進制向量,線約束對應於n*n的二進制矩陣A,則本問題轉化為解二進制線性方程組A*x=a+b。

  從而有,有解的充要條件是r(A)=r([A a+b]),這里的秩是指字母矩陣(λ-矩陣)的秩,不是數字矩陣的秩。

  因此,我們只需要1次秩的判斷就可以解出該問題。

  該解法總計算量約為(m-1)(n-1)/2,實際計算更簡單,因為只涉及到0和1的二進制加減。

  若用計算機判斷秩,我們可以選用n-1次秩的判斷代替手工計算,雖然計算量增大,但總計算量不過是大約為m*O(n²),甚至更少。

  實際上,只需要一次對角化,就可得出結果,因為只涉及到二進制加減,總計算過程運算量極小。

  給出例子:以第五關為例(高階類似)

《太極迷陣》通用解法

  共6個點,4條相連的線,初始點a=(1,0,0,0,1,0),終止點b1=0或b2=(1,1,1,1,1,1)

  矩陣A如下圖(左邊灰色是行標):

《太極迷陣》通用解法

  得出結果:

  若取b=b1,有x=(1,1,1,0,0,1),(選取初始列不同,得到結果不同,但本解是包含所選列的極小解)

  若取b=b2,則無解

  由於時間太晚,明天我會把第99關解答貼出。

  若需要詳細過程證明,我會詳細貼出。真正計算很簡單。

來源:TapTap
作者:﹏雨船

LEAVE A REPLY

Please enter your comment!
Please enter your name here