演算法筆記(三)|貪婪演算法(Greedy Algorithm)實作 in Java

Coding-X的課堂筆記(三)

對於貪婪演算法，簡單的理解就是 ，每次選擇中 ，都是選最佳解的選項 ，但不代表說每次的最佳解就是全體最佳解 ，那在這次 ，會使用旅行者問題來實作貪婪演算法 ，那規則是這樣 ，從任一城市出發，走訪每個城市一次，最後要回到原城市，不過每一次從上一個城市到下一個城市必選擇權重較小的路走，或當有複數個權重一樣的路，選擇城市編號較小的路走 。

實作方法:

1. 輸入n個城市後，生成n x n的矩陣來儲存路徑權重，例如:[0][1]就是城市A到B的權重是20。
2. 生成另一個矩陣trip，來儲存這個城市有沒有經過，用布林值來表示。

ajacencyMatrix = new int[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
ajacencyMatrix[i][j] = scanner.nextInt();

trip = new boolean[n];

3.生成3個int變數，分別為current、next、distance。

int current;
int next;
int distance;

4.寫一個函式，來比較哪一個城市是最近的。

public static int nextCity(int current){
   int distance = Integer.MAX_VALUE;
   int city = -1;
   for(int i = 0; i < trip.length; i++){
       if(i != current && !trip[i])//反向運算子
          if(ajacencyMatrix[current][i] < distance){
               distance = ajacencyMatrix[current][i];
               city = i;
           }
       }
return city;
}

5.遞迴呼叫(4)的函式，一邊放進path裏面去儲存來紀錄走過的點，一邊放進distance裏，之後最終比較距離時，會用到。

while(true){
next = nextCity(current);
// If all cities are passed by
if(next == -1){
distance += ajacencyMatrix[current][i];
path[index] = current;
path[index + 1] = i;
break;
}

// Travel

distance += ajacencyMatrix[current][next];
path[index] = current;
trip[current] = true;
current = next;
index++;
}

6.當break發生時，代表要儲存最終的距離了。

if(distance < shortest_path){
shortest_path = distance;
shortest_path_city = path.clone();
}

7.跑完輸入的城市數量的次數後，最終印出來。

System.out.print("The shortest path is: ");
for(int i = 0; i <= n; i++){
System.out.print(shortest_path_city[i]);
System.out.print(" ");
}
System.out.println("");
System.out.printf("length: %d", shortest_path);
}

附上程式碼讓大家參考喔 (*´∀`)~♥

總結

希望這些程式碼對大家有所幫助，假如能夠讓大家有所領悟的話，可以幫我按like讓我可以賺咖啡錢喔，我會很開心的 (ゝ∀･)。