Не могу улучшить метод nextPermutation в задаче TSP - PullRequest
Новая
       6

Не могу улучшить метод nextPermutation в задаче TSP

0 голосов
/ 30 октября 2018

Хорошо

Я продвинул проблему агента путешественника (TSP) в Java с помощью грубой силы, но у меня есть проблема в методе "nextPermutation". Я предполагаю, что обратные маршруты идентичны, поэтому стоимость моего кода будет: n! / 2. Я провел несколько тестов на бумаге, обмениваясь индексами по-разному, и всегда входил в бесконечный цикл.

Идея заключается в следующем: если у меня есть следующий вектор: 

Int[] array = {0,1,2,3};

Метод "nextPermutation" должен генерировать мне список такой, что:

0123 = 3210

2031 = 1302

0231 = 1320

0321 = 1230

0312 = 2130

1032 = 2301

0132 = 2310

1203 = 3021

2103 = 3012

2013 = 3102

0213 = 3120

1023 = 3201

Безразлично, левый или правый маршрут, оба они полностью действительны, кроме того, вы можете видеть, что общее количество перестановок равно 4! / 2 = 12.

Мой код n !, но я хочу n! / 2: 

   public static boolean nextPermutation (int[] v) {

        int i = v.length - 1;
        while (i > 0 && v[i - 1] >= v[i]) {
            i--;
        }
        if (i <= 0) {
            return false;
        }
        int j = v.length - 1;
        while (v[j] <= v[i - 1]) {
            j--;
        }

        swap(v, i, j);

        return true;
    }

    public static void swap(int[] v, int i, int j) {
        int aux = v[i - 1];
        v[i - 1] = v[j];
        v[j] = aux;

        j = v.length - 1;
        while (i < j) {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            i++;
            j--;
        }
    }

С помощью этого кода я генерирую все перестановки и заканчиваю тем, что вектор равен {3,2,1,0}, но я хочу улучшить метод и избежать вычисления случаев, в которых он будет обратным. Например, это то же самое, что ехать из Калифорнии во Флориду, а затем в Техас, чтобы ехать из Техаса во Флориду, а затем в Калифорнию, поэтому этот расчет не требуется.

Надеюсь, мне было понятно, привет и спасибо!

...