随机旅行世代问题 [英] Random Tour Generation Issues

问题描述

我试图从图中产生一个随机游。我正在使用adjacency-list方法。

I am trying to generate a random tour from the graph. I am using the adjacency-list method.

顶点存在问题。当我添加一个顶点到一个特定的列表时，顶点会被添加到图中的所有列表中。我不懂为什么！以下是代码：

There is a problem with the vertices. When I add a vertex to a particular list, the vertex gets added to all the lists in the graph. I do not understand why! Here's the code:

public static void main(String[] args) {
    defaultData(6);
}

public static void defaultData(int n) {
    Integer costs[] = { 26, 95, 38, 74, 80, 73, 73, 92, 22, 97, 13, 81, 41,
      17, 4, 2, 47, 54, 21, 68, 78, 4, 77, 3, 66, 55, 99, 42, 62, 39, 8, 36,
      53, 74, 26, 8, 42, 66, 30, 58, 69, 14, 49, 39, 85, 98, 72, 3, 18, 99,
      96, 66, 64, 36, 17, 44, 70, 0, 8, 14, 62, 41, 84, 59, 94, 27, 5, 27,
      96, 10, 15, 52, 43, 20, 2, 86, 45, 43, 32, 17, 49, 92, 9, 15, 6, 49,
      72, 7, 51, 21, 2, 26, 63, 82, 98, 48, 21, 96, 16 };

    ArrayList<ArrayList<Integer>> costGraph = new ArrayList<>();
    ArrayList<ArrayList<Integer>> completeGraph = new ArrayList<>();

    Random rand = new Random(System.currentTimeMillis());

    int costIndex = 0;
    for (int i = 0; i <= n; i++) {
        ArrayList<Integer> cost = new ArrayList<>();
        ArrayList<Integer> edge = new ArrayList<>();

        for (int j = 0; j <= n; j++) {
            if (i == j) {
                continue;
            }

            edge.add(j);
            cost.add(costs[costIndex]);
            costIndex++;
        }

        completeGraph.add(edge);
        costGraph.add(cost);
    }

    System.out.println(completeGraph);

    ArrayList<ArrayList<Integer>> dummyGraph =
      (ArrayList<ArrayList<Integer>>)completeGraph.clone();
    ArrayList<ArrayList<Integer>> randomTour = new ArrayList<>();
    ArrayList<Integer> dummyList = new ArrayList<>();

    for (int i = 0; i <= n; i++) {
        randomTour.add(dummyList);
    }

    System.out.println(dummyGraph);

    int edgeCount = 0;
    Integer row = rand.nextInt(n);
    Integer start = row;

    while(edgeCount <= n-1){
        //dummyList = dummyGraph.get(row);

        // To keep the bounds of the random equal
        // to the new reduced size of the lists in the graph 
        Integer col = dummyGraph.get(row).get(rand.nextInt(n-edgeCount));

        randomTour.get(row).add(col);

        System.out.println(row);
        System.out.println(randomTour);

        edgeCount++;
        for(int k = 0; k < n; k++)
            dummyGraph.get(k).remove(row);
        row = col;
    }

    randomTour.get(row).add(start);
    System.out.println(randomTour);
}

我会非常感谢及时回复。提前致谢！

I would be very grateful for a timely response. Thanks in advance!

推荐答案

您不想这样做：

You don't want to do this:

for (int i = 0; i <= n; i++) {
    randomTour.add(dummyList);
}

它会不断添加相同的引用次数，所以 ArrayList s在 ArrayList 中实际上是同一个对象。

It keeps adding the same reference lots of times, so all the ArrayLists in the ArrayList are actually the same object.

取而代之你想这样做：

for (int i = 0; i <= n; i++) {
    randomTour.add(new ArrayList<Integer>());
}

这样 ArrayList ArrayList 中的所有实例都不相同。

That way the ArrayList instances in the ArrayList are all different.

我希望这个答案足够及时！

I hope this answer was timely enough!

这篇关于随机旅行世代问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！