一、實驗目的與要求

1、實驗基本要求：

（1）掌味訓溯法演算法設計思想，
（2）掌握地圖填色問題的回溯法解法，

2、實驗亮點：

（1）通過回溯法完成了實驗，并驗證了結果的正確性，
（2）在使用回溯法的基礎上，從貪心剪枝，置換剪枝，向前探查剪枝，矩陣記錄和選擇鄰接表進行資料存盤5個方面對程式進行優化，大幅降低程式運行時間并在附件中上傳了所有實驗程序中的輸出結果并對結果都進行了驗證，
（3）通過實際操作與理論分析結合的方式，從圖規模，合法涂色數，圖的邊密度和圖的連通分量四個方面分析對比演算法的效率，
（4）有針對性地探究了找到全部可行解的方法，
（5）最后思考并探究了輪換等有效剪枝策略，極大提高演算法效率，

二、實驗內容與方法

背景知識：
為地圖或其他由不同區域組成的圖形著色時，相鄰國家/地區不能使用相同的顏色， 我們可能還想使用盡可能少的不同顏色進行填涂，一些簡單的“地圖”（例如棋盤）僅需要兩種顏色（黑白），但是大多數復雜的地圖需要更多顏色，
每張地圖包含四個相互連接的國家時，它們至少需要四種顏色，1852年，植物學專業的學生弗朗西斯·古思里（Francis Guthrie）于1852年首次提出“四色問題”，他觀察到四種顏色似乎足以滿足他嘗試的任何地圖填色問題，但他無法找到適用于所有地圖的證明，這個問題被稱為四色問題，長期以來，數學家無法證明四種顏色就夠了，或者無法找到需要四種以上顏色的地圖，直到1976年德國數學家沃爾夫岡·哈肯（Wolfgang Haken）（生于1928年）和肯尼斯·阿佩爾（Kenneth Appel，1932年-2013年）使用計算機證明了四色定理，他們將無數種可能的地圖縮減為1936種特殊情況，每種情況都由一臺計算機進行了總計超過1000個小時的檢查，
他們因此作業獲得了美國數學學會富爾克森獎，在1990年，哈肯（Haken）成為伊利諾伊大學（University of Illinois）高級研究中心的成員，他現在是該大學的名譽教授，
四色定理是第一個使用計算機證明的著名數學定理，此后變得越來越普遍，爭議也越來越小 更快的計算機和更高效的演算法意味著今天您可以在幾個小時內在筆記本電腦上證明四種顏色定理，

問題描述：
我們可以將地圖轉換為平面圖，每個地區變成一個節點，相鄰地區用邊連接，我們要為這個圖形的頂點著色，并且兩個頂點通過邊連接時必須具有不同的顏色，附件是給出的地圖資料，請針對三個地圖資料嘗試分別使用5個（le450_5a），15個（le450_15b），25個（le450_25a）顏色為地圖著色，

三、實驗步驟與程序

1、未優化的回溯：

（1）演算法描述：

a. 拓展當前節點，并對當前節點進行搜索
b. 判斷當前節點是否存在可行解，如果存在則進入c，如果不存在，則回溯上一節點，并進入a
c. 判斷是否搜索結束，如果結束則直接輸出結果并停止搜索；如果未結束，則進入a
d. 當全部搜索完畢后仍不存在可行解，則輸出無解

未經過優化的回溯演算法流程圖大致如下

（2）編程實作

大致代碼如下：

void dfs(int x) {
    //如果已經涂完整個地圖，即找到可行解
    if (x > n) {
        ans++;
        return;
    }
    //對每個點進行涂色
    for (int i = 1; i <= m; i++) {
        color[x] = i;//模擬涂色
        //進行涂色的合法性檢測
        for (int j = 1; j <= x; j++) {
            if (g[j][x] && color[j] == color[x]) {
                b = 1;
                break;//非法，重新染色
            }
        }
        if (b) {
            b = 0;
        } else {
            dfs(x + 1);//當前解合法，對當前節點進行拓展搜索
        }
    }
}

