Хроматическое число в Java - PullRequest
Новая
       15

Хроматическое число в Java

0 голосов
/ 16 ноября 2011

Это попытка грубой силы хроматического числа матрицы.Кажется, он работает в том смысле, что он дает мне правильное количество требуемых цветов, но вместо 1,2,3,4 он будет отображать 1,2,3,6.По какой-то причине, даже если матрица, возможно, удалась с меньшим количеством цветов, она все равно потерпит неудачу и продолжит идти к максимальному числу.Есть ли причина, по которой он продолжает отказывать?

«n» - максимальное количество цветов.«v» - это вершина, а «m» - количество используемых в данный момент цветов.

псевдокод: http://i42.tinypic.com/deoc2u.jpg

static int color(){ 
       int i;
       for(i = 1; i <= n; i++)
       {
               if(color(0,i)){
                       return i;}
       }
       return i;
}

    static boolean color(int v, int m) {

    if(v > n-1)
            return true;
    else
    {
            for(int i = 1; i <= m; i++)
            {
                    boolean match = false;
                    q[v] = i;

                            for(int j = 0; j < n; j++)
                            {
                                    if(input[v][j] == 1)                
                                    {
                                            if(q[v] == j+1)
                                                    match = true;
                                    }
                            }

                    if(match == false)
                    {
                            if(color(v+1,m)) 
                                    return true;
                    }
            }
            q[v] = 0;
            return false;
    }

}

пример вывода:

ФайлИмя: file1
Ввод
6
0 1 1 0 1 1
1 0 1 1 1 1
1 1 0 1 0 1
0 1 1 0 1 1
1 1 0 1 0 1
1 1 1 1 1 0
1 не удалось
2 не удалось
3 не удалось
4 не удалось
5 не удалось

Цвета: 1 2 3 1 3 6

1 Ответ

0 голосов
/ 16 ноября 2011

Гах, я должен спать! Но я не могу сосчитать, сколько раз я откладывал присвоение до самого последнего возможного момента, поэтому я чувствую сочувствие по поводу вашего крайнего срока.

Это на самом деле не "грубый" подход, поскольку на самом деле все сводится к тому, чтобы попробовать каждую возможную комбинацию раскраски узлов и проверить, какие из них не конфликтуют. Ваш подход - эвристика, известная как жадная раскраска . Он может найти оптимальные результаты, но также может дать произвольно плохое решение. Тем не менее, я попытался вручную просмотреть образец ввода, который вы предоставили (спасибо, Microsoft Paint) и следуя этому алгоритму, результат должен быть действительно 4, начиная с вершины 0.

Итак, вот что я считаю неправильным в вашем коде. В следующем отрывке ... 

if(input[v][j] == 1)
{
    if(q[v] == j+1)
    match = true;
}

Похоже, вы сравниваете цвет текущей вершины (который в любом случае будет i) с индексом вершины, а не с цветом этой другой вершины. Я думаю, вам нужно изменить внутренний тест на ... 

if(i == q[j])

или, если хотите (ничего не изменится) ... 

if(q[i] == q[j])

Кроме того, вы делаете слишком много проверок. Вершины 0 может быть назначен цвет 1. Затем необходимо проверить вершину 1 по отношению к вершине 0, если она смежна. Вершина 2 должна быть проверена на 0 и 1, если они смежные, и так далее. Вы проверяете вершины, которым еще не был присвоен цвет. Так что не ограничивайте j n, но ограничивайте его текущей вершиной v.

Наконец, использование такой конструкции, как if(match == false), довольно запутанно и необязательно. Просто используйте if(!match).

Надеюсь, это поможет. Если вы все еще застряли, и я вовремя ловлю комментарии, я могу предоставить больше указателей.

...