网站开发微信提现功能,广东智能网站建设费用,ps做网站画布多大,四川网站营销seo什么价格蛮力法在求解最优解问题中的应用
1、TSP#xff08;旅行商问题#xff09;要求我们找出一条n个给定城市之间的最短路径#xff0c;使我们再回到出发的城市之前#xff0c;对欧每个城市都只访问一次。我们可以用赋权图来描述这个问题#xff0c;那么算法的目的就是求解一个…蛮力法在求解最优解问题中的应用
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个重量为w1w2w3...wn, 价值为v1v2v3...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[n1];v new int[n1];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,j1,2,3,...,n来说将第j个任务分配给第i个人的成本是c[i,j]求出总成本最小的方案。我们当然不能从每一行中选出最小的元素因为这写最小的元素可能在同一列。这个问题和旅行商问题有相似之处基本思路也是将数据放到一个成本矩阵C中枚举出每种情况找出成本最小值 代码基本和TSP一样略。
发现问题同样是大数据量处理起来的效率问题
优化思路匈牙利算法