（3）運行并測驗：

為了對演算法進行測驗，我選擇了實驗時給定的如下地圖資料，并進行填涂嘗試，

①影像資料文字化：
由于對于代碼而言，不能夠存盤影像，因此需要將影像資料轉為鄰接矩陣進行圖的存盤，

將每個小塊看成圖的一個點，將圖與圖之間的鄰接關系映射成點與點之間的連邊，

②進行小資料試涂：
采用輸入流將每個連邊讀入后呼叫函式進行計算，并通過輸出流將結果輸出（全部運行結果在‘result’->‘9_4_480.txt’中）并利用系統函式進行計時，可得對于這個給定地圖，未優化的回溯在0.8544ms下找到全部480個解，

③涂色正確性檢驗：
完成了對地圖的涂色后，務必對演算法進行正確性檢驗以證明我們的涂色方案是正確的，

易知，涂色的正確性檢驗即檢測所填涂地圖中相鄰的邊的涂色是否相同，如果相同則為非法涂色，如果所有相鄰點涂色都不同則涂色合法，

檢測方法也相對簡單，僅需遍歷整個邊集，并依次對相鄰點進行顏色檢驗即可，通過檢驗，②中試涂的480個結果全部正確，證明回溯演算法具有正確性，
④大資料試涂：
完成了小資料下的試涂后，嘗試對大資料進行涂色，不過發現對附件中450點使用5色填涂不能在短時間內運行結束，并且運行比較長一段時間（12h+）也很難得到結果，這說明，常規的回溯演算法只適用于數量級較小的資料，回溯演算法亟待優化，

2、對回溯進行優化（本部分中時間消耗均為完備搜索的時間消耗）：

從上面的實驗中，我們可以知道，常規的回溯演算法耗時很長，而且搜索效率較慢，只能處理較低數量級的資料，因此需要對演算法進行一系列優化，通過對運算程序的分析與計算，提出了如下幾種可行的優化方案：（每種優化方案均進行了測驗，并將測驗結果存在‘result’檔案夾中）

（1）貪心剪枝策略：

①演算法描述：
通過分析，我們不難發現，對于搜索程序中產生的搜索樹最大深度一定，但分支數很大，因此需要采用策略去降低搜索樹的分支個數，從而對搜索樹進行剪枝，
通過分析，我們可以知道，對于每次搜索出的節點，拓展的節點為當前的可行解個數，而且，分支產生的越早，分支就會產生的越多，因此，需要降低搜索樹樹根處分支數，盡量將分支數靠近葉子節點，從而進行貪心剪枝，

通過分析可以得知，不論從哪個點開始搜索，得到的可行解不變，因此，只需從度數大的點開始搜起，并依次按照點度數降序順序依次搜索，直至搜索到最后一個點即可，

②具體實作：
本演算法的具體實作相對簡單，只需在最開始讀入圖資料之后，進行搜索之前按照點度數降序排序對圖進行重構，再進行搜索即可，

//比較點度數函式
bool comp(const MapNode tmp1, const MapNode tmp2) {
    return tmp1.value < tmp2.value;
}
//排序重構函式
void arraySort() {

        sort(vArray + 1, vArray + vNum + 1, comp);
        for (int i = 1; i <= vNum; i++) {
            oldToNew[vArray[i].id] = i;
            newToOld[i] = vArray[i].id;
        }
    }

③運行并測驗：
對給定的大資料（450點5色）進行填涂，并將可行解全部輸出，將程式運行20次取時間平均值做表如下：

這證明，使用貪心演算法進行優化是切實有效的優化方式，但演算法的運行時間仍然比較長，需要進一步優化，

（2）置換剪枝策略：

