java - m_coloring 的蒙特卡罗估计

Question

我的书中有一些使用回溯技术解决 m 着色问题的伪代码，如下所示:

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;
}

其中图形由二维数组 W 表示，其行和列的索引从 1 到 n，如果第 i 个顶点和第 j 个顶点之间存在边，则 W[i][j] 为真否则为假；这会输出图形的所有可能着色，最多使用 m 种颜色，因此相邻顶点的颜色都不会相同。每种着色的输出是一个从 1 到 n 索引的数组 vcolor，其中 vcolor[i] 是分配给顶点的颜色(1 到 m 之间的整数)。

我用 Java 实现了它并且它起作用了。它是使用调用 m_coloring(0) 调用的。它最终看起来像这样:

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;
}

现在的问题是实现蒙特卡洛估计的伪代码。书上是这样的。

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;
}

所以我创建了我认为是这个的 Java 版本:

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;
}

问题是我每次运行时都会收到 ArrayOutOfBoundsException。有没有人可以看到我的代码有什么问题，或者我如何才能更好地实现这个蒙特卡洛估计代码？

Answer 1

我确实运行了你的代码，没有问题:

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() );
}

}