JAVA算法合集：冒泡+插入+快速+希尔+归并+桶+基数+剪枝+回溯算法( 三 ) _JAVA算法

剪枝算法在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

文章插图

回溯算法回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
最短路径算法从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA算法等。
最大子数组算法
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n) 。比如输入a[]={31,-41,59,26,-53,58,97,-93,-23,84}，那么程序的输出为a[2...6]的和，即187 。
《编程珠玑》给出了一个时间复杂度为O(n)的扫描算法。代码非常简练，但得稍微思考一下才能明白。
首先我们必须找到最大的子数组的起始点，从a[0]开始扫描，并且逐一累加，累加和存储到max_ending_here变量。当累加到i,即a[0]+a[1]+...a[i]的和小于0时，我们认定最大子数组绝对不包括a[0]~a[i],就可以更新最大子数组的起始位置begin=i+1，并将max_ending_here清0 。所以说max_ending_here始终存储的是累加和大于0的子数组累加和。这时还需要另外一个变量max_sofar存储当前的最大子数组累加和。每扫描一个数据就将max_ending_here和max_sofar进行一次比较，保证max_sofar始终存储目前最大的子数组累加和。代码如下：

#include "stdafx.h"#include "stdio.h"#include <IOStream>using namespace std; int max_subarray(const int a[],int n){	int max_ending_here=0;	int max_sofar=0;	int begin=0;	int end=0;	int i=0;	for(i=0;i<n;i++)	{if(max_ending_here+a[i]>0)max_ending_here=max_ending_here+a[i];else{begin=i+1; //注意begin更新为i+1而不是imax_ending_here=0;}cout<<"max_ending_here: "<<max_ending_here<<endl;if(max_ending_here>max_sofar){max_sofar=max_ending_here;end=i;}cout<<"max_sofar: "<<max_sofar<<endl;	}	cout<<"max subarray begin="<<begin<<" "<<"end="<<end<<endl;	return max_sofar;} int _tmain(int argc, _TCHAR* argv[]) {	int sum;	int a[]={31,-41,59,26,-53,58,97,-93,-23,84};sum= max_subarray(a,10);	cout<<sum<<endl;getchar();	}

 最长公共子序算法/* * 最长公共子序列算法 。*/ public class LCS {public static void main(String[] args) {// TODO Auto-generated method stubString arr1="abcdefghijk";String arr2="adefabcdk";String subMax="";subMax=get_LCS_sub(arr1,arr2);System.out.println("LCS..."+subMax);}private static String get_LCS_sub(String arr1, String arr2) {// TODO Auto-generated method stubString sub="";int ti,tj;int max=0;int rs=0,re=0;//记录最长子串在arr1中的开始和结束位置 。for(int i=0;i<arr1.length();){ti=i;//记录i当前位置 。for(int j=0;j<arr2.length();){tj=j;//记录j当前位置 。while(i<arr1.length()&&j<arr2.length()&&arr1.charAt(i)==arr2.charAt(j)){i++;j++;}j=tj+1;if((i-ti)>max){max=i-ti;//记录最长子串 。rs=ti;re=i;}}i=ti+1;}sub=arr1.substring(rs, re);return sub;}

最小生成树算法现在假设有一个很实际的问题：我们要在 n 个城市中建立一个通信网络，则连通这 n 个城市需要布置 n-1 一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
于是我们就可以引入连通图来解决我们遇到的问题，n 个城市就是图上的 n 个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有 n 个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。
构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST 性质（假设N=(V,{E})是一个连通网，U 是顶点集 V 的一个非空子集，如果（u，v）是一条具有最小权值的边，其中 u 属于 U，v 属于 V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使用 MST 性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。