文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于Matlab的0_1背包问题的动态规划方法求解
侵权投诉

基于Matlab的0_1背包问题的动态规划方法求解

92 计算机技术与发展 第16卷

1)持球队员决策。

对于持球队员来说,首先考虑的是把球控制在自己的范围内,如果球被对方球员截到,进攻就无从谈起。在对手离球较近(其威胁性也大)的情况下,持球队员优先执行各种控球的策略,对球进行彻底的控制。而在对手离球较远(其威胁性也小)的情况下,持球队员才可以考虑如何组织进攻。组织进攻包括自己是否应该继续带球、预测周边的队友下一步的动作(以便更好地传球)及其传球的路线选择等。持球队员的决策在一个完整的进攻中处于核心地位(可以直接影响球的位置和速度),同时可以对无球队员决策进行方向性的指导。好的持球队员的决策决定了进攻的成败。持球队员是进攻的发起者。

2)无球队员决策。

对于无球队员来说,无须考虑控球的问题,也暂时无法影响球的位置和速度。无球队员的决策是以对持球队员行为的预测为核心。无球队员根据预测出持球队员动作(带球或传球)的情况,决定自己的行为。无球队员的行为主要是跑位,根据设定的有利进攻点来调整自身的方向。同时无球队员应做好对方可能会断球、球被断后进行快速抢球及其完成从无球队员到持球队员转换的准备。无球队员是进攻的响应者。

如图1(a)所示,持球队员首先预测了队友的动作(图中虚线箭头所示),将球沿实线箭头传给队友;同时如图1(b)所示,无球队员首先预测了队友的动作(传球),并预测球的路线(图中虚线箭头所示),同时决定沿实线箭头跑位。比较同一情况下两名不同位置的球员的决策,可以发现虽然预测和实际的动作有出入,但从总体上可以认为这两个agent完成了配合,达到了想要的结果(实现了非通讯状态下的球员之间的合作,即球员之间产生了(默契))。

实验表明,这种以持球队员为核心的进攻策略简化了agent考虑的因素,提高了传球的目的性,加快了进攻的速

(上接第89页)

度,从而实现了预期的球员之间的(默契)

基于Matlab的0_1背包问题的动态规划方法求解

。

图1 同一情况下球员的决策

4 结束语

从多agent系统研究入手,根据RoboCup的具体情况,实现了非通讯状态下agent之间的配合。在调整了考虑的agent的数目后,我们的策略达到了预期的效果。下一步,考虑增加对对手的建模,提高传接球的质量,以期得到更好的进攻成功率。

参考文献:

[1] 咸鹤群,孟庆春,殷 波,等.多Agent系统中潜在角色值研

究[J].哈尔滨工业大学学报,2003,35(9):1089-1092.[2] 祁正华,任勋益.基于MAS的智能决策支持系统研究[J].

微机发展,2004,14(9):14-16.

[3] 陈进才.多Agent系统的形式化理论研究[D].西安:西安

交通大学,2000.

[4] KokJR,SpaanMTJ,VlassisN.Non-communicativemulti

-robotcoordinationindynamicenvironments[J].RoboticsandAutonomousSystems,2005,50:99-114.

[5] 张颖霞,杨宜民,陈 波,等.多智能体团队合作在机器人

足球赛中的应用[J].微机发展,2004,14(7):112-114.

中,不得不存储实施过程中产生的各种状态,而造成空间复杂度比其它算法要高。

文中选择动态规划算法来解决背包问题,且认为它在空间上是可以承受的,而采用搜索算法在时间上却是难以承受的。舍空间而取时间,这正是该算法在解决背包问题上体现出的一种优越性。

一次,因此可节省大量的计算时间而具有更高的运行效率。

参考文献:

[1] 玄光男,程润伟 遗传算法与工程优化[M] 北京:清华大

学出版社,2004.55-63

[2] 罗小虎,赵 雷 一个解决0/1背包问题的蚁群算法[J]

苏州大学学报(工科版),2004(2):41-44

[3] SupowitK.FindingaMaximumPlanarSubsetofaSetof

NetsinaChannel[J].IEEETransationsonComputer-Aid edDesignofIntegratedCircuitsandsystems,1987,6(1):93-94.

[4] 阮沈勇,王永利,桑群芳 Matlab程序设计[M] 北京:电子

工业出版社,2004.

[5] 施益昌,郑贤斌,李自立 基于Matlab动态规划中最短路

[,:405 结束语

文中把动态规划方法用于求解背包问题,其算法是以空间换时间来解决问题的一种有效的方法。在解决实际问题的过程中,面对复杂问题而分解出的子问题往往并不是孤立的,要解决问题的子问题常常需要调用相同的子问题的子问题。如果它们之间也不是独立的,采用分治法势必会在解决同样的问题上造成很大的时间浪费。由于动

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email