蠻力法在求解最優解問題中的應用

1、TSP（旅行商問題）要求我們找出一條n個給定城市之間的最短路徑，使我們再回到出發的城市之前，對歐每個城市都只訪問一次。我們可以用賦權圖來描述這個問題，那么算法的目的就是求解一個圖的最短哈密頓回路問題。

哈密頓回路同樣可以定義為

其中第一個頂點和最后一個頂點相同，其他n-1個頂點互不相同。那么我們就可以通過生成n-1個中間城市的組合來的到所喲逇旅行線路，來出最短的線路。

import java.util.Scanner;public class Main {static int[][] a = new int[5][5];static int[] bestWay = new int[6];static int min = 99999999;static int sum = 0;static Scanner in = new Scanner(System.in);public static void main(String[] args) {/*** 假設a為1號點，b為2號點,c為3號點，d為4號點* 1 2 2* 1 3 5* 1 4 7* 2 3 8* 2 4 3* 3 4 1* */for (int i = 1; i < 7; i++) {int x = in.nextInt();int y = in.nextInt();int z = in.nextInt();a[x][y] = z;a[y][x] = z;}for (int i = 2; i < a.length; i++) {for (int j = 2; j < a.length; j++) {if (j != i) {for (int k = 2; k < a.length; k++) {if (k != i && k != j) {sum = a[1][i] + a[i][j] + a[j][k] + a[k][1];if (min > sum) {min = sum;bestWay[1] = 1;bestWay[2] = i;bestWay[3] = j;bestWay[4] = k;bestWay[5] = 1;}}}}}}for (int i = 1; i < bestWay.length-1; i++) {System.out.print(bestWay[i] + "-->");}System.out.println(bestWay[bestWay.length-1]);System.out.println(min);} }

發現問題：我們可以發現這有3對不同的線路，而對于每隊線路中，不同的只是線路的方向。

優化思路：固定住每條線路的方向，將頂點排列數目減半。

實際上用蠻力方法來解決這種問題是極為不明智的，這里只是給出一個思路，當頂點數目過多時還是要采用諸如動態規劃，貪心等方法來優化的。

2、背包問題給定n個重量為w1，w2，w3...wn, 價值為v1，v2，v3...vn的物品和一個稱重為C的背包，求這些物品中一個最有價值的子集。

import java.util.Scanner;public class Main {static int n, c;static int max = 0;static int[] w, v;static Scanner in = new Scanner(System.in);public static void main(String[] args) {n = in.nextInt();c = in.nextInt();w = new int[n+1];v = new int[n+1];for (int i = 1; i <= n; i++) {w[i] = in.nextInt();v[i] = in.nextInt();}/*** 對于n個物品，會存在2^n個中組合方式* 采用二進制的1,0來表示物品是否被選擇，比采用數組要方便，數組每次都要遍歷一遍* */for (int i = 0; i <= Math.pow(2, n); i++) {int k = i;int tempw = 0;int tempv = 0;for (int j = 1; j <= n; j++) {/*** 二進制位對應w[],v[]* 每次檢查末位數字是否為1，之后數去除末位數字* */if (k % 2 == 1) {tempw += w[j];tempv += v[j];}k /= 2;}if (tempw <= c) {if (tempv > max) {max = tempv;}}}System.out.println(max);} } 發現問題：顯然2^n次的迭代始終效率都是低下的

優化思路：背包問題最好的解決方法自然是用動態規劃來解決，當然也可以用回溯或者分支界限法。

3、分配問題可以理解為有n個任務需要分配給n個人執行，一個任務對應一個人。對于每一對i,j=1,2,3,...,n來說，將第j個任務分配給第i個人的成本是c[i,j]，求出總成本最小的方案。我們當然不能從每一行中選出最小的元素，因為這寫最小的元素可能在同一列。這個問題和旅行商問題有相似之處，基本思路也是將數據放到一個成本矩陣C中，枚舉出每種情況，找出成本最小值

代碼基本和TSP一樣，略。

發現問題：同樣是大數據量處理起來的效率問題

優化思路：匈牙利算法

總結

以上是生活随笔為你收集整理的蛮力法在求解最优解问题中的应用（JAVA）--旅行家问题、背包问题、分配问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。