0

我被困在学校项目的这一部分，我必须在两个坐标之间找到最短的路线（旅行推销员问题）。我在这里做了一点点东西来获取最近邻居的坐标，但是一些坐标有相同的最近邻居，我不想要那个。

我想了一些办法来解决这个问题，但它不起作用，我不知道为什么。

distance是当前位置与其他位置之间的当前距离。shortestDistance我认为有点不言自明。

locations[20][3]是一个二维数组，我在其中存储每个坐标的 Xco-ord、Yco-ord 和最近邻。X 在 [x][0] 中，Y 在 [x][1] 中，邻居在 [x][2] 中

for(int i = 0; i < 20; i++){
            int shortestDistance = 100;
            int distance;
            //Looking for nearest neighbour 20 times 
            for(int j = 0; j < 20; j++){
                //Looking for the closest neighbour here
                distanceX = locations[i][0] - locations[j][0];
                distanceY = locations[i][1] - locations[j][1];
                //To prevent a negative distance:
                if(distanceX < 0){
                    distanceX = distanceX * -1; 
                }
                if(distanceY < 0){
                    distanceY = distanceY * -1;
                }
                //Add distance
                distance = distanceX + distanceY;
                //If current distance is shorter then the shortestdistance, to prevent it does'nt see itself as 'neighbour' and to prevent another co-ord has the same neighbour, which happens in isOk(); 
                if(distance < shortestDistance && distanceX + distanceY != 0 && isOk(j)){
                    shortestDistance = distance;
                    locations[i][2] = j;
                }
            }
        }

函数 isOk 是：

private boolean isOk(int j){
    boolean result = false;
    for(int i = 0; i < 20; i++){
        if(locations[i][2] == j){
            result = false;
        }
        else{
            result = true;
        }
    }
    return result;
}

所以，我要问的是我做错了什么？我仍然得到一些与其最近邻居具有相同项目的项目（在 20 * 10 存储中）。

4

1 回答 1

1

您可能必须将邻居初始化为适合您的isOK方法的东西。例如，这样的值是-1。

for(int i = 0; i < 20; i++) locations[i][2] = -1;

还包含一个小isOk错误。j当发现作为另一个位置的邻居时，应该停止循环：

private boolean isOk(int j){
    for(int i = 0; i < 20; i++){
        if (locations[i][2] == j) return false;
    }
    return true;
}
于 2013-04-26T11:49:10.287 回答