Java: локальный поиск ошибки TSP - PullRequest
Новая
       15

Java: локальный поиск ошибки TSP

0 голосов
/ 28 августа 2011

Я кодирую простые локальные алгоритмы поиска для TSP в Java. Вот метод: 

public Permutation localSearch(Permutation best, int maxnoimprov) {
    int count = 0 ;
    Permutation candidate;
    do {
        candidate = stochastic_2_opt(best);
        count = (candidate.getLength() < best.getLength()) ? 0 : count+1;
        if (candidate.getLength() < best.getLength()) {
            best=candidate;
        }
        System.out.print("Candidate "); candidate.showPermutation(); System.out.println(" Current best: "+best.getLength());
    } while (count<maxnoimprov);
    return best;
}

Проблема в том, что оператор if всегда верен, поэтому при запуске метода вывод выглядит так:

.... 3, 34, 43, 32,} ДЛИНА: 30464.0 Текущий лучший: 30464.0

.... 14, 37, 24, 49,} ДЛИНА: 31499,0 Текущий лучший: 31499,0

.... 8, 4, 20, 42,} ДЛИНА: 30710,0 Текущий лучший: 30710.0

.... 23, 33, 12, 6,} ДЛИНА: 29321.0 Текущий лучший: 29321.0

.... 11, 32, 28, 15,} ДЛИНА: 30545,0 Текущий лучший: 30545.0 .................................................. ........

Как видите, «лучшее» всегда заменяется «кандидатом», а не должно.

Мой код мне подходит, но что-то явно не так.

ПРИМЕЧАНИЯ:

1) Я проверил метод stochastic_2_opt (), и все в порядке.

2) Метод getLength () возвращает двойные значения, поэтому я подумал, что это может быть ловушкой, и я использовал Double.compare, но даже тогда он не работал.

3) Я также замечаю, что при написании условия if как (candid.getLength ()

Можете ли вы помочь мне найти, где ошибка?

1 Ответ

1 голос
/ 28 августа 2011

Я подозреваю, что переменная-член Permutation, которая содержит длину, является статической переменной; это могло бы объяснить результаты отлично. Затем, когда stochastic_2_opt() создает кандидата, он по неосторожности также устанавливает длину best. В этом случае ваша вера в то, что if всегда верна, - это красная сельдь; if оценивается как false, но вы все равно получите тот же результат.

...