Комбинации грубой силы коммивояжера

Question

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

Моя программа спрашивает пользователя, сколько городов они добавят. Затем он просит их ввести название города, а затем их долготу и широту. Я создал метод для создания двумерного массива, в котором хранятся расстояния между всеми городами.

То, что я хочу, чтобы мой алгоритм грубой силы вычислял расстояние между всеми комбинациями городов, и в конце выведите кратчайшее расстояние.

Например:

Введено 3 города (Нью-Йорк, Париж, Шанхай) Расстояния между ними сохраняются.

[0.0, 5834.0, 11851.0]
[5834.0, 0.0, 9257.0]
[11851.0, 9257.0, 0.0]

Теперь я хочу отработать все возможные комбинации и их общее расстояние:

NY-P-S-NY
NY-S-P-NY
P-NY-S-P
P-S-NY-P
S-NY-P-S
S-P-NY-S

Моя проблема заключается в том, чтобы избежать расстояния 0,0 от массива, что, очевидно, приведет к более коротким маршрутам.

Любая помощь очень ценится. Обратите внимание, я только учусь кодировать, поэтому, если возможно, я предпочитаю менее эффективные и более простые для понимания ответы:)

Приведенный ниже код является моей попыткой заставить его работать в 4 городах, однако я хочу, чтобы программа смогла выполнить эту задачу для любого количества городов. Я хорошо знаю, что я пытался безуспешно:

int numCities = weights.length();
      List<Integer> brute = new ArrayList<Integer>();
      for (int i = 0; i< 4; i++){
        brute.add(i);
      }
      System.out.println(brute);
      double weight = 0.0;
      double tempWeight = 0.0;
      int temp1 = 0;
      int temp2 = 0;
      int temp3 = 0;
      int temp4 = 0;
      int removing = 0;
      int valuetoRemove = 0;
      for (int a = 0; a < 4; a++){
        for (int b = 0; b < 3; b++){
          temp2 = brute.get(b);
          //System.out.println(temp2);
          List<Integer> brute2 = new ArrayList<Integer>();
          brute2.addAll(brute);
          brute.remove(b);
          System.out.println(brute);
          for (int c = 0; c < 2; c++){
            temp3 = brute.get(c);
            //System.out.println(temp3);
            List<Integer> brute2 = new ArrayList<Integer>();
            brute2.addAll(brute);
            brute.remove(c);
            //System.out.println(brute);
            temp4 = brute.get(0);
            //System.out.println(temp4);
            //brute.remove(0);
            //System.out.println(brute);
            tempWeight = weights[temp1][temp2] + weights[temp2][temp3] + weights[temp3][temp4] +  weights[temp4][temp1]; 
            System.out.println(tempWeight);
            brute = brute2;
          }
        }
      }