Java TSP排列積分

爲我們實施最近鄰啓發式（我已經完成）的學校做項目，以及我們進行詳盡搜索的旅行銷售員問題（然後分析算法，它們的時間複雜度等）。我們的老師說要四處尋找代碼來使用（或修改）窮舉搜索部分，而不是像最近鄰居部分那樣對整個事物進行編程。我環顧四周，只發現與我們被指示如何執行程序無關的東西。與使用整數的典型問題相反，我們使用的是點（x，y）。我的目標是計算最短排列並能夠知道排列是什麼。所以我想有一個數組的數組（其中包含排列）。Java TSP排列積分

如果有人可以幫助我與詳盡的搜索，這將是很好的。

這裏是從我的代碼一些摘錄（成員變量，功能的兩個點之間計算距離，並且其中存儲所有的點）：

private int x; 
private int y; 
private boolean visited; 

public double dist(point pt){ 
    int xdist = this.getX() - pt.getX(); 
    int ydist = this.getY() - pt.getY(); 
    double xsr = xdist*xdist; 
    double ysr = ydist*ydist; 
    return Math.sqrt(xsr + ysr); 
} 

point[] points = new point[n];

任何幫助不勝感激。

來源

2012-09-05 lorenzo

單個TSP可能的解決方案本質上只是一個城市數組，代表了訪問它們的順序，而沒有起始城市。因此，假定n（城市數量）= 5。然後，一個可能的解決方案被表示爲長度爲4的數組。現在，您可以訂購多少種方式的城市[B，C，D，E] ？ BCDE，BCED，BDCE，BDEC，...這是4!或24種組合。所以對於n個城市你有(n-1)!組合。對於製造362880個組合的10個城市。對於20個城市或10^17個組合，如果您想將它們全部留在記憶中，您將會耗盡內存。

另外一個問題是，你將需要n可嵌套的for循環，但它是不可能的，只是寫那些循環，因爲有n個。（你可以開始書寫for() for() for() ...。所以，您的實現可能需要某種形式的walker approach，那就是你有一個循環，對所有組合蜱，很像與代表陣列中的1個指數每個數字一個數字時鐘。

來源

2012-09-06 06:42:09

感謝您的幫助。昨天晚上在做這件事（而沒有到任何地方）的時候，我開始想，我決定今天如何實施它。這是一個相當粗糙的方法，但它不會改變這個算法是O（n！）的事實。我將按照我的points數組中的索引來排列一個單獨的整數數組，然後我將使用這些索引作爲點的排列。如果我有更多時間「更高效」地做到這一點，我會這樣做，但由於它不會改變時間複雜度，所以我會堅持下去。 – lorenzo

你不需要生成所有排列/對給定實例解決方案（額外）的內存，你可以只寫在屏幕上...

在此實現看看https://github.com/stardog-union/pellet/blob/master/core/src/main/java/org/mindswap/pellet/utils/PermutationGenerator.java。
它產生每次致電getNext()一個新的解決方案。

public void PermGen() { 
    int[] tour; 
    PermutationGenerator x = new PermutationGenerator(N); 
    System.out.println(x.getTotal()); 
    while (x.hasMore()) { 
     tour = x.getNext(); 
     System.out.println(Arrays.toString(tour)); 
    } 
}

上面的Java代碼打印所有TSP實例解決方案...
當然你可以將它們保存（在文件（縣）爲例），但你需要TB的百來做到這一點。

來源

2017-08-12 16:53:43 elkrari

Java TSP排列積分

回答

相關問題