①演算法描述：
通過觀察第一次優化輸出的可行解，我們不難發現，在起始搜索點的不同涂色方案下的可行解個數相同，這是因為對于第一個搜索點而言，不同涂色下的各個填涂方案是對稱的，即對于在涂色 x 0 x_0 x0?下的解向量 S 0 = ( x 0 , x 1 , x 2 , x 3 , … ) S_0=(x_0,x_1,x_2,x_3,… ) S0?=(x0?,x1?,x2?,x3?,…)，可以映射出 n ? 1 n-1 n?1（n為可用顏色數）個等效可行解，因此搜索時只需固定第一個點，并將搜索出來的可行解個數乘以可用顏色數即可，大約可以將實際運行時間縮短至原來的 1 n \frac{1}{n} n1?（ n n n為可用顏色數），
②具體實作：
本演算法的具體實作很簡單，只需在搜索時固定第一個顏色即可

③運行并測驗：
對給定的大資料（450點5色）進行填涂，并將可行解全部輸出，將程式運行20次取時間平均值做表如下：

這證明，使用置換剪枝策略進行優化是切實有效的優化方式，但演算法的運行時間仍然比較長，需要進一步優化，

（3）向前探查剪枝策略：

①演算法描述：
在搜索程序中，對于一些無解的節點，可以做到提前探查，即拓展節點前先對是否存在可行解進行檢查，如果不存在可行解，則剪枝并回傳，

②具體實作：
在本題中，采用了colorMatrix陣列對每個點可以使用的顏色進行計數，并在回溯搜索時對當前點的合法顏色進行檢測，如果沒有則直接回傳，無需拓展，

③運行并測驗：
對給定的大資料（450點5色）進行填涂，并將可行解全部輸出，將程式運行20次取時間平均值做表如下：

這證明，使用向前探查剪枝策略進行優化是有效的優化方式，但優化并不十分明顯，

（4）矩陣記錄可行解避免多次搜索

①演算法描述：
在進行回溯搜索程序中，每次對點進行顏色合法性檢查時都要遍歷當前點，每一次每一層的搜索都需要檢查合法性，成千上萬次操作將大大提高這部分的時間消耗，而每次拓展節點時，新節點與原節點都會有公共邊，因而點的可用性不會差別特別大，因此，可以設計一個陣列對每個點的可用性進行檢測并存盤，從而避免多次對可用性的檢測，

②具體實作：
為了存盤每個點的顏色可用性，設定了colorMatrix進行存盤，其中，colorMatrix[i][1]表示第i點1顏色是否可用（可用為1，反之為0），colorMatrix[j][2]表示第j點2顏色是否可用（可用為1，反之為0），特殊地，colorMatrix[i][0]表示第i點共有幾種可用顏色
因此對于每個點回溯時，只需通過colorMatrix遍歷點i的可用顏色，再洗掉鄰接點colorMatrix可用顏色并繼續搜索即可，完成搜索則恢復該可用顏色即可，

a.搜索函式：

//backtrack to search
void backtrack(Map &map, int index, int rest) {
    //judge if find the solution
    if (rest == 0) {
        //store the solution
        result.push_back(vector<int>(map.colorArray + 1, map.colorArray + 1 + map.vNum));
        for (int i = 0; i < map.vNum; i++) {
            ofs << result[result.size() - 1][i];
        }
        ofs << endl;
        return;
    }
    //dissatisfied solution: check each valid color
    for (int i = 0; i < map.colorType; i++) {
        if (map.colorMatrix[index][i + 1] == 0) {
            //if the color solution is invalid
            if (deleteColor(map, index, i) != -1) {
                recoverColor(map, index, i);
                continue;
            }
            //search point[index]
            map.colorArray[index] = i;
            //backtrack to search
            backtrack(map, next(map), rest - 1);
            //recover the validation of the color and return
            map.colorArray[index] = -1;
            recoverColor(map, index, i);
        }
    }
    return;
}

首先回溯函式中對是否為解進行判斷，如果是解，則將結果存入結果容器中，并直接回傳，
如果當前不為可行解，且當前點沒有合法可用顏色，則進入下一個點的判斷，如果有可用顏色，則對當前節點的可用顏色進行拓展，并使用colorMatrix對顏色情況進行記錄，搜索前洗掉該可用顏色，搜索后恢復該可用顏色，

b.恢復顏色函式：

