2016-05-31 52 views
0

我已经建立在J​​ava中我自己的树的数据类,这是一个极小的运算法则用来填充树的每个节点下面的4个孩子。树中的每个节点都会保存代表独特游戏状态的Board对象(我创建的其他东西),并且树中的边(代表移动方向 - 游戏是Tron)表示用户为达到状态边缘导致。我想创建一个函数,它接受一个树并递归填充深度为“DEPTH”(在其他地方作为常量保持,而不是参数),并给出修改的游戏状态,给出每个玩家在四个可能的整数移动中的每一个每个级别。我只是不太确定如何最好地做到这一点...如何递归在Java中

而且,因为它是被用于极小,树结构具有如下:

  • 根表示当前,不变游戏状态
  • 1级儿童代表改变游戏状态给用户的4个可能的举动
  • 2级儿童代表改变游戏状态给对手的4个可能的举动
  • 第三级的游戏状态为用户的4个给出的移动对手的动作,a第二等等......上延伸到水平的深度数值

这里是我有工作的基本方法:

  • 的树采取了董事会和整数方向导致构造董事会
  • 一个名为produceChildren(方法),需要一个树和布尔“userMove”,并增加了4个新局向树的内部代表给每个用户或对手的4个可能移动的改变游戏状态下儿童的名单。 'userMove'参数指定作为儿童制作的委员会应该是用户4次移动的结果还是对手的4次移动的结果。
  • 树的方法称为getDepth()返回由其父和儿童的更大的树中节点的深度(如果有的话) - >返回0,如果它是根

任何人都可以也许给我提供一些伪代码(使用我提供的方法,除非需要其他方法),我如何以这种交替的,最小化的方式填充一棵树?

回答

1

我有一对夫妇对你的数据结构的意见,你移动到执行的逻辑之前。

这是没有必要的板的完整副本存储在树的每个节点。鉴于它被用于极大极小,每一点你唯一需要知道的就是到达那里的动作和那个位置的价值。您需要知道叶子中的棋盘状态以计算该值,但即使这样,一旦计算完成,就不需要保留其副本。

要走得更远,极大极小甚至不要求你保持树的永久副本。如果使用递归完成,每个节点的最大值或最小值可以保存在局部变量中并返回 - 不需要在树中保留永久副本。

minimax维基百科的文章有一些伪代码,可以让你开始。