、二叉树
树应用及其广泛,二叉树是树中的一个重要类型。在这里,我们主要研究二叉树的一种应用方式:判定树。其主要应用在描述分类过程和处理判定优化等方面上。
在人工智能中,通常有很多分类判断。现在有这样一个例子:设主角的生命值d,在省略其他条件后,有这样的条件判定:当怪物碰到主角后,怪物的反应遵从下规则:
表1
根据条件,我们可以用如下普通算法来判定怪物的反应: if(d<100) state=嘲笑,单挑;
else if(d<200) state=单挑;
else if(d<300) state=嗜血魔法;
else if(d<400) state=呼唤同伴;
else state=逃跑; 上面的算法适用大多数情况,但其时间性能不高,我们可以通过判定树来提高其时间性能。首先,分析主角生命值通常的特点,即预测出每种条件占总条件的百分比,将这些比值作为权值来构造最优二叉树(哈夫曼树),作为判定树来设定算法。假设这些百分比为:
表2
构造好的哈夫曼树为:
图2
对应算法如下: if(d>=200)&&(d<300) state=嗜血魔法;
else if(d>=300)&&(d<500) state=呼唤同伴;
else if(d>=100)&&(d<200) state=单挑;
else if(d<100) state=嘲笑,单挑;
else state=逃跑; 通过计算,两种算法的效率大约是2:3,很明显,改进的算法在时间性能上提高不少。
一般,在即时战略游戏中,对此类判定算法会有较高的时间性能要求,大家可以对二叉树进行更深入的研究。现在,我们进入本文的最后一节:图的介绍,终于快要完事了。
树应用及其广泛,二叉树是树中的一个重要类型。在这里,我们主要研究二叉树的一种应用方式:判定树。其主要应用在描述分类过程和处理判定优化等方面上。
在人工智能中,通常有很多分类判断。现在有这样一个例子:设主角的生命值d,在省略其他条件后,有这样的条件判定:当怪物碰到主角后,怪物的反应遵从下规则:
表1
根据条件,我们可以用如下普通算法来判定怪物的反应: if(d<100) state=嘲笑,单挑;
else if(d<200) state=单挑;
else if(d<300) state=嗜血魔法;
else if(d<400) state=呼唤同伴;
else state=逃跑; 上面的算法适用大多数情况,但其时间性能不高,我们可以通过判定树来提高其时间性能。首先,分析主角生命值通常的特点,即预测出每种条件占总条件的百分比,将这些比值作为权值来构造最优二叉树(哈夫曼树),作为判定树来设定算法。假设这些百分比为:
表2
构造好的哈夫曼树为:
图2
对应算法如下: if(d>=200)&&(d<300) state=嗜血魔法;
else if(d>=300)&&(d<500) state=呼唤同伴;
else if(d>=100)&&(d<200) state=单挑;
else if(d<100) state=嘲笑,单挑;
else state=逃跑; 通过计算,两种算法的效率大约是2:3,很明显,改进的算法在时间性能上提高不少。
一般,在即时战略游戏中,对此类判定算法会有较高的时间性能要求,大家可以对二叉树进行更深入的研究。现在,我们进入本文的最后一节:图的介绍,终于快要完事了。
解决方案 »
免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货