Monte Carlo Schätzung von m_coloring

Question

Ich habe einige Pseudo-Code aus meinem Buch für die m Färbungsproblem der Rückzieher Technik, die wie folgt aussieht:

void m_coloring(index i) 
{ 
    int color; 
    if (promising(i)) 
     if (i == n) 
      cout << vcolor[1] through vcolor[n]; 
    else 
     for (color = 1; color <= m; color++){ 
      vcolor[i + 1] = color; 
      m_coloring(i + 1); 
    } 
} 
bool promising (index i) 
{ 
    index j; 
    bool switch; 

    switch = true; 
    j = 1; 
    while (j < i && switch){ 
     if (W[i][i] && vcolor[i] == vcolor[j]) 
      switch = false; 
     j++; 
    } 
    return switch; 
} 

wo der Graph durch eine zweidimensionale Matrix dargestellt wird W denen hat sowohl seine Zeile als auch seine Spalten von 1 bis n indiziert, wobei W [i] [j] wahr ist, wenn es eine Kante zwischen dem i-ten Knoten und dem j-ten gibt und andernfalls falsch ist; Dies gibt alle möglichen Farben des Graphen aus, die höchstens m Farben annehmen, so dass keine benachbarten Ecken die gleiche Farbe haben. Die Ausgabe für jede Färbung ist ein Array vcolor, das von 1 bis n indiziert ist, wobei vcolor [i] die Farbe (eine ganze Zahl zwischen 1 und m) ist, die dem Scheitelpunkt zugeordnet ist.

Ich habe dies in Java implementiert und es hat funktioniert. Es wird mit dem Aufruf m_coloring (0) aufgerufen. Es endete wie folgt aussehen:

public static boolean W[][]= 
     {{false, false, false, false, false, false}, 
     {false, false, true, true, true, false}, 
     {false, true, false, false, true, false}, 
     {false, true, false, false, true, false}, 
     {false, true, true, true, false, true}, 
     {false, false, false, false, true, false}}; 
public static int n = 5; 
public static int m = 3; 
public static int vcolor[] = {1, 2, 3, 4, 5, 6}; 
public static int promising = 0; 
static void m_coloring (int i) 
{ 
    int color; 
    if (promising(i)){ 
     promising++; 
     if (i == n){ 
      for (int k = 1;k <= n; k++) 
       System.out.println(k + ": " + vcolor[k]); 
      System.out.println(); 
     } 
     else{ 
      for (color = 1; color <= m; color++){ 
       vcolor[i + 1] = color; 
       m_coloring(i + 1); 
      } 
     } 
    } 
}  
static boolean promising (int i) 
{ 
    int j; 
    boolean Switch; 
    Switch = true; 
    j = 1; 
    while (j < i && Switch){ 
     if (W[i][j] && vcolor[i] == vcolor[j]) 
      Switch = false; 
     j++;    
    } 
    return Switch; 
} 

Nun ist die Frage, die Pseudo-Code des Monte Carlo Schätzung implementiert. Das sieht im Buch so aus.

int estimate() 
{ 
    node v; 
    int m, mprod, t, numnodes; 

    v = root of state space tree; 
    numnodes = 1; 
    m = 1; 
    mprod = 1; 
    while (m != 0){ 
     t = number of children of v; 
     mprod = mprod * m; 
     numnodes = numnodes + mprod * t; 
     m = number of promising children of v; 
     if (m != 0) 
      v = randomly selected promising child of v; 
    } 
    return numnodes; 
} 

Also habe ich, was ich dachte, eine Java-Version dieser war:

public static int estimate(){ 
    int v[] = vcolor; 
    int numnodes, m1, mprod, t, i; 
    i = 0; 
    numnodes = 1; 
    m1 = 1; 
    mprod = 1; 
    while(m1 != 0){ 
     t = m; 
     mprod *= m1; 
     numnodes = numnodes + mprod * t; 
     m1 = promising; 
     Random rnd = new Random(); 
     if (m1 != 0) 
      v[i] = rnd.nextInt(m1); 
     i++; 
    } 
    return numnodes; 
} 

Das Problem ist, ich erhalte eine ArrayOutOfBoundsException jedes Mal wenn ich es laufen. Gibt es jemanden, der sehen kann, was mit meinem Code nicht stimmt oder wie ich diesen Monte-Carlo-Schätzcode besser umsetzen könnte?

Answer 1

Ich habe Ihren Code ausführen, und es gibt kein Problem mit ihm:

import java.util.*; 

class Main { 

private static final Random rnd = new Random(); 

public static boolean W[][]= 
     {{false, false, false, false, false, false}, 
     {false, false, true, true, true, false}, 
     {false, true, false, false, true, false}, 
     {false, true, false, false, true, false}, 
     {false, true, true, true, false, true}, 
     {false, false, false, false, true, false}}; 
public static int n = 5; 
public static int m = 3; 
public static int vcolor[] = {1, 2, 3, 4, 5, 6}; 
public static int promising = 0; 

public static int estimate(){ 
    int v[] = vcolor; 
    int numnodes, m1, mprod, t, i; 
    i = 0; 
    numnodes = 1; 
    m1 = 1; 
    mprod = 1; 
    while(m1 != 0){ 
     t = m; 
     mprod *= m1; 
     numnodes = numnodes + mprod * t; 
     m1 = promising; 
     if (m1 != 0) 
      v[i] = rnd.nextInt(m1); 
     i++; 
    } 
    return numnodes; 
} 

public static void main(String[] args){ 
    System.out.println(estimate()); 
} 

}