2016-05-31 1 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維基百科的文章有一些僞代碼,可以讓你開始。