void recoverColor(Map &map, int index, int color) {
    MapNode candidate = map.vArray[index];
    MapNode *tmp = candidate.next;
    while (tmp) {
        int candidateIndex = tmp->value;
        //if the point is uncolored and its adjacent point is not colored with that color
        if (map.colorArray[candidateIndex] == -1 && map.colorMatrix[candidateIndex][color + 1] == 1 + index) {
            map.colorMatrix[candidateIndex][color + 1] = 0;
            if (map.colorMatrix[candidateIndex][0] == 0) {
                map.colorMatrix[candidateIndex][0]++;
                return;
            }
            map.colorMatrix[candidateIndex][0]++;
        }
        tmp = tmp->next;
    }
}

對于每個搜索的點，當他下一個鄰接點不為空時，則進行搜索，首先判斷當該點未涂色且該點鄰接點顏色合法時，則可以認為該點的當前涂色合法，將colorMatrix對應值加一并回傳即可，

c.洗掉顏色函式：

int deleteColor(Map &map, int index, int color) {
    MapNode candidate = map.vArray[index];
    MapNode *tmp = candidate.next;
    while (tmp) {
        int candidateIndex = tmp->value;
        //if the point is uncolored and its adjacent point is not colored with that color
        if (map.colorArray[candidateIndex] == -1 && map.colorMatrix[candidateIndex][color + 1] == 0) {
            map.colorMatrix[candidateIndex][color + 1] = 1 + index;
            map.colorMatrix[candidateIndex][0]--;
            if (map.colorMatrix[candidateIndex][0] == 0)
                return candidateIndex;
        }

        tmp = tmp->next;
    }
    return -1;
}

對于每個搜索點，如果該點的下一個鄰接點的可涂色顏色為0，則回傳當前點的序號，如果不存在下一個鄰接點，則回傳-1，對于鄰接點可涂顏色不為0的情況，則更新鄰接點可涂顏色直至搜索到末端點，

（5）資料結構的選擇：

①演算法描述：
對于儲存圖的資料結構，常見的有鄰接表和鄰接矩陣兩種，因此如何選擇合適的資料結構也將從一定程度上節省程式的運行時間，

對于鄰接矩陣，尋找相鄰區域時需要遍歷所有區域；對于鄰接表而言，可以直接獲取相鄰區域，由于本地搜索程式與深度優先搜索類似，而采用鄰接表的深度優先搜索的時間復雜度為 O ( n + e ) ( e 為 邊 數 ) O(n+e)(e 為邊數) O(n+e)(e為邊數)，采用鄰接矩陣的深度優先搜索的時間復雜度為 O ( n 2 ) O(n^2 ) O(n2)，因此在搜索時，可以采用鄰接表進行搜索，但對于鄰接表而言，對于一些資料的存盤沒有鄰接矩陣方便，因此可以采用鄰接矩陣和鄰接表共用的方式對圖結構進行存盤，
②具體實作：

struct Map {
    int vNum;          //number of vertex
    MapNode *vArray;   //adjacency list
    int *colorArray;   //store type of color, -1 for uncolored
    int colorType;     //type of color
    int *oldToNew;     //change after sort by degree, origin id-> new id
    int *newToOld;     //change after sort by degree, new id-> origin id
    bool **matrix;     //adjacency matrix
    int **colorMatrix; //store the validation of each point and number of valid colors
};

使用colorMatrix二維矩陣存盤各個點的顏色可用情況，使用vArry存盤鄰接表，使用colorArray存盤點的涂色情況，

③運行并測驗：
對給定的大資料（450點5色）進行填涂，并將可行解全部輸出，將程式運行20次取時間平均值做表如下：

這證明，使用鄰接表存盤資料并進行優化是有效的優化方式，

3、時間與效率分析：

利用以上演算法優化，完成不同規模下資料的試涂色記錄并整理如下（搜索結果在‘result’檔案夾中）：

（1）三組資料的涂色：

①得到第一個可行解：

可以看到隨著可用顏色的增多，涂色消耗時間依次縮短，這是由于可用顏色更多，搜索程序中更容易搜索到可行解，無需進行多次搜索就可以找到可行解，

