整理Java迴歸代碼用於回溯圖着色算法

問題是使用遞歸來爲給定的圖賦予最小數量的顏色，使得沒有相鄰頂點可以具有相同的顏色。函數簽名是靜態的String exhaustive（int color，字符串前綴）其中，color是該迭代中使用的顏色數，前綴是由每個節點的顏色組成的字符串（如果有3個節點，則示例爲0，其中節點0用顏色0着色，節點1用顏色1着色，節點2用顏色2着色;然後前綴將是012）。當所有節點着色時，函數返回字符串前綴。第一次調用是使用參數（0，「」）進行的，意思是嘗試用0種顏色着色。這是我寫的代碼。它工作正常，返回少於34個節點的正確答案，但是對於超過34個，該功能不返回到主。任何改進代碼的想法將不勝感激。請讓我知道是否需要更多信息。整理Java迴歸代碼用於回溯圖着色算法

int n=36; 
static int[] lastcolor = new int[n];  
static StringBuilder newprefix ; 
String addprefix=""; 
static int node=0,j=0; 
Graph.generateFixedSet(n); 
verticies2 =Graph.getVerticies(); 

public static String exhaustive(int color,String prefix) 

{ 

    newprefix = new StringBuilder(prefix); 

     if(prefix.length()==verticies2.size()) 
      return prefix; 
     else 
     { 
      for(;j<=color;j++) 
      { 
       lastcolor[node]=j; 

       addprefix = Integer.toString(j); 
      canColor =1; 
      tempnode = (verticies2.get(node)).getEdges(); 
       for(h=0;h<tempnode.size();h++) 
       { 
        if((tempnode.get(h)).getColor() == j) 
       { 
        canColor =0; 
        break; 
       } 

      } 

      if(canColor==1) 
       { 
         verticies2.get(node).setColor(j);    
        node++; 
         j=0; 
       newprefix.append(addprefix); 
         break; 

       }//end if canColor 
      }//end for 

     if(j!= 0) 
      { 


       if(node==1) 
       {       
         color++; 
         j=0; 
         node=1; 
       newprefix.delete(0,newprefix.length()); 
       newprefix.append("0"); 

       }//end if node <=1 
       else 
       { 
         verticies2.get(node).setColor(-1); 
         node--; 
         j=lastcolor[node]+1; 
         newprefix.setLength(node); 
        } 
      }//end if j!=0 
      prefix = newprefix.toString(); 
      return exhaustive(color,prefix); 
      }//end else 
    }//end exhaustive

來源

2012-03-18 HighBit

歡迎來到Stack Overflow！要求陌生人通過檢查發現代碼中的錯誤並不是富有成效的。您應該通過使用調試器或打印語句來識別（或至少隔離）問題，然後返回一個更具體的問題。 – 2012-03-18 18:06:05

這是功課嗎？ – Perception 2012-03-18 18:15:00

Hi @OliCharlesworth！你是對的，但程序沒有顯示任何錯誤。而且由於該程序是遞歸的，對自己進行了數以千計的調用，所以我不知道如何跟蹤問題。請指教。 – HighBit 2012-03-18 18:27:14

不要使用遞歸。使用循環...和arraylists如有必要。

來源

2012-03-18 18:27:09

我不喜歡遞歸，只是在這裏使用遞歸是一個要求，正如我在第一行中所述。此外，我認爲回溯最好使用遞歸實現。或者，還有更好的方法？ – HighBit 2012-03-19 00:40:03

沒有完全清楚，你必須。我很好奇你爲什麼需要使用遞歸。你可以在代碼的一小部分中使用遞歸嗎？那會滿足要求嗎？ – 2012-03-19 10:53:38

這是一個分析算法的問題，目的是證明NP完全問題的指數複雜度 – HighBit 2012-03-19 19:01:03

整理Java迴歸代碼用於回溯圖着色算法

回答

相關問題