java - 旅行推销员蛮力组合

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

标签： javaarrayslistmultidimensional-array