精华内容
下载资源
问答
  • 使用启发式,f(n) = h(n) 距离目标最近,最快找到解 A*搜索 从松弛问题出发设计可采纳的启发式 减小了行动限制的问题称为松弛问题。松弛问题的状态空间图原有状态空间的超图,因为减少限制导致图中边的...

    基本概念

    在这里插入图片描述
    最佳优先搜索的评价函数f(n) 由启发函数(heuristic function)构成
    h(n) = 结点n到目标结点的最小代价路径的代价估计值

    在这里插入图片描述
    启发式函数h(n): n到目标s的估计代价
    如果估计代价≤实际代价,那么称这个启发式函数是可采纳的

    获得可启发式的方法: 1. 松弛问题:减少对动作的限制
    2. 子问题: 一个目标分成多个子目标
    3. 机器学习

    贪婪最佳优先搜索

    使用启发式,f(n) = h(n)
    距离目标最近,最快找到解
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    A*搜索

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    A*搜索和一致代价搜索搜索的实现非常的相似,仅仅是多了个启发式函数

    def aStarSearch(problem, heuristic=nullHeuristic):
        """Search the node that has the lowest combined cost and heuristic first."""
        "*** YOUR CODE HERE ***"
        pqueue = util.PriorityQueue()
        start_state = problem.getStartState()
        search_already = []
        pqueue.push((start_state,[]),nullHeuristic(start_state,problem))
        while not pqueue.isEmpty():
            state,action = pqueue.pop()
            if problem.isGoalState(state):
                return action
            if state not in search_already:
                successor = problem.getSuccessors(state)
                for next_node in successor:
                    next_state = next_node[0]
                    next_action = next_node[1]
                    pqueue.push((next_state,action+[next_action]),problem.getCostOfActions(action+[next_action])+ heuristic(next_state,problem))
            search_already.append(state)
        util.raiseNotDefined()
    
    

    从松弛问题出发设计可采纳的启发式

    在这里插入图片描述

    减小了行动限制的问题称为松弛问题。松弛问题的状态空间图是原有状态空间的超图,因为减少限制导致图中边的增加。

    从子问题出发设计可采纳的启发式——模式数据库

    在这里插入图片描述

    子问题的最优解代价是完整问题的解代价的下界。存储每一个子问题代价的实例,作为启发式用。两个不想叫的子问题的代价之和是整个问题的下界(不相交的模式数据库)

    从经验中学习启发式,线性回归方程等。

    课后习题

    3.1
    在这里插入图片描述

    答:在制定目标时,我们决定我们对世界的哪些方面感兴趣,哪些方面可以被忽视或抽象化。然后,在问题描述中,我们决定如何操纵重要的方面(而忽略其他方面)。如果我们先制定问题,我们就不知道应该包括什么,也不知道遗漏了什么。也就是说,在目标制定、问题制定和问题解决之间有一个循环,直到一个人找到一个足够有用和有效的解决方案。

    3.2
    在这里插入图片描述

    答案A.我们将定义坐标系,使得迷宫的中心位于(0,0),迷宫本身是(1,1)到(1,1)的正方形。
    初始状态:机器人在坐标(0,0),面向北。
    目标测试:X>1或Y>1,其中(x,y)为当前位置。
    行动:向前移动任何距离D;将方向机器人改变方向。
    成本函数:移动的总距离。由于机器人的位置是连续的,所以状态空间是无限大的。

    答案B.将记录机器人目前的交叉口的状态,以及它面临的方向。在每条走廊的尽头,离开迷宫,我们将有一个出口节点。我们假设某个节点对应于迷宫的中心。
    初始状态:位于朝北迷宫中心。
    目标测试:在出口节点。
    行动:如果有一个交叉口,就移到前面的下一个十字路口;转向一个新的方向。
    成本函数:总移动距离。有4N个状态,其中n是交叉口的数目。

    答案C.
    初始状态:在迷宫的中心。
    目标测试:在退出节点处。
    行动:移动到北、南、东或西的下一个交叉点。
    成本函数:移动的总距离。
    我们不再需要跟踪机器人的方位,因为它与预测我们的行动的结果无关,而且不是目标测试的一部分。执行该计划的电机系统需要跟踪机器人的当前取向,以知道何时旋转机器人。

    答案D.
    状态抽象:(i)忽略机器人离地面的高度,不管它是否从垂直方向倾斜。
    (ii)机器人只能在四个方向上面对。
    (iii)世界的其他部分被忽略:其他机器人在迷宫中的可能性,天气等。
    动作抽象:(i)我们假设我们可以安全访问的所有位置:机器人无法卡住或损坏。
    (ii)机器人可以无电源限制地移动。
    (iii)简化的移动系统:向前移动一定距离,而不是控制每个单独的马达并观看传感器以检测碰撞。

    3.6
    在这里插入图片描述
    在这里插入图片描述

    状态:(V(a),V(b),V©);V(a),V(b),V©是各壶中水的体积;V(a)⋲Z,0<=V(a)<=12;V(b)⋲Z,0<=V(b)<=8;V©⋲Z,0<=V©<=3;

    初始状态:V(a)=V(b)=V©=0

    行动:这个任务环境中,每个状态可执行的行动共有12种。分别为:将a中的水倒入b中;将a中的水倒入c中;a中的水倒在地上;将a装满;将b中的水倒入a中;将b中的水倒入c中;b中的水倒在地上;将b装满;将c中的水倒入a中;将c中的水倒入b中;将c中的水倒在地上;将c装满。

    转移模型:(V’(a),V’(b),V’©) = result(V(a),V(b),V©,action)
    其中V(a),V(b),V©是执行动作前各壶中水的体积,action为执行的动作,V’(a), V’(b), V’©是执行动作后各壶中水的体积。
    对于不同action,result函数计算公式如下:
    1.将a中的水倒入b中。V’(a)=V(a)-min(8-V(b),V(a));V’(b)=V(b)+min(8-V(b),V(a));V’©=V©
    2.将a中的水倒入c中。V’(a)=V(a)-min(3-V©,V(a));V’(b)=V(b);V’©=V©+min(3-V©,V(a))
    3.a中的水倒在地上。V’(a)=0;V’(b)=V(b);V’©=V©
    4.将a装满。V’(a)=12;V’(b)=V(b);V’©=V©
    5.将b中的水倒入a中。V’(a)=V(a)+min(12-V(a),V(b));V’(b)=V(b)-min(12-V(a),V(b));V’©=V©
    6.将b中的水倒入c中。V’(a)=V(a);V’(b)=V(b)-min(3-V©,V(b));V’©=V©+min(3-V©,V(b))
    7.将b中的水倒在地上。V’(a)=V(a);V’(b)=0;V’©=V©
    8.将b装满。V’(a)=V(a);V’(b)=8;V’©=V©
    9.将c中的水倒入a中。V’(a)=V(a)+min(12-V(a),V©);V’(b)=V(b);V’©=V©-min(12-V(a),V©);
    10.将c中的水倒入b中。V’(a)=V(a);V’(b)=V(b)+min(8-V(b),V©);V’©=V©-min(8-V(b),V©)
    11.将c中的水倒在地上。V’(a)=V(a);V’(b)=V(b);V’©=0
    12.将c装满。V’(a)=V(a);V’(b)=V(b);V’©=3

    目标测试:V(a)=1 or V(b)=1 or V©=1

    路径消耗:每一步耗散值为1,整个解路径的耗散值是路径中的步数。

    展开全文
  • 贪心算法::启发式搜索

    千次阅读 2012-10-29 09:26:04
    则不宜使用,常用的做法是剪枝,剪枝是一种形象的描述,因为按深搜的算法,图可以描述为与之对应的树或森林,而剪枝的意思就是去掉某些子树,为什么要去掉,这里要用到一个剪枝判断,判断的方法是具体问题具体分析,...
    蛮干算法的成功完全是借助于计算机运算的快速,如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多,则不宜使用,常用的做法是剪枝,剪枝是一种形象的描述,因为按深搜的算法,图可以描述为与之对应的树或森林,而剪枝的意思就是去掉某些子树,为什么要去掉,这里要用到一个剪枝判断,判断的方法是具体问题具体分析,但是有一点是要考虑到的,剪枝的高效性是建立在判断的额外开销上的,如果这里的开销大,则剪枝只会宣告失败。

    而更好的做法是运用“贪心策略”。

    【贪心算法】
    贪心算法(也叫贪婪算法)不是某种特定的算法,而是一类抽象的算法,或者说只是一种思想,它的具体表现在,对解空间进行搜索时,不是机械地搜索,而是对局部进行择优选取,贪心算法的目的不是为了找到全部解,也当然找不出最优解,而只是找出一种可行解,这样就会得到惊人的高效性。因此,贪心算法也叫启发式搜索,这种启发就是所谓的“贪心策略”。

    以马踏棋盘问题为例,问题描述:在国际象棋的棋盘上指定一个初始马位置,一匹马从这个位置出发,经过不重复的走动,直到踏遍整个棋盘,输出一种可行路径。

    对8×8的棋盘来说,马踏棋盘的解是一个天文数字,相当之多,而采用蛮干算法,求一个解的时候会非常吃力,因此采用贪心算法。这里选取的贪心策略是,在某个马位置顶点的后继顶点(子结点)中,择优选取那些出口更小的顶点进行搜索,出口的意思就是这个点能跳到的可行位置的路径数,这样的贪心策略是容易被人接受的,一开始往出口少的点跳,则往后出口多的点就多,能跳通的可能性就大,而事实也证明了,如果采用这样的策略在求一个解时几乎不需要回溯,对于更大的棋盘也如此。



    #include "stdio.h"
    class horse
    {
    public:
        horse(int,int);
        ~horse();
        void solve(int,int);
    protected:
        void dfs(int,int,int);
        int **data;
        int *head;
        int width;
        int height;
        int size;
        int count;
    };
    struct hnode
    {
        int x;
        int y;
        int weight;
    };
    horse::horse(int n,int m)
    {
        width=n;
        height=m;
        size=n*m;
        head=new int[size];
        data=new int*[m];
        for(int i=0;i<m;++i)
        {
            data[i]=head+i*n;
            for(int j=0;j<n;++j)
                data[i][j]=0;
        }
    }
    horse::~horse()
    {
        delete[] data;
        delete[] head;
    }
    void horse::solve(int x,int y)
    {
        try
        {
            count=0;
            dfs(x,y,1);
            printf("无解!\n回溯%d次\n",count);
        }
        catch(int)
        {
            for(int i=0;i<height;++i)
            {
                printf("\n");
                for(int j=0;j<width;++j)
                    printf(" %02d",data[i][j]);
            }
            printf("\n回溯%d次\n",count);
        }
    }
    void horse::dfs(int x,int y,int c)
    {
        static int dx[8]={-1,-1,1,1,-2,-2,2,2};
        static int dy[8]={-2,2,-2,2,-1,1,-1,1};
        hnode hn[8];
        data[y][x]=c;
        if(c==size)throw(1);
        for(int i=0;i<8;++i)
        {
            int tx,ty;
            hn[i].x=tx=x+dx[i];
            hn[i].y=ty=y+dy[i];
            if(tx<0||tx>=width||ty<0||ty>=height||data[ty][tx]>0)
            {
                hn[i].weight=-1;continue;
            }
            hn[i].weight=0;
            for(int j=0;j<8;++j)
            {
                int mx,my;
                mx=tx+dx[j];
                my=ty+dy[j];
                if(mx>=0&&mx<width&&my>=0&&my<height&&data[my][mx]==0)
                    hn[i].weight++;
            }
            if(hn[i].weight==0)
                hn[i].weight=9;
        }
        for(i=0;i<7;++i)
            for(int j=i+1;j<8;++j)
                if(hn[i].weight>hn[j].weight)
                {
                    hnode temp=hn[i];
                    hn[i]=hn[j];
                    hn[j]=temp;
                }
        for(i=0;i<8;++i)
            if(hn[i].weight>0)
                dfs(hn[i].x,hn[i].y,c+1);
        data[y][x]=0;
        ++count;//回溯次数
    }
    void main()
    {
        horse a(8,9);//width=8 * height=9的盘棋
        a.solve(0,0);//初始棋子位置
    }



    展开全文
  • 题目描述 FJ的奶牛想要快速计算整数P的幂 (1 <= P <=20,000),它们需要你的帮助。因为计算极大数的幂,所以它们同一时间仅能使用2个存储器,每个存储器可记录某个... 例如, 如果他们想计算x^31, 一种计算方法是...

    题目描述

    FJ的奶牛想要快速计算整数P的幂 (1 <= P <=20,000),它们需要你的帮助。因为计算极大数的幂,所以它们同一时间仅能使用2个存储器,每个存储器可记录某个结果值。 第一件工作是初始化存储器内的值一个为底数x, 另一个为1。 奶牛可以相乘或相除2个存储器中的值,并把结果存在其中某个存储器内,但所有存储的结果必须是整数。 例如, 如果他们想计算x^31, 一种计算方法是:

    WV1 WV2
    开始: x 1
    存储器1和存储器1相乘,结果存于存储器2: x x^2
    存储器2和存储器2相乘,结果存于存储器2: x x^4
    存储器2和存储器2相乘,结果存于存储器2: x x^8
    存储器2和存储器2相乘,结果存于存储器2: x x^16
    存储器2和存储器2相乘,结果存于存储器2: x x^32
    存储器2除以存储器1,结果存于存储器2: x x^31
    因此, x^31可以通过6次计算得出。给出要计算的幂次,要求求出最少需要几次计算。

    输入格式
    仅一个整数: P。

    输出格式
    仅一个整数:最少计算次数。

    样例数据
    input

    31
    output

    6

    题目大意

    有两个数,分别是1100;每次选取其中两个相同或不同的数相加或相减,每次替换掉其中的一个数,并在保证每一个数都是非负数的前提下不断进行这样的操作,问至少要操作多少次才能使其中的一个数变成n。

    题解

    这道题由于边权为11,可以选择使用正常的广度优先搜索算法;但是搜索状态有ans10ans^{10},因此我们需要用其他算法来解决此题。

    我们可以使用启发式AA*算法来解决,可以设计估价函数为:

    • f(now)=nf(now)=当前状态的任意一个数\ge n的最小步数
    • 由于自加最快,不断对最大数进行*2操作即可。
    • 一定可以保证优于最优策略:如果步数=n=n不用说,直接可以到达最优决策。如果操作步数&gt;n&gt;n,要么通过若干次相减得到,要么直接无解,但是一定可以小于最优决策。

    但是这样的AA*算法仍然有超时的可能,我们还需要对此进行一系列的剪枝,对于每一个状态(x,y,v)(x,y,v),表示两个数分别为x,yx,y且满足x&gt;yx&gt;y,操作步数为vv,则有:

    • 如果xxyy是负数,则是一组非法解。
    • 如果x&gt;nx&gt;ny=0y=0,则不论如何都不能达到nnxx无法通过yy变小,只能通过自减变成00;若如此,则无法通过自身与yy变大达到nn)。
    • 如果n mod gcd(x,y) ≠ 0n\ mod\ gcd(x,y)\ =\not\ 0,则无法通过加减操作得到最优解(此时需要意会 )。
    • 如果x = yx\ =\ y,则相当于状态(x,z),x≠z(x,z),x=\not z的自加自减操作,是一种等效的状态,因此可以剪枝。
    • 显然对于每一个状态到需要用HashHash算法解决;如果当前状态的步数\ge该状态的最优步数, 则剪枝。

    注意

    • 对于AA*算法,要设计两个关键字;第一关键字为深度+估价函数,第二关键字为估价函数。因为第二关键字越少,基于底层的搜索层数也越少,可以在很大情况下减少搜索树的规模。

    代码如下:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1000000;
    const int V = 100000;
    int n,tot,ans;
    int Link[V],X[N],Y[N],Next[N],v[N];
    
    struct node
    {
    	int x,y,v;
    	int f (void)
    	{
    		int tx = x;
    		int cnt = 0;
    		while (tx<n) tx<<=1, cnt ++;
    		return cnt;
    	}
    	friend bool operator < (node a,node b)
    	{
    		//if (a.v+a.f() ^ b.v+b.f()) 
    			return a.v+a.f() > b.v+b.f();
    		//else 
    		//	return a.f() > b.f();
    	}
    };
    
    priority_queue < node > q;
    
    inline int Hash (int x,int y)
    {
    	int num = x*47+y*991;
    	return num%99991;
    } 
    
    void add (int x,int y,int num)
    {
    	tot ++;
    	Next[tot] = Link[Hash(x,y)];
    	X[tot] = x;
    	Y[tot] = y;
    	v[tot] = num;
    	Link[Hash(x,y)] = tot;
    }
    
    int ask (int x,int y)
    {
    	for (int i=Link[Hash(x,y)];i;i=Next[i]) 
    	    if (x == X[i] && y == Y[i]) 
    	        return v[i];
    	return -1;
    }
    
    pair<int,int> New(int x,int y,int num)
    {
    	if (num == 0) return make_pair(x+x,y);
    	if (num == 1) return make_pair(x+x,x);
    	if (num == 2) return make_pair(y+y,y);
    	if (num == 3) return make_pair(max(y+y,x),min(y+y,x));
    	if (num == 4) return make_pair(x+y,y);
    	if (num == 5) return make_pair(x+y,x);
    	if (num == 6) return make_pair(x-y,x);
    	if (num == 7) return make_pair(max(x-y,y),min(x-y,y));
    	if (num == 8) return make_pair(y,0);
    	if (num == 9) return make_pair(x,0);
    }
    
    int gcd(int a,int b)
    {
    	if (b == 0) return a;
    	return gcd(b,a%b);
    }
    
    int main(void)
    {
    	freopen("power.in","r",stdin);
    	freopen("power.out","w",stdout);
    	tot = 0;
    	cin>>n;
    	add(1,0,0);
    	q.push(node{1,0,0});
    	while (q.size())
    	{
    		node top=q.top();
    		q.pop();
    		if (top.x == n || top.y == n) 
    		{
    			ans = top.v;
    			break;
    		} 
    		if (top.v > ask(top.x,top.y)) continue;
    		for (int i=0;i<10;++i)
    	    {
    	    	pair<int,int> Next = New(top.x,top.y,i);
    	    	int nx = Next.first;
    	    	int ny = Next.second;
    	    	if (nx < 0 || ny < 0) continue;
    			if (nx == ny) continue;
    	    	//等效状态 
    	    	if (ask(nx,ny) ^ -1 && ask(nx,ny) < top.v+1) continue;
    	    	//相同状态下访问步数少 
    	    	if (n % gcd(nx,ny)) continue;
    	    	//无解 
    	    	if (nx > n && ny == 0) continue;
    	    	//无解 
    	    	add(nx,ny,top.v+1);
    	    	q.push(node{nx,ny,top.v+1});
    	    }
    	}
    	cout<<ans<<endl;
    	return 0;
    }
    
    展开全文
  • 实用算法实现-第 14 篇 启发式搜索

    千次阅读 2011-10-23 00:15:58
    A*(A star)算法是一种很好的树搜索策略,在许多人工智能的书籍中有所介绍。比如《人工智能,一种现代方法》和《人工智能,复杂问题求解的结构和策略》。 [i]文介绍到,A*算法使用估价函数F(N)来估算从初始状态S到...

    14.1    A*搜索

    A*(A star)算法是一种很好的树搜索策略,在许多人工智能的书籍中有所介绍。比如《人工智能,一种现代方法》和《人工智能,复杂问题求解的结构和策略》。

    [i]文介绍到,A*算法使用估价函数F(N)来估算从初始状态S到当前状态N,再到目标状态T需要的最小步数。有公式:

    F(N) = G(N) + H(N)

    其中,G(N)是起始状态S到当前状态的实际代价G(N),它比最佳路径的代价G*(N)大。

    H(N)是从当前状态到目标状态T的实际代价的估算值H*(N),它比实际代价H(N)大。

    对于一个起始状态到当前状态的实际路径,G(N)是已经决定的。H(N)的选择则至关重要。有两个限制:

    1. H(N)一定要小于等于当前结点N至目标结点T的实际代价。

    2. 任意结点的F值必须大于其父辈状态的F值,即F单调递增。

    当估价函数F满足以上两个限制条件,则启发式搜索算法一定能得出问题的最优解。

    14.1.1   实例

    PKU JudgeOnline, 1077, Eight.

    14.1.2   问题描述

    15数码游戏就是完成类似下面的转换的一种游戏:

    1  2 3  4    1 2  3  4   1  2  3 4    1  2 3  4

    5  6 7  8    5 6  7  8   5  6  7 8    5  6 7  8

    9  x 10 12   9 10  x 12    9 10 11 12    9 10 11 12

    1314 11 15   13 14 11 15   13 14 x 15   13 14 15  x

               r->           d->           r->

        8数码游戏类似,只不过只有8个数码而已。

        给出8数码游戏的一个初始状态,求达到目标状态的一个解,不要求是最优解。如果没有解,输出“unsolvable”。

    14.1.3   输入

    2 3  4  1 5  x  7 6  8

    1.1.4   输出

    ullddrurdllurdruldr

    14.1.5   分析

    《人工智能,一种现代方法》对使用A*算法解决八数码问题进行了深入的分析。提出了两种启发函数的策略:

    1. h1 = 不在位的棋子的总数。

    2. h2 = 所有棋子到其目标位置的曼哈顿距离的总和。

    并且通过实验,得到h2的性能总是优于h1。

    具体实现中,用到最小堆实现的优先队列。

    这里还需要用到一个排列到整数的映射方法,以判断一种状态是不是已经遍历过。一个具体的映射方法如下:

    把9看成插到8的排列中,那么有9种插法,可以把362880等分成9段,分别代表一个位置,每段递归处理。

    令pos(a)为数字a在排列中排在a前面并且小于a的数字的个数,那么有伪代码:

    int n=1;

    for (int i=1; i<10; i++)

    {

         n+=pos(i)*(i-1)!;

    }

         下面程序中int calPos1(node *temp)和int calPos(node *temp)就是两种映射方法。

    也许[ii]中介绍的排列的“反序”概念,能很好地用来解释上面这个算法。

    14.1.6   程序

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    bool visited[362880];
    #define maxNum     10000000
    #define MAX        0x7F7F7F7F
    struct tile{
         int x;
         int y;
    };
    #define maxLength 100//貌似最数码游戏的解长度为...
    struct node{
         tile pos[3][3];
         int key;
         charop[maxLength];
         int blankX;
         int blankY;
    };
    nodeminHeap[maxNum];
    int heapSize;
    void minHeapify(int i)
    {
         int l;
         int r;
         int min;
         node temp;
         l = i * 2;
         r = i * 2 + 1;
         min = i;
         if((l <=heapSize)&&
         (minHeap[l].key < minHeap[min].key)){
             min = l;
         }
         if((r <=heapSize)&&
         (minHeap[r].key < minHeap[min].key)){
             min = r;
         }
         if(min !=i)
         {
             temp = minHeap[min];
             minHeap[min] = minHeap[i];
             minHeap[i] = temp;
             minHeapify(min);
         }
    }
    void buildMinHeap()
    {
         int i;
         for(i =heapSize / 2; i > 0; i--){
             minHeapify(i);
         }
    }
    nodeheapExtractMin()
    {
         node min;
         if(heapSize< 1)
         {
             cout << "ERROR:no more" << endl;
         }
         min = minHeap[1];
         minHeap[1] = minHeap[heapSize];
         heapSize--;
         minHeapify(1);
         return min;
    }
    void heapIncreaseKey(int i, int key)
    {
         node temp;
         if(key >minHeap[i].key)
         {
             cout << "ERROR:new key is smaller than current key" << endl;
         }
         minHeap[i].key = key;
         while(i> 1 && minHeap[i/2].key > minHeap[i].key)
         {
             temp = minHeap[i];
             minHeap[i] = minHeap[i/2];
             minHeap[i/2] = temp;
             i = i / 2;
         }
    }
    void minHeapInsert(node temp)
    {
         heapSize++;
         minHeap[heapSize] = temp;
         minHeap[heapSize].key = MAX;
         heapIncreaseKey(heapSize, temp.key);
    }
    inline int solved(node *temp)
    {
         int i, j;
         for(i = 0;i < 3; i++){
             for(j =0; j < 3; j++){
                  if((*temp).pos[i][j].y!= i || (*temp).pos[i][j].x != j)
                  {
                       return0;
                  }
             }
         }
         return 1;
    }
    int adj[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    char operation[4] = {'l', 'r', 'u', 'd'};
    int calKey(node *temp, int blankX2, int blankY2)
    {
         int key;
         int x1;
         int y1;
         int x2;
         int y2;
         int blankX1= (*temp).blankX;
         int blankY1= (*temp).blankY;
         key = 1;
         x1 = abs((*temp).pos[blankY1][blankX1].x -blankX1);
         y1 = abs((*temp).pos[blankY1][blankX1].y -blankY1);
         x2 = abs((*temp).pos[blankY2][blankX2].x -blankX2);
         y2 = abs((*temp).pos[blankY2][blankX2].y -blankY2);
         key += - (x1 + y1 + x2 + y2);
         x1 = abs((*temp).pos[blankY2][blankX2].x -blankX1);
         y1 = abs((*temp).pos[blankY2][blankX2].y -blankY1);
         x2 = abs((*temp).pos[blankY1][blankX1].x -blankX2);
         y2 = abs((*temp).pos[blankY1][blankX1].y -blankY2);
         key += x1 + y1 + x2 + y2;
         return key;
    }
    int factorial[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
    int calPos1(node *temp)
    {
         int i;
         int j;
         int x, y;
         int x1, y1;
         int temp1,temp2;
         int num;
         int sum;
         sum = 0;
         for(i = 0;i < 9; i++)
         {
             y = i / 3;
             x = i % 3;
             temp1 = (*temp).pos[y][x].x +(*temp).pos[y][x].y * 3;
             num = 0;
             for(j =0; j < i; j++)
             {
                  y1 = j / 3;
                  x1 = j % 3;
                  temp2 = (*temp).pos[y1][x1].x +(*temp).pos[y1][x1].y * 3;
                  if(temp2< temp1)
                  {
                       num++;
                  }
             }
             sum += (temp1 - num) * factorial[9 - i- 1];
            
         }
         return sum;
    }
    int calPos(node *temp)
    {
        inti,j,k=0,b[9],ret=0,num=0;
        for(i=0;i<3;i++)
            for(j=0;j<3;j++)
                b[k++]=(*temp).pos[i][j].x +(*temp).pos[i][j].y * 3;
        for(i=0;i<9;i++)
        {
            num=0;
            for(j=0;j<i;j++)
                if(b[j]>b[i])  num++;
            ret+=factorial[i]*num;
        }
        return ret;
    }
    int main()
    {
         int i;
         int j;
         int x;
         int y;
         int blankX;
         int blankY;
         char c;
         int length;
         node insertNode;
         node temp;
         int pos;
         bool find;
         insertNode.key = 0;   
         for(i = 0;i < 3; i++){
             for(j =0; j < 3; j++){
                  cin >> c;
                  if(c== 'x'){
                       insertNode.blankY = i;
                       insertNode.blankX = j;
                       insertNode.pos[i][j].x = 2;
                       insertNode.pos[i][j].y = 2;
                  }else{
                       x = c - '1';
                       y = x / 3;
                       x = x % 3;
                       insertNode.pos[i][j].x = x;
                       insertNode.pos[i][j].y = y;
                  }
                  insertNode.key +=abs(insertNode.pos[i][j].x - j);
                  insertNode.key +=abs(insertNode.pos[i][j].y - i);
             }
         }
         heapSize = 0;
         for(i = 0;i < maxLength; i++)
         {
             insertNode.op[i] = '\0';
         }
         memset(visited, 0, sizeof(visited));
         pos = calPos(&insertNode);
         visited[pos] = 1;
         minHeapInsert(insertNode);
         find = 0;
         int count =0;
         while(heapSize> 0){
             if(heapSize> maxNum)
             {
                  cout <<endl<< "Too large" << endl;
                  return-1;
             }
             temp = heapExtractMin();
             if(solved(&temp)== 1)
             {
                  find = 1;
                  cout << temp.op <<endl;
                  break;
             }
             for(i =0; i < 4; i++){
                  blankX = temp.blankX;
                  blankY = temp.blankY;
                  y = blankY + adj[i][0];
                  x = blankX + adj[i][1];
                  count++;
                  if(x< -1 || x > 3 || y < -1 || y > 3)
                  {
                       while(1)
                       {}
                  }
                  if(x< 0 || y < 0 || x > 2 || y > 2)
                  {
                       continue;
                  }
                  insertNode = temp;
                  insertNode.pos[y][x].x =temp.pos[blankY][blankX].x;
                  insertNode.pos[y][x].y =temp.pos[blankY][blankX].y;
                  insertNode.pos[blankY][blankX].x =temp.pos[y][x].x;
                  insertNode.pos[blankY][blankX].y =temp.pos[y][x].y;
                  pos = calPos(&insertNode);
                  if(visited[pos]!= 0){
                       continue;
                  }
                  visited[pos] = 1;
                  insertNode.key +=calKey(&temp, x, y);
                  insertNode.blankX = x;
                  insertNode.blankY = y;
                  length = strlen(temp.op);
                  insertNode.op[length] =operation[i];
                  minHeapInsert(insertNode);
             }
         }
         if(find ==0)
         {
             printf("unsolvable\n");
         }
         return 1;
    }

    14.2    IDA*搜索

    A*算法减少存储需求的最简单的方法就是将迭代深入的思想用在启发式搜索上,形成迭代深入A*算法,即IDA*。

    使用BFS搜索需要实用一个队列,这个队列如果过大就可能超出内存限制。用DFS代替BFS,可以减少存储需求。

    IDA*算法实际上是在迭代加深的深度优先搜索的基础上进行的一种改进。迭代加深的深度优先搜索使用当前搜索深度来判断是否停止搜索,而IDA*算法则使用A*算法的估价函数F(N) = G(N) + H(N)来判断是否停止搜索。可以知道,此时的G(N)就是当前搜索深度,H(N)则是对于从当前结点N至目标结点T的实际代价一种乐观估计。说H(N)乐观,是因为在设计估价函数的时候,H(N)被约束为小于等于实际代价。由此可知,相对于朴素的迭代加深的深度优先搜索,IDA*算法省去了一些不必要的搜索。

    14.2.1   实例

    PKU JudgeOnline, 2286, The Rotation Game.

    14.2.2   问题描述


    如上图一种游戏,给定初始状态,通过拉动A到H的,对该行或列进行旋转。目标是使得中间的八个数字相等。

    输出字典序最小的最优解的旋转过程,及其最终状态时中间的数字。

    14.2.3   输入

    11 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3

    11 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3

    0

    14.2.4   输出

    AC

    2

    DDHH

    2

    14.2.5   分析

    对搜索的深度给一个步数限制。每次在状态空间里进行DFS搜索的时候,如果遇见当前状态决定了已经不可能在限制内找到解,就返回,而不再搜索其子状态。如果这次DFS没找到,就继续放宽限制,重新对状态空间进行DFS。如此反复直到找到一个解。

    显然这个解是最优的解。

    确保解字典序最小的办法是DFS中顺次地从A到H中选择子状态。

    14.2.6   程序

    #include <iostream>
    using namespace std;
     
    int a[25];
    int res[1000];
    int ans;
    int limit;
     
    int state[8][7][2] = {
         { {1,23}, {3,1}, {7,3}, {12,7}, {16,12},{21,16}, {23,21} },
         { {2,24}, {4,2}, {9,4}, {13,9}, {18,13},{22,18}, {24,22} },
         { {11,5}, {10,11}, {9,10}, {8,9}, {7,8},{6,7}, {5,6} },
         { {20,14}, {19,20}, {18,19}, {17,18},{16,17}, {15,16}, {14,15} },
         { {24,2}, {22,24}, {18,22}, {13,18},{9,13}, {4,9}, {2,4} },
         { {23,1}, {21,23}, {16,21}, {12,16},{7,12}, {3,7}, {1,3} },
         { {14,20}, {15,14}, {16,15}, {17,16},{18,17}, {19,18}, {20,19} },
         { {5,11}, {6,5}, {7,6}, {8,7}, {9,8},{10,9}, {11,10} }
     
    };
     
     
    int isSuccess()
    {
         int ll =a[7];
         if(a[8]!=ll|| a[9]!=ll || a[12]!=ll || a[13]!=ll ||
             a[16]!=ll || a[17]!=ll || a[18]!=ll)
             return0;
         return ans= ll;
    }
     
    int getval()
    {
         int i;
         int cnt[4];
         memset(cnt,0,sizeof(cnt));
         for(i = 7;i <=9 ;i++)cnt[a[i]]++;
         for(i = 12;i <=13 ;i++)cnt[a[i]]++;
         for(i = 16;i <=18 ;i++)cnt[a[i]]++;
         return8-max(cnt[1],max(cnt[2],cnt[3]));
    }
     
    int dfs(int t)
    {
         inttemp[25];
         if(t==limit)
             returnisSuccess();
         if(t +getval() > limit)return 0;
         for(int i = 0 ; i < 8 ; i++)
         {
             res[t] = i;
             memcpy(temp,a,sizeof(a));
             for(int j = 0 ; j < 7 ; j++)
                  a[state[i][j][1]] =temp[state[i][j][0]];
             int ret= dfs(t+1);
             memcpy(a,temp,sizeof(temp));
             if(ret!=0)return ret;
         }
         return 0;
    }
     
     
    int main()
    {
         while(true)
         {
             scanf("%d",&a[1]);
             if(!a[1])
                  break;
             for(int i = 2; i <=24; i++)
                  scanf("%d",&a[i]);
             if(isSuccess())
             {
                  cout<<"No moves needed"<<endl<<a[7]<<endl;
                  continue;
             }
             limit = 1;
             while(dfs(0)== 0)limit++;
             for(int i = 0 ; i < limit ;i++)putchar((char)(res[i]+'A'));
             printf("\n%d\n",ans);
         }
         system("pause");
         return 0;
    }
    
    本文章欢迎转载,请保留原始博客链接http://blog.csdn.net/fsdev/article


    [i] 实用算法的分析与程序设计。吴文虎,王建德。

    [ii] The Art of Computer Programming, Volume 3, Sorting and Searching.Donald E. Knuth.

    展开全文
  • 我们的研究SLSDT是一种使用称为后验收爬山(LAHC)的随机局部搜索方法来感应倾斜决策树的方法,以尝试在每个内部节点中找到特征的最佳组合。 该项目还提供了一个实用程序,可读取csv文件并将其转换为SLSDT方法接受...
  • 本文提供了一种新颖的启发式加权方法,以选择最可能的路径来构建基于角色的信任链。 我们应用对历史敏感的启发式方法来测量路径复杂度并评估链接效率。 我们使用加权目标,链接角色和交点边缘来自适应地发现信任链...
  • 但是,本文主要介绍了一种自行开发的启发式方法,并结合研究和我们自己的经验证明了与网上可用的Connect-4系统版本相抗衡的结果。 尽管大多数以前的工作都集中在赢得算法和基于知识的方法上,但我们通过启发式分析...
  • 搜索算法-搜索的优化

    2016-10-22 16:05:13
    一些搜索的优化方法: 1.爬山法 2.Best-First法 3.分支界限法 ...3.爬山搜索使用启发式测度来排序节点拓展的顺序,也就是说要有测度函数,在8-puzzle问题中测度函数结点中处于错误位置的方块数。
  • 结果:为了使p-ECR的移动效率更高,本文提出了一种名为p-ECRNJ的新方法。 p-ECRNJ的主要思想是使用邻居连接(NJ)来优化p-ECR中产生的未解析节点。 结论:真实数据集的实验表明,到目前为止,p-ECRNJ可以找到比最佳...
  • 这项研究的目的将和声搜索算法作为一种成功的用于无线传感器网络路由的元启发式算法,以延长此类网络的寿命。 这项研究旨在改善和谐搜索算法中能效的目标函数,以在网络能耗和路径长度控制之间建立平衡。 因此,...
  • 第六章 约束满足问题 6.0绪论 从搜索算法的角度看,每个状态都原子的,或者...CSP搜索算法使用通用策略,而不是问题专用启发式来求解复杂问题。 主要思想通过识别违反约束的变量/值的组合迅速消除大规...
  • 盲目搜索方法又叫非启发式搜索是一种无信息搜索,一般只适用于求解比较简单的问题,盲目搜索通常是按预定的搜索策略进行搜索,而不会考虑到问题本身的特性。常用的盲目搜索有宽度优先搜索和深度优先搜索两种。盲目...
  • 具体方法有很多,比如今天要讲的两最简单、最“暴力”的深度优先、广度优先搜索,还有 A*、IDA* 等启发式搜索算法。 图有两主要存储方法,邻接表和邻接矩阵。本文使用邻接表来存储图。我这里先给出图的代码实现...
  • 人工智能概论-搜索算法编程及实验报告 人工智能概论大作业 学院电子工程学院 专业智能科学与技术 题目一搜索算法编程及实验报告 算法题目 八数码难题的求解 实验目的 从盲目搜索和启发式搜索方法中分别选择一种解决...
  • 搜索是一种在自然语言处理中常用的搜索方式,它全称是集束搜索,也就是Beam-Search,通常认为该方法也是一种启发式的搜索方式。    在介绍束搜索之前,我们先来了解两种比较极端的搜索方式,第一种...
  • 涡流搜索算法(Vortex Search,VS)最近提出的一种新型元启发式单解优化算法,涡流算法灵感源自搅动液体产生的涡流现象,该方法通过使用一种自适应步长调整方案的的搜索行为模拟涡流现象,具有操作简单和搜索能力...
  • 自适应大邻域搜索算法

    千次阅读 2020-06-16 20:50:10
    自适应大邻域搜索算法(Adaptive Large Neighborhood Search)由Ropke与Pisinger在2006年提出的一种启发式方法,其在邻域搜索的基础上增加了的对算子的作用效果的衡量,使算法能够自动选择好的算子对解进行破坏与...
  • 禁忌搜索(Tabu Search)算法及python实现

    万次阅读 多人点赞 2018-08-16 13:46:51
    禁忌搜索(Tabu Search,TS,又称禁忌搜寻法)是一种现代启发式算法,由美国科罗拉多大学教授Fred Glover在1986年左右提出的,是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案;基于此,算法“移动”到...
  • 本文提出了一种三值重力搜索算法(TGSA),以解决图形的平面化问题。 问题(GPP)。 GPP是图论中最重要的任务之一,被证明是一个NP难题。 为了解决这个问题,TGSA使用三值编码方案,并根据众所周知的单行路由表示...
  • 文章目录一、实验内容二、实验任务三、算法A*算法四、解题思路总结 ...1)对九宫重排问题,建立图的启发式搜索求解方法; 2)用A*算法求解九宫重排问题。 三、算法 A*算法 A*算法是一种用于求解最短路径的算法,给出
  • 结合启发式搜索的精确性和蒙特卡洛方法随机抽样的一般性,提出一种基于$Q_MC$的蒙特卡洛聚类/扩展算法(CEMC),CEMC整合了Q值函数求解和策略搜索过程,避免保存所有值函数,只按需求解.实验结果表明,CEMC在时间和内存占用...
  • MQEPSP系统方法,量子启发式进化算法和局部搜索的适当组合,它通过使用类细胞P系统的分层框架进行设计的,该对象由量子启发性比特和经典比特组成,规则由系统中量子激发的门进化规则和进化规则的建立,以及在...
  • 其中使用一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此,A*搜索算法最佳优先搜索的范例。​02集束搜索又名定向搜索,Beam Search最佳...
  • 无线电链路频率分配问题是一种约束满足问题(CSP),包括将频率分配给在站点对之间定义的一组无线电链路,以避免干扰。 有关此问题的详细说明,请参见。 使用搜索方法: 通过向前检查(FC)回溯 保持电弧一致性...
  • 方法的主要优势在于能够使用从结构化数据或半结构化数据中得到的知识以及一些通用的启发式规则,自动标注语料。对于网页中文本内容的抽取,提出了一种基于启发式规则的网页正文内容抽取算法,自动识别网页中的正文...
  • 启发式方法是基于像奖励一样使用的权重 七排 所采用的策略基于表环境中块的影响。 要连续创建4个,表格中的新作品只能在自己位置的3个角附近搜索。 当您在每个方向和新作品的位置上加入3个空格时,将形成个七...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 124
精华内容 49
关键字:

启发式搜索是一种使用搜索方法