②得到全部可行解（15色和25色全部可行解個數超過10^9無法一定時間內得到完備搜索結果）：

可以看到采用貪心剪枝，置換剪枝，向前探查剪枝，矩陣記錄并選擇鄰接表進行資料存盤這5種優化后，實作了從最開始未優化時短時間內無法完成完備搜索變為在一分鐘左右的時間即可完成全部搜索，演算法的效率得到極大提升，

（2）自行生成地圖涂色并分析：

通過亂數，自行生成了不同規格的地圖，對于每個地圖，均將程式運行10次并取平均值作為實際值，對于每次比較時，均需要保證其余變數的值不變，在有解的情況下，分析統計作表如下：

①圖規模對運行時間的影響：

圖的規模極大影響了搜索的規模，規模小的圖要比規模大的圖的搜索時間小的多，
通過上圖，可以看到，當地圖規模成線性級增長時，時間消耗大致成指數型增長，并且，隨著數量級的增長，指數增長速率放緩，這是因為多種剪枝策略對大資料下優化作用更明顯，

②合法涂色數對運行時間的影響：

合法的顏色數極大的影響了搜索的規模，合法顏色少的圖要比合法顏色多的圖的搜索時間小的多，
通過分析可知，若對于某圖涂色的存在可行解向量 S 0 = ( x 0 , x 1 , x 0 , x 0 , … ) S_0=(x_0,x_1,x_0,x_0,…) S0?=(x0?,x1?,x0?,x0?,…)則 S 1 = ( x 1 , x 0 , x 1 , x 1 , … ) ( 交 換 x 0 , x 1 ) S_1=(x_1,x_0,x_1,x_1,…)(交換x_0,x_1) S1?=(x1?,x0?,x1?,x1?,…)(交換x0?,x1?)則存在 n ! n! n!種等效可行解向量，因此，當合法顏色數增多時，可行解數量大致成階乘型（指數）增加，
此外，隨著合法顏色數的增長，指數增長速率增大，這是因為由于合法顏色數的增加導致可剪枝數降低，搜索樹成指數級增長，剪枝策略的優化作用減弱，

③圖的邊密度對運行時間的影響（在400點5色下進行測驗）：

邊密度影響了可行解的個數，也影響了剪枝的效率，邊密度越大，剪枝效率越高，邊密度越小，搜索樹的每一支就會更深，
從上圖以及上表中可以看出，隨著邊密度的提高，時間消耗指數級急速降低，這是剪枝效率大大提升的原因，

④圖的連通分量對運行時間的影響（在400點5色下進行測驗）：

聯通分量從一定程度上影響了搜索樹的規模，當搜索程序中搜索完一個極大連通圖后，搜素會從下一個極大連通圖的最大度節點開始搜索，而不是從原節點上繼續拓展，類似于重新從根節點伸展出一顆新的搜索樹，降低了上一級的節點拓展，從一定程度上節省了時間，
通過分析上圖以及上表，可以看到連通分量確實對圖的運行時間有影響，并且連通分量越大，演算法運行時間越短，

四、實驗結論或體會

1. 常規演算法的演算法效率往往較低，需要進行優化
2. 對于回溯搜索演算法，搜索時應優先選擇限制較多的分支進行拓展搜索
3. 可以通過數學方法對演算法進行優化，例如本實驗中借助圖論中輪換的思想完成了優化，
4. 除了演算法本身，選擇合適的資料結構也可以在一定程度上降低程式的運行時間，
5. 演算法優化程序中，演算法的正確性驗證必不可少，在本題中，每種優化策略都經過了理論和實際進行驗證，

五、思考

輪換替換思想的推廣：

1、演算法描述：

