179      京東網上商城

拚圖遊戲的數學原理

一、線性代數基礎知識

1、逆序的定義：

        逆序是一個與排列相關的概念。
        由自然數1，2…，n組成的不重複的每一種有確定次序的排列，稱為一個n級排列（簡稱為排列）；或者一般的，n個互不同元素排成一列稱為“一個n級排列”。例如，1234和4312都是4級排列，而24315是一個5級排列。
        在一個n級排列中，如果一對數的前後位置與大小順序相反，即前麵的數大於後麵的數，那麼它們就稱為一個“逆序”。

        一個排列中逆序的總數就稱為這個排列的逆序數。

        逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。

        如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。

         再來一個定理：交換一個排列中的兩個數，則排列的奇偶性發生改變。

二、拚圖的數學定義

       在m*n*p(m,n>2,p>=1)的方塊區域裏，所有的方格兩兩不同，其中有一個特殊的方格，稱為空穴，任何與之有鄰麵(二維時隻須有鄰邊)的方塊均可與之互換位置(一次這樣的位置互換稱為一次操作，也稱為空穴的一次移動)。剛開始時隨機產生雜亂的排列順序，要求經過一係列操作後形成要求的排列順序(目標排列)。

       其實，拚圖問題可以轉化為這麼一個問題：“任意給一個數字矩陣，能否證明：經過無限次的交換，一定能到達目標矩陣或者經過無限的交換也不能實現目標矩陣？”。

三、定理

定理一：

         圖形A與圖形B等價的充要條件圖形A的排列的逆序數加上0元素行號和列號的奇偶性等於圖形B的排列的逆序數加上0元素行號和列號的奇偶性。為方便表述，把圖形排列的逆序數加上0元素行號和列號的奇偶性稱為圖形的奇偶性。

定理二：

        對於任意 m* n 的情況，任意兩個空穴在同一個位置且奇偶性相同的排列可以通過空穴移動相互轉化。

定理三、

        對源狀態A與目標狀態B進行規範化，使得兩矩陣的元素0（此處的元素0就是空穴）的位置相同；記為新的源狀態A'與目標狀態B'；

        若A'與B'的逆序對的奇偶性相同（即A'與B1的逆序對的奇偶性相同），則A'必定可能轉化為B',即A可以轉化到B;

        若A'與B'的逆序對的奇偶性不同（即A'與B2的逆序對的奇偶性相同），則A'必定不可能轉化為B',即A不可以轉化到B;

小結：

        其實：以上三個定理或者說是結論，說的都是一個事，隻是角度不同，三個定理的證明與敘述見下麵的鏈接。

定理一的敘述及證明

定理二的敘述及證明

定理三的敘述及證明

最後更新：2017-04-03 12:54:31

  上一篇： 申請解除PBL限製

  下一篇： mac os X下的updatedb