java - 使用 Random 作为 ArrayList 中的索引，如果之前使用过则不会移动

Question

我正在尝试做类似java中的TSP的事情，但我在生成路径时遇到问题。 我想用随机整数选择下一个“城市”，但如果在我想重新随机化它之前使用该整数，并且不再移动循环的索引，直到索引是唯一的。

这就是我的代码。

int citynum = 10;
double maxdist = 0;
int ants = 10;
Random random = new Random(500);
Random ran = new Random(citynum);
double dist;
double pair = 0;

ArrayList<TestCity> cities = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
ArrayList<ArrayList<Integer>> used = new ArrayList<>();
ArrayList<Integer> bestpath = new ArrayList<>();


for (int i = 0; i < citynum; i++) {
    dist = random.nextDouble();
    cities.add(new TestCity(dist, i + 1));
}

/**
 * generate paths
 */
for (int i = 0; i < ants; i++) {
    for (int k = 0; k < cities.size(); k++) {
        int j = ran.nextInt();
        int[] usedNum = new int[citynum];


        if (cities.get(j).isVisited() == false) {    
            cities.get(j).setVisited(true);
            pair += cities.get(j).getDistance();
            path.add(cities.get(j).getName());
        }
    }
    used.add(path);
    if(pair<maxdist){
        maxdist=pair;
        bestpath = path;
    }
}


System.out.println(path);

我的问题是在 spt 中，我在 for() 循环中使用随机数。我尝试使用整数数组来保留使用的随机数，但我只是在循环中迷失了。 谁能告诉我该怎么做？或者也许有一种更简单的方法，而不使用一些大型发布的算法？我不懂那些数学。

Answer 1

当您调用随机数/索引时，请使用 HashSet。假设你得到了随机索引 x。现在您检查它是否在 HashSet 中。如果不是，则将其添加到 HashSet 中并可以将其用作索引。如果它已经在 HashSet 中，则不使用它，只需调用获取另一个随机索引 y 即可。