四色地圖定理遞歸回溯算法

我已經編碼到下面的程序來實現四色地圖定理（任何地圖可以用四種顏色着色，簡而言之，沒有任何相鄰區域是相同的顏色）遞歸地。一切都在編譯，但是我的輸出給了我錯誤的數據（每個區域的顏色爲-1，而不是現在的值0-3）。我最大的問題是爲什麼輸出不正確。四色地圖定理遞歸回溯算法

對於那些想知道，輸入文件是鄰接矩陣看起來如下：

這裏是我的代碼：

public class FourColorMapThm 
{ 
    public static boolean acceptable(int[] map, int[][] matrix, int r, int c) 
    { 
     for(int i = 0; i < map.length; i++) 
     { 
      if(matrix[r][i] == 1) 
      { 
       if(map[i] == c) return false; 
      } 
     } 
     return true; 
    } 

    public static boolean colorTheMap(int[] map, int[][] matrix, int r, int c) 
    { 
     boolean q = false; 
     int i = 0; 

     if(!acceptable(map, matrix, r, i)) return false; 

     map[r] = i; 
     boolean done = true; 

     for(int j = 0; j < map.length; j++) 
     { 
      if(map[j] == -1) 
      { 
       done = false; 
      } 
     } 
     if(done) return true; 

     do 
     { 
      i++; 
      q = colorTheMap(map, matrix, r+1, i); 
      if(q) return true; 
     } 
     while(i <= 3); 

     map[r] = -1; 
     return false; 
    } 

    public static void main(String[] args) throws IOException 
    { 
     Scanner in = new Scanner(System.in); 
     String snumRegions, fileName; 
     int numRegions; 

     System.out.print("Enter the number of regions: "); 
     snumRegions = in.nextLine(); 
     numRegions = Integer.parseInt(snumRegions); 

     System.out.print("\nEnter filename for adjacency matrix: "); 
     fileName = in.nextLine(); 
     in.close(); 

     Scanner inFile = new Scanner(new FileReader(fileName)); 
     PrintWriter outFile = new PrintWriter("coloredMap.txt"); 
     int[][] matrix = new int[numRegions][numRegions]; 
     int[] map = new int[numRegions]; 

     //initializing matrix from file 
     for(int row = 0; row < matrix.length; row++) 
     { 
      for(int col = 0; col < matrix.length; col++) 
      { 
       matrix[row][col] = inFile.nextInt(); 
      } 
     } 
     inFile.close(); 

     //initialize map vals to -1 
     for(int i = 0; i < map.length; i++) 
     { 
       map[i] = -1; 
     } 

     colorTheMap(map, matrix, 0, 0); 

     outFile.println("Region\t\tColor"); 
     for(int i = 0; i < map.length; i++) 
     { 
      outFile.println(i+1 + "\t\t" + map[i]); 
     } 
     outFile.close(); 
    } 
}

來源

2015-09-18 Alex

您還沒有colorTheMap使用c，和你可能想要。

你得到的所有條目-1一個map原因是這樣的：

int i = 0; 
    if(!acceptable(map, matrix, r, i)) return false; 
    map[r] = i; 
    . 
    . 
    . 
    do 
    { 
     i++; 
     q = colorTheMap(map, matrix, r+1, i); 
     if(q) return true; 
    } 
    while(i <= 3); 
    map[r] = -1;

的colorTheMap(map, matrix, r+1, i)回報false它擊中

int i = 0; 
    if(!acceptable(map, matrix, r, i)) return false;

如果任何鄰國已經瞬間每次調用使用0着色（因爲您從未使用c，因此您將始終將0指定爲中的，如果你到達那條線），所以在返回之後，我們立即返回false，然後給r分配任何顏色。我假設你輸入圖形連接的。因此，colorTheMap(map, matrix, r, c)任何呼叫或者找到與0有色r鄰居甚至不設置map[r]以來if(!acceptable(map, matrix, r, i)) return false;任何東西都不會立即返回，或者它只是在

接收的 q = false分配

do 
    { 
     i++; 
     q = colorTheMap(map, matrix, r+1, i); 
     if(q) return true; 
    } 
    while(i <= 3);

並且撤消循環後面的行map[r] = -1;中的着色。

另注：我假設你想實現貪婪的色彩，但不是最優的，即你可以這樣結束了無色的區域。四色問題比一個簡單的「只用一種顏色塗色，沒有任何鄰居被分配，而且你很好」的方式更復雜，否則一個證明四種顏色就足夠了出現。 Here看起來像一個正確算法的輪廓，它需要二次時間。在證明四個着色平面圖總是可能的情況下，又出現了20年。

來源

2015-09-18 09:01:44

四色地圖定理遞歸回溯算法

回答

相關問題