通過對運行結果中可行解的分析以及對涂色邏輯的分析我們可以知道，對于m個合法顏色，規模為n的圖的一個解向量如果為 S 0 = ( c 0 , c 1 , c 0 , c 2 … ) ( c 0 , c 1 , c 2 … 互 異 顏 色 ) S_0=(c_0,c_1,c_0,c_2…)(c_0,c_1,c_2…互異顏色) S0?=(c0?,c1?,c0?,c2?…)(c0?,c1?,c2?…互異顏色)，則 S 1 = ( c 1 , c 0 , c 1 , c 2 … ) , S 2 = ( c 1 , c 2 , c 1 , c 0 … ) … S_1=(c_1,c_0,c_1,c_2…),S_2=(c_1,c_2,c_1,c_0…)… S1?=(c1?,c0?,c1?,c2?…),S2?=(c1?,c2?,c1?,c0?…)…也都為可行解，
即對于已經找到的可行解，可以通過輪換獲得更多可行解，由于顏色之間滿足互異性原則，且解向量中的顏色滿足全排列性質，因此確定一個可行解，可映射出 A n n = n ! A_n^n=n! Ann?=n!個可行解，通過這個規律可以在短時間內獲取巨大數量級的可行解，對于5色，找到一個可行解等于找到 A 5 5 = 5 ! = 120 A_5^5=5!=120 A55?=5!=120個可行解；對于 15 15 15色，找到一個可行解等于找到 A 1 5 1 5 = 15 ! = 1 , 307 , 674 , 368 , 000 A_15^15=15!=1,307,674,368,000 A1?515=15!=1,307,674,368,000個可行解；對于 25 25 25色，找到一個可行解等于找到 A 2 5 2 5 = 25 ! = 15 , 511 , 210 , 043 , 330 , 985 , 984 , 000 , 000 A_25^25=25!=15,511,210,043,330,985,984,000,000 A2?525=25!=15,511,210,043,330,985,984,000,000個可行解，
此外，對于不可行的搜索節點也同理，當找到搜索樹的某一枝無解后，可以利用輪換，將所有等效解全部剪枝剪掉，這大大降低了程式的運行時間，

2、運行并測驗：

采用輪換進行剪枝的策略和上面幾種已經介紹的剪枝策略，對450點5色地圖進行涂色并計時，發現僅需要不到一秒的時間即可完成全部3840個點的搜索，與之前大約一分鐘左右的時間相比，演算法效率得到極大提升，

附錄：

除以上嘗試外，我還進行了一些其他的嘗試，經過若干種演算法的優化，最終可以在 60 m s 60ms 60ms內搜出3840個全部可行解，將具體代碼附上如下：

#include <iostream>
#include <time.h>

using namespace std;

#define COLOR 5    //顏色數
#define VERTEX 90     //點數
#define EDGE 500   //邊數

class Vertex {
public:
    int color;
    int state[COLOR + 1];  //顏色狀態，1為可選，非1為不可選
    int choice;  //可選顏色數，即state中1的數量
    int restrain;  //相鄰數量
    Vertex() {
        color = 0;
        for (int i = 0; i < COLOR + 1; ++i) {
            state[i] = 1;
        }
        choice = COLOR;
        restrain = 0;
    }
};


//int map[VERTEX + 1][VERTEX + 1];  //圖的鄰接矩陣
int map2[VERTEX + 1][256];  //圖的鄰接表
long long int sum = 0;   //記錄解的個數
long Start;
long End;


int ColorFirst(Vertex *S) {
    int maxRestrain = 0, maxIndex = 0;
    for (int i = 1; i <= VERTEX; ++i) {
        if (S[i].restrain > maxRestrain) {
            maxRestrain = S[i].restrain;
            maxIndex = i;
        }
    }
    S[maxIndex].color = 1;
    maxRestrain = 0;
    int next = 0;
    for (int k = 1; k <= map2[maxIndex][0]; ++k) {
        int j = map2[maxIndex][k];
        S[j].choice--;
        S[j].restrain--;
        S[j].state[1] = -maxIndex;
        if (S[j].restrain > maxRestrain) {
            maxRestrain = S[j].restrain;
            next = j;
        }
    }
    return next;
}

