现在的位置: 首页 > 综合 > 正文

(三) 蛮力法

2014年09月05日 ⁄ 综合 ⁄ 共 2358字 ⁄ 字号 评论关闭

        蛮力法(brute force method,也称为穷举法或枚举法)是一种简单直接地解决问题的方法,常常直接基于问题的描述,所以,蛮力法也是最容易应用的方法。

蛮力法特性:

        (1)理论上,蛮力法可以解决可计算领域的各种问题。

        (2)蛮力法经常用来解决一些较小问规模的问题。

        (3)对于一些重要的问题(如排序、查找、串匹配),蛮力法可以设计一些合理的算法,这些算法具有实用价值,而且不受输入规模的限制。

        (4)蛮力法可以作为某类问题时间性能的下界,来衡量同样问题的其他算法是否具有更高的效率。


查找问题中使用蛮力法。


        顺序查找:


        是指在查找集合中一次查找值为k的元素,若查找成功,则给出元素在查找集合中的位置;若查找失败,则给出失败信息。

        【想法】:将查找集合放在一维数组中,然后从数组的一端向另一端逐个将元素与带查找值进行比较,若相等,则查找成功,给出该元素在查找中的序号;若整个数组检测完仍未找到与带差值相等的元素,则查找失败,给出失败标志0。我们在查找过程中还要注意下标是否越界的问题。

        算法的实现方法一:

        int SeqSearch1(int r[] ,int n, int k) //数组r[1] r[n]中存放查找集合。
        {
                int i = n;
               while(i>0 && r[i]!k)    //注意检测比较位置是否越界。
               {   i--;   }

                return  i;
        }


        上述算法我们每次都要去判断数组的下标是否越界,为了避免在查找过程中每一次比较前都要判断查找位置是否越界,可以设置观察哨,即将待查值放在查找方向的“尽头”处,则比较位置i至多移动到下标0处。改进的顺序查找算法c的代码如下所示:


        int SeqSearch(int r[] , int n, int k) //数组r[1] r[n]中存放查找集合。
        {
                int i = n;    //从数组的高端开始查找。
                r[0]=k;      //数组第一个元素放置要查找的元素。
                while(r[i] != k)  //不用检测和比较位置是否越界。
                {
                       i--;
                }
               return i;
        }



蛮力法解决0/1背包问题。


        【问题描述】:一个强盗去一个宝藏的山洞中取宝藏,但宝藏很多很多种,LV包,香奈儿钱包,劳力士刮胡刀,一颗超大的金珍珠等等,强盗带的仅仅有一个包,包中的容量就是那么大,能盛下的东西就那么多,每个珍宝都有自己的重量和价值,那强盗怎么装宝藏,让包中东西的价值最大,同时不超过包中的重量。你要是那个强盗怎么装入包中呢?这个强盗用蛮力法,就是在包中试装了各种宝藏,幸好,宝藏的品种没有超过十种。


        【官方描述】:
给定n个重量为{w1,w2,w3,....,wn} ,价值为{v1,v2,v3,.....vn}  的物品和一个容量为C的背包,0/1 问题背包问题,求这些物品中的一个最有价值的子集,并且能够装入背包中。


        【思路】:用蛮力法解决0/1背包问题,需要考虑n个给定物品的子集,找出所有重量不超过背包容量的子集,计算可能子集的总价值,然后找出价值最大的子集。


        【例题】:
        例如:给定4个重量为{7,3,4,5} ,价值为{42,12,40,25},和一个容量为10的背包。

        下表来描述蛮力法求解背包的过程。把四个包按照重量7 3 4 5 的顺序编号为1 2 3 4 。


        【复杂度分析】:

采用蛮力法求解0/1背包问题的时间复杂度为:T(n)=O(2的n次方)

        【C语言程序代码】:
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100	//最多可能物体数
struct goods	//物品结构体
{
	int sign;	//物品序号
	int w;	//物品重量
	int p;	//物品价值
}a[N];
bool m(goods a,goods b)
{
	return (a.p/a.w)>(b.p/b.w);
}
int max(int a,int b)
{
	return a<b?b:a;
}
int n,C,bestP=0,cp=0,cw=0;
int X[N],cx[N];
/*蛮力法求解0/1背包问题*/
int Force(int i)
{
	if(i>n-1){
		if(bestP<cp&&cw+a[i].w<=C){
			for (int k=0;k<n;k++)	X[k]=cx[k];//存储最优路径
			bestP=cp;
		}
		return bestP;
	}
	cw=cw+a[i].w;
	cp=cp+a[i].p;
	cx[i]=1;	//装入背包
	Force(i+1);
	cw=cw-a[i].w;
	cp=cp-a[i].p;
	cx[i]=0;	//不装入背包
	Force(i+1);
	return bestP;
}
int KnapSack1(int n,goods a[],int C,int x[])
{
	Force(0);
	return bestP;
}



蛮力法解决TSP问题。

        【问题描述】:TSP问题是指旅行家要旅行n个城市,然后回到出发城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。

        【思路】:采用蛮力法求解TSP问题的基本思想是,找出所有可能的旅行路线,即一次考察图中所有顶点的全排列,从中选取路径长度最短的简单回路(从起点出发能再回到起点)。

        【例题】: 如图所示无项带权图,TSP求解问题的过程表格如下。







代码略。


本节完毕,下一节第四节分治法。





抱歉!评论已关闭.