精华内容
下载资源
问答
  • 博弈树搜索算法

    万次阅读 多人点赞 2017-05-09 20:17:47
    0 引言 在智能过程中,...在游戏(人机博弈)程序中博弈树搜索算法是其核心的部分,它与估值及规则(走法)构成一个完整的系统。1 α-β剪枝算法1.1 基本思想 根据倒推值的计算方法,或中取大,与中取小,在扩展和

    即使满腹经纶,但没有好的口才来授课,也会让学生听得昏昏欲睡、不知所云呢!即使满腔热血,没有好的口才来凝聚共识,也会让这份理想温暖黯淡无光。但是,好的说话之道,也要有一颗赤诚的心、诚恳的情来润饰,否则,很难做到说好话、做好事、做好人的成果!——《爱读书的孩子,不会变坏 (宋怡慧 著)》

    0 引言

      在智能过程中,搜索是必不可少的,是人工智能中的一个基本问题—— Nilsson。这是因为人工智能研究的主要是那些没有成熟方法可依的问题领域,需要一步步搜索求解。游戏中如何找到对自己有利的局面就属于这类问题。在游戏(人机博弈)程序中博弈树搜索算法是其核心的部分,它与估值及规则(走法)构成一个完整的系统。

    1 α-β剪枝算法

    1.1 基本思想

      根据倒推值的计算方法,或中取大,与中取小,在扩展和计算过程中,能剪掉不必要的分枝,提高效率。

    1.2 定义

      α值:有或后继的节点,取当前子节点中的最大倒推值为其下界,称为α值。节点倒推值>=α;
      β值:有与后继的节点,取当前子节点中的最小倒推值为其上界,称为β值。节点倒推值<=β;

    1.3 α-β 剪枝

      (1)β剪枝:节点x的α值不能降低其父节点的β值,x以下的分支可停止搜索,且x的倒推值为α;
      (2)α 剪枝:节点x的β值不能升高其父节点的α值,x以下的分支可停止搜索,且x的倒推值为β;

    1.4 例题图

    这里写图片描述
      先做个说明:有画弧线的是与,取较小值,没有的是或,去最大值。
      第一步:2、9、3做比较,取最小值2,I点确定为2。
      第二步:J点的1和I点2大小进行比较,如果1是J点的最小值,由于J的父节点是取较大值,1<2,无法升高D的值,所以J点的-1可以点可停止搜索,我们划掉该值。
      第三步:I点2接着与K点的左值-1进行比较,如果-1是最小值,由于K的父节点取较大值,-1<2,无法升高D的取值,所以K点的右值可以停止搜索。
      第四步:D的值可以确定为2。
      第五步:L点的作用值进行比较,取较小值6,D值与L值相比较,由于E去较大值,假设L就是最大值,E=6,二B点取得是D和E的较小。值,2<6,E的结果值无法降低B的取值,所以E的右枝可以截掉。
      第六步:B的值可以确定为2。
      第七步:N的左右值进行比较,取0,N点在和O点的左值-5进行比较,假设-5是最小值,0>-5,O点的取值无法升高父节点F的值,所以可以停止搜索O点的右枝。
      第八步:F确定为0。
      第九步:F点假设是C的最小值,它和B点的值比较,2>0,也就是说C点的取值无法升高A点的取值,所以G和H都停止搜索。

    第十步:A点取2.

    2 改进α - β剪枝算法

    2.1 窗口原则(Window Principle)

      在α - β剪枝过程中,初始的的搜索窗口往往是从- ∞(即初始的α值)到+ ∞(初始的β值),在搜索进行中再不断缩小窗口,加大剪枝效果,这种估计是可靠的,但却不是高效的。如果我们一开始就使用一个较小的窗口,那么我们就有可能提高剪枝效率,这就是窗口原则。
      使用窗口原则的算法有: Falphabeta 算法,即Failsoft-alphabeta算法; 渴望搜索(Aspiration Search); 极小窗口搜索(Minimal Window Search/PVS)

    2.2 置换表(Transpotion Table)

      置换表基本思想: 在搜索进行中,用一张表把搜索过的节点结果(包括搜索深度,估值类型: 准确还是上下边界)记录下来,在后继的搜索过程中,查看表中记录。如果搜索的节点已经有记录(子树的深度大于或者等于当前的新节点要求的搜索深度),它的信息就可以直接运用了,这样我们可以避免重复搜索很多子树。置换表是一种内存增强技术,以空间换时间。

    2.3 历史启发(History Heuristic)

      历史启发是为了迎合α-β剪枝搜索对节点排列顺序敏感的特点来提高剪枝效率的,即根据历史走法对当前搜索的节点集进行排序,从而优先搜索好的走法。

    2.4 迭代深化(Iterative Deepening)

      迭代深化是一个不断求精的过程,对博弈树进行多次遍历,并不断加深其深度,用于控制搜索的时间。
      在实用中迭代深化和前面提到的算法结合使用具有很好的效果,如PVS算法,上几层迭代得到的最佳走法可以帮助下一层提高剪枝效率; 迭代过程中把前面局面的历史得分存入置换表最佳走法存入历史启发表可以提高剪枝效率。

    2.5 实验数据分析

      各种增强策略都能提高α - β剪枝的效率,其中空窗口探测(PVS)从第五层开始平均需估计的节点数减少为一半,而效率提高一倍。单纯的迭代深化由于在迭代需要耗费时间,从效率上看提高不大。置换表在前三层没什么表现,这是因为置换表操作也要耗费时间,且当其命中率低时效果不佳,但层数较多命中率高时优势越来越明显。历史启发是这几种增强策略中最好的,在第五层效率就能提高十倍以上,越往后效果更好,这也证实了α-β剪枝对顺序的极度敏感。
      MTD(f)算法在实验中的前几层稍优于PVS 算法,但它层数大于六时很不稳定且本身带置换表,因此在把各种增强策略融合时不如PVS 算法。融合各种增强策略的PVS 算法在第六层就比基本的α - β剪枝快两百多倍。

    3 B* 算法

    3.1 B* 算法的思想与要点

      B* 算法是由Hans J. Berliner在1979年提出来的一个算法,毫无疑问B*算法是到目前为止最具有人类风格的棋手[6]。
      Berliner在研究极小极大搜索树的时候,认为有两个问题是关键的。
      第一个问题是:如何降低组合搜索的复杂性,即如何尽早地查出不合用的坏分支,并把它剪除。这一步涉及到了进一步改进Alpha-Beta剪枝。
      第二个问题是:如何合理地确定搜索的深度限制,已解决他本人提出的所谓水平效应(见下小节)。为了做到这一点,应该对每个分枝的前景有一定的定量的展望,以便及早放弃前途不大的搜索方向。

    3.1.1 水平效应

      由于固定搜索深度而引起的问题称为“水平效应”。
      负水平效应:
      如果一个搜索程序前进到了某个深度的时候,自以为找到了一个比较有利的结局,但是它不知道,若再深入几步就可以看出,真正的结局原来是不利的。这种看不出危险的毛病称为负水平效应。
      正水平效应:
      如果一个搜索程序在极限深度处发现了一种不利的局面,于是决定放弃这个方向。但是它不知道,只要再搜索几步即可出现“柳暗花明又一村”的好形式,由于“眼光”太短浅而没有做“再坚持一下”的努力。这种情况称为正水平效应。

    算法的思想与要点

      每个节点用一个乐观估值和一个悲观估值来表示评价值。
      两个估计值都动态可变,且估值出自同一方的立场,只是估计的棋局按层次交错更替。对对方棋局的乐观估计即是对本方棋局的悲观估计; 对对方棋局的悲观估计即是对本方棋局的乐观估计。因此,从下层节点向上层节点反馈信息时,悲观估计和乐观估计是交叉传递的。
      B*树在展开过程中,只要子节点的估值有利于父节点估值的精化,即改动父节点的估计值,即使乐观估值和一个悲观估值相互靠近(当当前节点深度大于零时需回溯),如果这种改动波及到父节点的估值,则根节点需考虑使用何种策略。
      B*算法设立两种策略,证明最优( P R O V E B E S T ) 和排除其余(DISPROVEREST)。
      算法从这点出发,用这两个界来证明哪个节点是最好的。当根节点的一个孩子的悲观值不比所有其它节点的乐观值差的时候,B* 算法就结束了。
      算法的搜索控制就是尽可能快的得到终止条件。B* 算法的优点是找到一步好棋速度快,不限定搜索深度,不会“产生水平效应”(这是固定深度α-β剪枝算法的一个缺点),缺点是它对局面的乐观值和悲观值的估计依赖性太强,实现困难

    3.2 B* 算法伪代码

    typedef struct statue
    {
        qiju con; // qiju 为当前棋局内容(数组)
        int opt; // 棋局乐观估计值
        int pes; // 棋局悲观估计值
        unsigned par; // 父节点所在的地址
        unsigned eld;// 长子节点所在的地址
        unsigned young;幼子节点所在的地址
    } STATUE;
    sta = { cur-qiju, -ININITY, ININITY, 0, 0, 0 };
    qiju BXin(STATUE sta)
    {
        vector< STATUE > v;
        unsigned al = 1; // 第一可分配的位置
        unsigned depth = 0; // 当前搜索深度(层次)
        unsigned cur = 0; // 当前节点的地址
        STATUE st;
        v.push_back(sta);
        while(1)
        {
            if(v[cur].eld == 0) // 当前节点未扩展过
            {
                int count = CreatePossibleMove();
                for(each possibly move m)
                {
                    make move m // 产生 m 的子节点
                        // 创建子节点的状态
                        construct child’s STATUE st;
                    v.push_back(st);
                }
                v[cur].eld = al; // 修改长子节点所在地址
                // 修改幼子节点所在的地址
                v[cur].young = al + Count - 1;
                al += count; // 修改第一可分配的位置
            }
            // 建立最佳节点和次佳节点
    lab:
            best = next = pest = v[cur].eld;
            if(depth%2 == 0) //偶数层
                for(i = v[cur].eld; i <=v[cur].young; i++)
                {
                    if(v[best].opt < v[i].opt)
                        best = i; // 修改极大乐观值节点位置
                    if(v[next].opt < v[i]. opt t &&
                            v[i].opt < v[best]. opt)
                        next = i; // 修改次极大乐观值节点位置
                    if(v[pest].pes < v[i]. pes)
    
                        pest = i; // 修改极大悲观值节点位置
                }
            else// 为奇数层
                for(i = v[cur].eld; i <=v[cur].young; i++)
                {
                    if(v[best].pp.first > v[i].pp.first)
                        best = i; // 修改极小乐观值节点位置
                    if(v[next].opt>v[i].opt&&v[i].opt> v[best]. opt)
                        next = i; // 修改次极小乐观值节点位置
                    if(v[pest]. pes > v[i]. pes)
                        pest = i; // 修改极小悲观值节点位置
                }
            int opt = v[best].opt;
            int pes = v[pest].pes;
            // 满足条件,则修改当前节点的估计值,并在深度大于零时进行回溯
            if( ((depth%2 == 0) && (opt < v[cur].pes || pes > v[cur].opt))
                    || ( (depth%2 == 1) && (opt >v[cur].pes || pes < v[cur].opt)) )
            {
                v[cur].pes = opt;
                v[cur].opt = pes;
                if(depth > 0)
                {
                    cur = v[cur].par;
                    depth--;
                    goto lab; //回溯
                }
                else
                    // 有一枝的悲观值不小于其它枝的乐观值,则搜索结束。
                    if(v[best].pes >= v[next].opt)
                        return v[best].con;
            }
            if(depth == 0)// 决定下一步的策略
            {
                if(take provebest strategy) cur = best;
                else cur = next;
            }
            if(depth > 0) cur = best;
            depth++;
        }
    }

    3.3 实验说明

      实验中用的策略为Berliner 原则:用一组候选分枝与最佳分枝做比较,如果各候选分枝实行信息反馈的深度是ti,最佳分枝实行信息反馈的深度是t,比较Σti2和t2,若前者小于后者,则采用DISPROVEREST策略,否则采用PROVEBEST策略,即优先搜索那些至今搜索深度比较浅的分枝。由于B* 算法对估值的依赖性很强,实验所用的估值效果实现算法速度很快(时间小于一秒),但走法只有搜索深度为三层α - β剪枝的水准,实用时有待进一步提高。

    4 SSS*算法

    5 结束语

      以上讨论了博弈树搜索算法的两类算法,其中α - β剪枝算法比较成熟,是当前最常用的算法,在融合各种策略后具有很高的剪枝效率。如果能进一步改进数据结构和进行代码优化以及使用开局、残局库可以使程序具有很高的效率智能。B* 算法由于其复杂性,一般使用较少,国内研究的热情不高,有待进一步研究,包括如何对棋局进行估值,使用何种策略以及与在中国象棋、围棋等游戏中实现。

    6 参考文献

    [1]陆汝钤.《人工智能》[M].北京:科学出版社,1995.
    [2]王小春.游戏编程(人机博弈)[M].重庆:重庆大学出版社,2002.
    [3][美]Nils J Nilsson.人工智能[M].北京: 机械工业出版社,2000
    [4]Knuth, D.E. and Moore, R.W. (1975). An Analysisof Alpha-Beta Pruning[J]. Artificial Intelligence,Vol. 6, No. 4:293-326.
    [5]Berliner, H.J. (1979). The B*-tree search: Abest-first proof procedure[J]. Artificial Intelligence,Vol. 12, No. 1:23-40.

    展开全文
  • 蒙特卡洛树搜索算法(MCTS)

    千次阅读 2020-01-25 12:16:30
    Monte Carlo Tree Search, 是一类树搜索算法的统称。 蒙特卡洛树搜索是一种基于树数据结构**、能在搜索空间巨大仍然比较有效的搜索算法 MCTS是一种逼近纳什均衡的搜索策略。 应用场景 搜索空间巨大 zero-sum...

    蒙特卡洛树搜索(MCTS)

    参考网址:https://zhuanlan.zhihu.com/p/30458774

    定义

    Monte Carlo Tree Search, 是一类树搜索算法的统称。

    • 蒙特卡洛树搜索是一种基于树数据结构、能在搜索空间巨大仍然比较有效启发式搜索算法
    • MCTS是一种逼近纳什均衡的搜索策略。
    应用场景
    • 搜索空间巨大

    • zero-sum、fully information、determinism、sequential、discrete

    • 第二点即:场景能分出输赢、游戏信息完全公开、每一个操作结果没有随机因素、操作按顺序执行、没有操作是一种连续值

    • 只能解决Combinatorial Game的问题

    四大阶段

    SelectionExpansionSimulation_和_Backpropagation(选择、扩展、模拟、回溯

    理论基础

    一、Game Theory(博弈论)

    1. 纳什均衡点

    定义

    minmax算法最终达到的平衡点

    2. minmax算法

    img

    图1 minmax算法示意图

    应用

    在搜索树中,每次轮到黑棋走时,走对黑棋最有利的;轮到白棋走时,走对黑棋最不利的。

    二、Black Box Optimization(黑盒优化)

    无法得知场景内部的函数或模型结果,只能通过输入和输出对算法进行优化。

    示例

    进化算法、贝叶斯优化、MCTS

    三、UCB算法基础

    与蒙特卡洛搜索算法关系说明

    • UCB: 指UCB公式 (Upper Confidence Bound),公式为:

    Vi+ClnNni V_i + C \sqrt{\frac{lnN}{n_i}}

    • UCT 算法:UCB for Tree的算法,最经典的蒙特卡罗树搜索算法

      UCT = MCTS + UCB

    • UCB1: 一种简单而广泛使用的UCB公式

    Vi+2lnNni V_i + \sqrt{\frac{2 lnN}{n_i}}

    四、MCTS过程

    img

    图2 MSTC 1次迭代的 4个步骤

    UCT (UCB for Tree)算法

    蒙特卡罗树搜索大概可以被分成四步。选择(Selection),拓展(Expansion),模拟(Simulation),反向传播(Backpropagation)。

    在开始阶段,搜索树只有一个节点,也就是我们需要决策的局面。

    搜索树中的每一个节点包含了三个基本信息代表的局面,被访问的次数,累计评分。

    [1]选择(Selection)

    在选择阶段,需要从根节点,也就是要做决策的局面R出发向下选择出一个最急迫需要被拓展的节点N,局面R是是每一次迭代中第一个被检查的节点;

    ​ 对于被检查的局面而言,他可能有三种可能:

    ​ 1)该节点所有可行动作都已经被拓展过

    ​ 2)该节点有可行动作还未被拓展过

    ​ 3)这个节点游戏已经结束了(例如已经连成五子的五子棋局面)

    ​ 对于这三种可能:

    ​ 1)如果所有可行动作都已经被拓展过了,那么我们将使用UCB公式计算该节点所有子节点的UCB值,并找到值最大的一个子节点继续检查。反复向下迭代。

    ​ 2)如果被检查的局面依然存在没有被拓展的子节点(例如说某节点有20个可行动作,但是在搜索树中才创建了19个子节点),那么我们认为这个节点就是本次迭代的的目标节点N,并找出N还未被拓展的动作A。执行步骤[2]

    ​ 3)如果被检查到的节点是一个游戏已经结束的节点。那么从该节点直接执行步骤{4]。

    每一个被检查的节点的被访问次数在这个阶段都会自增。

    在反复的迭代之后,我们将在搜索树的底端找到一个节点,来继续后面的步骤。

    [2]拓展(Expansion)

    在选择阶段结束时候,我们查找到了一个最迫切被拓展的节点N,以及他一个尚未拓展的动作A。在搜索树中创建一个新的节点Nn作为N的一个新子节点。Nn的局面就是节点N在执行了动作A之后的局面。

    [3]模拟(Simulation)

    为了让Nn得到一个初始的评分。我们从Nn开始,让游戏随机进行,直到得到一个游戏结局,这个结局将作为Nn的初始评分。一般使用胜利/失败来作为评分,只有1或者0。

    [4]反向传播(Backpropagation)

    在Nn的模拟结束之后,它的父节点N以及从根节点到N的路径上的所有节点都会根据本次模拟的结果来添加自己的累计评分。如果在[1]的选择中直接发现了一个游戏结局的话,根据该结局来更新评分。

    每一次迭代都会拓展搜索树,随着迭代次数的增加,搜索树的规模也不断增加。当到了一定的迭代次数或者时间之后结束,选择根节点下最好的子节点作为本次决策的结果。

    上面描述的是UCT (UCB for Tree)算法,可以说是最经典的蒙特卡罗树搜索算法了。但随着算法的发展,MCTS已经有了非常大的改变。例如很多围棋AI都已经不再使用纯粹的UCB公式而改用效果更好的UCB1-Tuned了[2],而搜索方法上也有了非常多的改动了。

    MCTS 和 UCT

    Kocsis 和 Szepervari 在 2006 年首先构建了一个完备的 MCTS 算法,通过扩展 UCBminimax 树搜索,并将其命名为 Upper Confidence Bounds for Trees(UCT)方法。这其实是用在当前众多 MCTS 实现中的算法版本。

    UCT 可以被描述为 MCTS 的一个特例:UCT = MCTS + UCB。

    展开全文
  • K近邻 kd 搜索算法 python实现

    千次阅读 2019-02-27 16:08:18
    文章目录K近邻 k维kd树搜索算法 python实现python数据结构之二叉树kd树算法介绍构造平衡kd树用kd树的最近邻搜索kd树算法python实现参考文献 K近邻 k维kd树搜索算法 python实现 在KNN算法中,当样本数据量非常大时...

    K近邻 k维kd树搜索算法 python实现

    在KNN算法中,当样本数据量非常大时,快速地搜索k个近邻点就成为一个难题。kd树搜索算法就是为了解决这个问题。本篇博客主要介绍多维数据kd树搜索算法的Python实现。

    python数据结构之二叉树

    本篇博客不对二叉树进行详细介绍,只提及一些比较重要的概念。

    • 二叉树抽象数据类型的定义:
    ADT BinTree:
    	BinTree(self, data, left, right)	#构造函数,创建一个新的二叉树
    	is_empty(self)							#判断self是否为一个空二叉树
    	num_nodes(self)						#求二叉树的结点个数
    	data(self)									#获取根结点存储的数据
    	left(self)									#获得二叉树的左子树
    	right(self)									#获得二叉树的右子树
    	set_left(self, btree)					#用btree取代原来的左子树
    	set_right(self,btree)					#用btree取代原来的右子树
    	traversal(self)							#遍历二叉树中各节点数据的迭代器
    	forall(self, op)							#对二叉树中的每个结点的数据执行操作
    
    • 遍历二叉树的两种方法:
      • 深度优先遍历:先根序遍历,中根序遍历,后根序遍历。
      • 广度优先遍历。

    kd树算法介绍

    kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树,表示对k维空间的一个划分。构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

    构造平衡kd树

    输入:k维空间数据集 T={x1,x2,...,xN}T=\{ x_{1},x_{2},...,x_{N}\},N表示样本个数。
    其中xi=(xi1,xi2,...,xik)T,i=1,2,...,Nx_{i} = (x_{i}^{1},x_{i}^{2},...,x_{i}^{k})^{T},i=1,2,...,N
    输出:kd树

    1. 开始:构造根结点,根节点对应于包含T的k维空间的超矩形区域。选择第一维为坐标轴,以T中所有样本数据的第一维坐标的中位数为切分点,将根结点对应的超矩形区域切分成为两个子区域。切分由通过切分点并与第一维坐标轴垂直的超平面实现。由根结点生成深度为1的左、右子结点:左子结点对应第一维坐标小于切分点的子区域,右子结点对应第一位坐标大于切分点的子区域。将落在切分超平面上的实例点保存在根结点。
    2. 重复:对深度为j的结点,选择第i维为切分的坐标轴,i=(jmodk)+1i=(j mod k)+1。以该结点的区域中所有实例的第i维坐标的中位数为切分点,将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与第i维坐标轴垂直的超平面实现。由该结点生成深度为i+1的左右子结点。
    3. 直到两个子区域没有实例存在时停止,从而形成kd树的区域划分。

    用kd树的最近邻搜索

    输入:已构造的kd树;目标点x;
    输出:x的最邻近

    1. 在kd树中找出包含目标点的x的叶结点:从根结点出发,递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标,则移动到左子结点,否则移动到右子结点。直到子结点为叶结点为止。
    2. 以此叶结点为“当前最近点”。
    3. 递归地向上回退,在每个结点进行以下操作:(a)如果该结点保存的实例点比当前最近点距离目标点更近,则以该实例点为“当前最近点”。(b)当前最近点一定存在于该节点的一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地,检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点的距离为半径的超球体相交。如果相交,可能在另一个子结点对应的区域内存在距离目标点更近的点,移动到另一个子结点。接着,递归地进行最近邻搜索;如果不相交,向上回退。
    4. 当回退到根结点是,搜索结束,最后的“当前最近点”即为x的最近邻点。

    如果实例点是随机分布的,kd树更适用于训练样本数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时。它的效率会迅速下降,几乎接近线性扫描。

    kd树算法伪代码

    建立kd树

    初始维度设为dim = 0
    def creat(points,dim):
    	if points is not None:
        	1.找到所有样本点(points)在第dim维度下的坐标的中位点,记为point[media]
            2.确定过该中位点且垂直于第dim维坐标轴的一个超平面。(只是一个概念无需体现在代码中)
            3.该超平面将空间分为两个子空间。该中位点则作为当前kdtree的根结点						root.data=point[media]
            4.在第dim维度下,小于该中位点的所有样本点被划分到左子树,记为lefts点集
            5.大于该中位点的所有样本点被划分到右子树,记为rights点集.
        	递归执行:root.left = creat(lefts,(dim+1)% m)
        	递归执行:root.right = creat(rights,(dim+1)% m)
        	return root
        else:
        	return None
    

    搜索最近邻点

    def research_nn(point):
    	1.遍历:将point点的坐标对应维度与kdtree的结点进行比较,小于结点对应维度的值往左子树走,反之往右子树走,等于的话就停止,或者知道kdtree的叶子结点再停止。将经过的所有节点坐标依次压入栈stack。以最后停下来的点(stack.pop)作为最近零点,并计算距离dist_min
    	2.回溯:
    	def back(point, dist):
    		leaf = stack.pop
    		计算leaf与point的距离,记为dist
    		if dist <= dist_min:
    			dist_min=dist
    			return
    		else:
    			计算point到leaf的父结点所在的超平面的距离,记为dist
    			if dist_min<dist:   #说明没有交点
    				return
    			else:
    				stack。append(leaf的兄弟结点)
    				back(point, dist)
    

    kd树算法python实现

    使用开源的KDTree库函数,详情见https://mp.csdn.net/mdeditor/87977160#

    参考文献

    1.李航,统计学习方法,清华大学出版社。
    2.裘宗燕,数据结构与算法python语言描述,机械工业出版社。

    展开全文
  • 许多完全信息的二人零和博弈问题都可以用博弈树搜索算法解决。 那么什么是二人零和博弈问题呢? 有一系列的博弈问题拥有以下性质[1]: 1. 有两个对抗者:对抗者1和对抗者2. 2. 两个对抗者交替移动.在博弈的每一...

    博弈树的搜索是人工智能领域一个重要的研究课题.许多完全信息的二人零和博弈问题都可以用博弈树搜索算法解决。

    那么什么是二人零和博弈问题呢?

    有一系列的博弈问题拥有以下性质[1]:

    1. 有两个对抗者:对抗者1和对抗者2.

    2. 两个对抗者交替移动.在博弈的每一个位置,对于正在移动的参与者,都存在有限个可能的移动.

    3. 游戏是决定性的,即游戏中不存在随机性.

    4. 游戏是完全信息的,即在任意时刻,博弈双方知道所处状态的所有信息.例如国际象棋是完全信息的,因为博弈双方知道所有的棋子所处位置,而两人玩的扑克牌游戏则是非完全信息的,因为一个人看不到对方手上的扑克牌.

    5. 游戏有三种可能结局:对抗者1获胜,对抗者2获胜,或者平局.有一些游戏不存在平局,只有两种可能解决:对抗者1获胜,或者对抗者2获胜.由于这个性质,所以一个对抗者的损失对另一个对抗者来说是受益,故此这类的博弈游戏称为零和博弈(zero-sum game).

    对于具有上述性质的博弈问题,可以用博弈树来表示两个对抗者在博弈过程可能遇到的状态和移动选择.在对抗树(adversarytree)或者博弈树(gametree)中,两个对抗者交替移动.处于树底层的结点称为叶结点(leaf node),叶结点的祖先称为内部结点(interior node).

    使用的[2]术语,一个问题空间(problem space)看以看做是一个状态(state)和实现状态之间映射的操作(state)的集合.在博弈问题中,博弈树上的一个内部结点或叶结点就是一个状态,一般使用位置(position)来表述.移动(move)就是将一个位置转化为其子位置(successor position)的操作.如果一个位置是博弈树的叶结点,可以用评价者(evaluator)来对其优劣进行评分(evaluate).有了评价者,博弈树中的每个叶结点都有一对应值(value).

    博弈树搜索或者对抗搜索的目的就是找出博弈树的值(game tree value).博弈树的值(gametree value,下面简称博弈值)指的是博弈树中一个子结点的值,该值对于博弈双方都是最优的.博弈树的子树(subtree)在该子树搜索完成之后也会返回一个博弈值,虽然该值对于该子树来说最优的,但是对整个博弈树来说并不是全局最优的.

    找出一棵博弈树的博弈值,可以使用基本的Min-Max方法.为了减少Min-Max方法需要搜索的结点个数,可以使用Alpha-Beta算法进行剪枝.根据博弈树的性质,在Alpha-Beta算法的基础上,各种改进方法被先后提出来.为了进一步提高搜索速度,Alpha-Beta算法又可以基于不同的思想进行并行化.在博弈树搜索算法方面,前人做了许多丰富而充满意义的研究工作.

    本文重点在于讨论博弈树并行搜索算法的设计和分析.但是一方面由于博弈树搜索的并行算法与串行算法的紧密内在联系,一方面为了对博弈树的搜索问题进行全面和深入的认识,本文不仅将讨论并行的博弈树搜索算法,而且将总结关于博弈树的串行搜索算法的许多其他问题.从最基本的Min-Max方法开始,到Alpha-Beta串行算法,再到Alpha-Beta算法的并行化,本文沿着博弈树搜索问题的脉络,将进行细致的分析和总结.

    本文章欢迎转载,请保留原始博客链接http://blog.csdn.net/fsdev/article

    -------------------------------------------------

     [1]    Valavan Manohararajah(2001). Parallel Alpha-Beta Search on SharedMemory Multiprocessors. Master’s thesis, Graduate Department of Electrical andComputer Engineering, University of Toronto, Canada.

     [2]    A. Newell and H.A. Simon (1972). Human Problem Solving.Prentice-Hall, 1972.


    展开全文
  • 除了基于Alpha-Beta算法的博弈树并行搜索算法外,还有其他的博弈树搜索算法.现简要介绍如下. 7.1 SSS*算法及其并行化 Alpha-Beta算法是一种基于Min-Max方法的固定深度(fixed-depth)搜索算法.说它是固定深度的...
  • 状态树搜索算法,妖怪与和尚过河问题的求解...
  • 树搜索算法 及 最优解

    千次阅读 2020-03-24 16:03:34
    深度优先搜索算法不全部保留结点,扩展完的结点从数据存储结构栈中弹出删去,在栈中存储的结点数就是解空间的深度,因此它占用空间较少。所以,当搜索的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失...
  • 近邻法中计算距离需要遍历,带来很大的计算量和存储量,为了改善这两方面的性能,有人提出采用分枝界定...2)利用树搜索算法找出与未知样本的k个近邻。 1.层级划分 1)将样本集X划分成l个子集,每个子集再分成l个子集,
  • 查找搜索算法可以说是被提及最多的人工智能方法,绝大多数AI问题都可以被看成一个搜索查找问题,也就是找到最好的方案,路径,模型等。
  • 下面开始介绍一些在Alpha-Beta算法中引入并行化的方法和算法. 6.1 并行求值(Parallel Evaluation) 游戏的博弈程序经常要在搜索...一个在博弈树搜索中应用并行性的思想[6]就是将求职函数设计得较为复杂,并将它划
  • 假设博弈的深度为d,每个结点有b个分支,即分支因子(branchingfactor)为b,那么使用Min-Max方法搜索这个博弈需要搜索个结点. 然而幸运的是,Min-Max方法的一些搜索是没有必要的,故此可以剪除(cut-off)那些没有...
  • 搜索博弈时,内部结点有多个可能的移动.择序指的是搜索这些分支的顺序.择序影响着搜索叶结点的个数,使得其数目在[,]区间内变化.如果择序使得博弈是随机的,那么所需搜索的叶结点的个数较多,如果择序使得博弈是...
  • 在Alpha-Beta算法的并行化的过程中,一个较为困难的问题是判断从哪里开始并行搜索,因为一个分支的搜索可能会发现并行进行的另一个搜索完全可以避免.正因为如此,Alpha-Beta算法是一个很难并行的算法. 虽然仿真可能...
  • 由于博弈双方是交替移动的,所以博弈的结点及其父结点分属于两个对抗者中的一个,他们的种类(type)分属max和min.博弈上的每个结点对应于一个深度(depth),叶结点的深度为0.因此,在任意的结点node,对
  • 首先要定义问题的解,并分析解空间范围和拓扑结构,然后根据解空间的范围和拓扑结构设计遍历搜索算法。 建立数学模型,根节点为初始状态,叶子节点可能是最终状态,也可能是某个无法转换的最终中间状态,有多少...
  • 蒙特卡洛树搜索(MCTS)算法

    万次阅读 多人点赞 2017-10-24 18:29:38
    论文原文下载地址:...Deepmind 官网的介绍:AlphaGo Zero: Learning from scratch一、蒙特卡洛树搜索(MCTS)算法MCTS算法是一种决策算法,每次模拟(simulation)分为4步: 1. Tree traversal: UCB1(Si)=Vi¯¯
  • 蒙特卡洛树搜索

    千次阅读 2019-11-03 10:03:20
    蒙特卡洛树搜索 一、基本思想 要搞清楚蒙特卡洛树搜索的基本思想首先要明白什么是蒙特卡洛树?...蒙特卡洛树搜索算法是一种用于决策的启发式搜索算法,在上《人工智能基础》这门课时,接触过几个启发式搜...
  • AlphaGo背后的搜索算法:蒙特卡罗树搜索 本文首发于微信公众号号“编程派”。微信搜索“编程派”,获取更多Python编程一手教程及优质资源吧。 昨天(3月9日)下午,经过三个多小时的...
  • python 算法-二叉搜索树

    万次阅读 2020-07-10 14:01:14
    python 算法-二叉搜索树 文章目录python 算法-二叉搜索树1、实现2、二叉搜索树-Coding 1、实现 2、二叉搜索树-Coding
  • DFS(深度优先搜索算法)

    万次阅读 多人点赞 2018-10-07 16:32:43
    深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索或图的算法。 沿着的深度遍历的节点,尽可能深的搜索的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到...
  • 求各路大神,有没有用matlab实现的找出有向图的所有生成算法?毕设需要,跪谢!
  • 决策分类算法

    千次阅读 2016-10-26 15:56:22
    最近在学习数据挖掘,算法的重要性可想而知,先学习下理论,本篇是关于决策树算法,参考了一些博客,觉得写的非常不错。后面会结合代码来实现这些算法,并尝试着使用mahout等框架来使用这些算法解决实际的问题
  • 最优二叉搜索树动态规划算法

    千次阅读 2017-06-20 17:45:37
    最优二叉搜索树动态规划算法题目描述: Java实现:import java.util.Scanner;public class BestBinarySearchTree { public static void main(String[] args) { // TODO 自动生成的方法存根 Scanner sc=new ...
  • 各种搜索算法复杂度

    千次阅读 2014-05-21 14:58:40
    参考 树搜索算法 http://hi.baidu.com/jjgjklk/item/9924e3a01f633b258919d305
  • 机器智能-高频问题-无信息搜索算法

    千次阅读 2020-03-08 21:31:47
    首先,解释一下名词,什么是“树搜索算法”? 树搜索算法并不是特指一个算法,而是指一类基于树结构的搜索算法(如深度优先和广度优先等) 当然,还有一个名词,什么是“图搜索算法”? 图搜索不会重复搜索节点,树...
  • 快速搜索随机树算法(RRT)和A*算法

    千次阅读 2020-12-16 09:22:41
    1.简述快速搜索随机树算法 快速生长随机树算法需要知道整个环境信息,通过随机采样的方法并通过一系列判断来找到起点和终点之间的一条可行路线。这种方法在概率上是可以找到一条可行路线的,但是需要足够长的时间,...
  • RFID防碰撞 二进制搜索算法 C语言实现

    千次阅读 热门讨论 2018-04-01 20:31:13
    本篇文章只是简单的用C语言模拟出了二进制搜索算法的实现方法,但是并没有用到理论中的二叉树排序理论,所以并不是一个严格意义上的搜索算法 话不多说,先上一段A标签收到读写器发送的REQUEST命令的程序 if(a...
  • 算法的基本思想是,利用已经搜索过的状态对搜索进行剪枝,以提高搜索的效率。算法首先按照一定原则模拟双方一步步下棋,直到向前看几步为止,然后对棋局进行打分(分数越大表明对我方越有利,反之表明对对方有利)
  • Merkle Tree(默克尔算法解析

    万次阅读 多人点赞 2017-01-20 17:52:14
    Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵。Merkle的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1]1、HashHash是一个把任意长度的...
  • 蒙特卡洛树搜索(Monte-Carlo Tree Search,简称MCTS) 这是许多游戏的核心算法。顾名思义,这是一种常见的数据结构——树。这棵树的每一个节点都代表游戏的一个当前局面的确定状态。在每局游戏过程中,每一步落子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 196,678
精华内容 78,671
关键字:

树搜索算法