int getNext(Vertex *S) {
    int min = COLOR;
    int next = 0;
    for (int i = 1; i <= VERTEX; ++i) {
        if (S[i].color == 0) {
            if (S[i].choice == min) {
                if (S[i].restrain > S[next].restrain) {
                    min = S[i].choice;
                    next = i;
                }
            } else if (S[i].choice < min) {
                min = S[i].choice;
                next = i;
            }
        }
    }
    return next;
}

//搜索函式
int DFS(Vertex *S, int now, int count, int used) {
    if (count == VERTEX) //到達葉子,找到一個著色方案
    {
        /*End = clock();
        cout << End - Start << endl;
        for (int i = 1; i <= VERTEX; i++) //輸出該著色方案
            cout << S[i].color << " ";
        cout << endl;
        exit(1);*/

        sum += S[now].choice;

        /*if (sum > 1000000000) {
            End = clock();
            cout << End - Start << endl;
            exit(1);
        }*/

        return S[now].choice;

    } else {
        int s = 0;
        for (int i = 1; i <= COLOR; i++) {
            if (S[now].state[i] == 1) {
                int ss = 0;
                S[now].color = i;
                bool isNew = i > used;
                //剪枝
                for (int k = 1; k <= map2[now][0]; ++k) {
                    int j = map2[now][k];
                    if (S[j].color == 0 && S[j].state[i] == 1) {
                        /*S[j].state[i] = -now;
                        S[j].choice--;
                        S[j].restrain--;*/
                        if (S[j].choice == 1) {
                            goto BACK;
                        } else {
                            S[j].state[i] = -now;
                            S[j].choice--;
                            S[j].restrain++;
                        }
                    }
                }
                if (isNew)
                    ss = DFS(S, getNext(S), count + 1, used + 1);
                else
                    ss = DFS(S, getNext(S), count + 1, used);

                BACK:
                for (int k = 1; k <= map2[now][0]; ++k) {
                    int j = map2[now][k];
                    if (S[j].state[i] == -now) {
                        S[j].choice++;
                        S[j].restrain++;
                        S[j].state[i] = 1;
                    }
                }
                S[now].color = 0;
                if (isNew) {
                    s += ss * (COLOR - used);
                    sum += ss * (COLOR - used - 1);
                    break;
                }
                s += ss;
            }
        }
        if (sum > 100000000) {
            End = clock();
            cout << End - Start << endl;
            exit(1);
        } else
            return s;
    }
}

int main() {
    Vertex S[VERTEX + 1];
    FILE *fp;
    int command;
    cin >> command;
    if (command == 1) {
        if ((fp = fopen("G:\\MapData\\MapR_5_90_500.txt", "r")) == NULL)  //打開檔案
        {
            printf("Can not open file!\n");
            exit(1);
        }
    } else if (command == 2) {
        if ((fp = fopen("G:\\MapData\\MapR_5_100_500.txt", "r")) == NULL)  //打開檔案
        {
            printf("Can not open file!\n");
            exit(1);
        }
    } else if (command == 3) {
        if ((fp = fopen("G:\\MapData\\MapR_5_110_500.txt", "r")) == NULL)  //打開檔案
        {
            printf("Can not open file!\n");
            exit(1);
        }
    } else if (command == 4) {
        if ((fp = fopen("G:\\MapData\\MapR_5_120_500.txt", "r")) == NULL)  //打開檔案
        {
            printf("Can not open file!\n");
            exit(1);
        }
    }
    int u, v;
    char ch;
    for (int i = 1; i <= EDGE; i++) {
        fscanf(fp, "%c%d%d\n", &ch, &u, &v);
//        map[u][v] = map[v][u] = 1;
        map2[u][0]++;
        map2[u][map2[u][0]] = v;
        map2[v][0]++;
        map2[v][map2[v][0]] = u;
        S[u].restrain++;
        S[v].restrain++;
    }

    cout << "OK" << endl;
    fclose(fp);
    Start = clock();
    int a = DFS(S, getNext(S), 1, 0);
    End = clock();
    cout << "TIME:" << End - Start << endl;
    cout << "ANSWER:" << a << endl;
    return 0;
}