rekursiv erstellen einer Struktur
Ich versuche rekursiv füllen ein Baum, aber mein code ist nur Sie nur füllen Sie eine Tiefe Länge, und dann quiting. d.h. jeder Knoten hat nur ein Kind. Gibt es etwas, bin andernfalls zu nehmen zu berücksichtigen?
public static void populate(Node n, int depth, String player){
System.out.println("Depth: " + depth);
if(player.equalsIgnoreCase("X"))
player = "O";
else
player = "X";
int j = 0;
System.out.println("empty spots: " + ((Board)n.getData()).noOfEmpty());
for(int i=0; i<((Board)n.getData()).noOfEmpty(); i++){
if(((Board)n.getData()).getSquare(j).equalsIgnoreCase("X")
|| ((Board)n.getData()).getSquare(j).equalsIgnoreCase("O"))
j++;
else{
Board tmp = new Board(((Board)n.getData()), j, player);
Node newNode = new Node(tmp);
tree.insert(n, newNode);
populate(newNode, depth-1, player);
}
}
}
P. S. und ich check das noOfEmpty()
return-Wert, der sollte bestimmen die Anzahl der Kinder eines Knotens haben sollte.
edit:@eznme der komplette code, wie verlangt:
public class MinMax {
protected static Tree tree;
public static void createTree(Board b){
tree = new Tree();
tree.setRoot(new Node(b));
populate(tree.getRoot(), 5, "X");
//System.out.println("printing tree");
//tree.print(1);
}
public static void populate(Node n, int depth, String player){
System.out.println("Depth: " + depth);
if(player.equalsIgnoreCase("X"))
player = "O";
else
player = "X";
int j = 0;
System.out.println("empty spots: " + ((Board)n.getData()).noOfEmpty());
for(int i=0; i<((Board)n.getData()).noOfEmpty(); i++){
if(((Board)n.getData()).getSquare(j).equalsIgnoreCase("X")
|| ((Board)n.getData()).getSquare(j).equalsIgnoreCase("O"))
j++;
else{
Board tmp = new Board(((Board)n.getData()), j, player);
Node newNode = new Node(tmp);
tree.insert(n, newNode);
populate(newNode, depth-1, player);
}
}
}
}
import java.util.ArrayList;
/**
*
* @author Greg
*/
public class Node {
protected Object data;
protected int score; //fields to be used by the MaxMin class
protected ArrayList<Node> children;
//constructors
public Node(){
children = new ArrayList(0);
data = null;
}
public Node(Object obj){
children = new ArrayList(0);
data = obj;
}
public void setChild(Node n){
//EFFECT: set the ith child to node t
children.add(n);
}
public void setChildren(Node[] t){
//EFFECT: copy the array t, into the array children, effectively
//setting all the chidern of this node simultaneouly
int l = children.size();
for(int i=0; i<t.length; i++){
children.add(l, t[i]);
}
}
public void setData(Object obj){
//EFFECT: set the date of this node to obj, and also set the number of
// children this node has
data = obj;
}
public Node getChild(int i){
//EFFECT: returns the child at index i
return children.get(i);
}
public int noOfChildren(){
//EFFECT: return the length of this node
return children.size();
}
public Object getData(){
//EFFECT: returns the data of this node
return data;
}
@Override
public String toString(){
//EFFECT: returns the string form of this node
return "" + data.toString() + "\nwith " + noOfChildren()+ "\n";
}
public boolean isLeaf(){
if(children.size()==0)
return true;
return false;
}
public void setScore(int scr){
score = scr;
}
public int getScore(){
return score;
}
}
public class Tree {
private Node root;
public Tree(){
setRoot(null);
}
public Tree(Node n){
setRoot(n);
}
public Tree(Object obj){
setRoot(new Node(obj));
}
protected Node getRoot(){
return root;
}
protected void setRoot(Node n){
root = n;
}
public boolean isEmpty(){
return getRoot() == null;
}
public Object getData(){
if(!isEmpty())
return getRoot().getData();
return null;
}
public Object getChild(int i){
return root.getChild(i);
}
public void setData(Object obj){
if(!isEmpty())
getRoot().setData(obj);
}
public void insert(Node p,Node c){
if(p != null)
p.setChild(c);
}
public void print(int mode){
if(mode == 1) pretrav();
else if(mode == 2) postrav();
else
System.out.println("yeah... mode 1 or 2...nothing else, try agn");
}
public void pretrav(){
pretrav(getRoot());
}
protected void pretrav(Node t){
if(t == null)
return;
System.out.println(t.getData()+" \n");
for(int i=0; i<t.noOfChildren(); i++)
pretrav(t.getChild(i));
}
public void postrav(){
postrav(getRoot());
}
protected void postrav(Node t){
if(t == null)
return;
System.out.print(t.getData()+" ");
for(int i=0; i<t.noOfChildren(); i++)
pretrav(t.getChild(i));
System.out.print(t.getData()+" ");
}
}
public class Board {
boolean isFull = false; //a check to see if the board is full
String[] grid = new String[9]; //an array represting the 9 square on a board
int hV;
String MIN, MAX;
public Board(){
for(int i=0; i<grid.length;i++)
grid[i] = Integer.toString(i);
hV = heuristicValue(this);
}
public Board(Board b, int x, String player){
this.grid = b.getBoard();
if(!(grid[x].equalsIgnoreCase("X")|| grid[x].equalsIgnoreCase("X")))
grid[x] = player;
}
public boolean setSquare(String player, int position){
/*
EFFECT:set a square on the board to either a X or a O, debending on the player
PRECON: square (x,y) is empty
POATCON: square (x,y) has player 'symbol'
*/
boolean isValidPlay = false;
try{
//as a sanity
Integer.parseInt(grid[position]);
grid[position] = player;
isValidPlay = true;
}catch(NumberFormatException e){
System.out.println("positon " + position + "is already occupied");
}
return isValidPlay;
}
public boolean endGame(){
/*
* EFFECT: check to see if the game have been won or drawn
*/
if(ticTacToe(0,1,2)){
//System.out.println("Player " + grid[0] + " wins");
return true;
}
else if(ticTacToe(3,4,5)){
//System.out.println("Player " + grid[3] + " wins");
return true;
}
else if(ticTacToe(6,7,8)){
//System.out.println("Player " + grid[6] + " wins");
return true;
}
else if(ticTacToe(0,4,8)){
//System.out.println("Player " + grid[0]+ " wins");
return true;
}
else if(ticTacToe(0,3,6)){
//System.out.println("Player " + grid[0]+ " wins");
return true;
}
else if(ticTacToe(1,4,7)){
//System.out.println("Player " + grid[1] + " wins");
return true;
}
else if(ticTacToe(2,5,8)){
//System.out.println("Player " + grid[2] + " wins");
return true;
}else if(ticTacToe(2,4,6)){
//System.out.println("Player " + grid[2] + " wins");
return true;
}
else
return isDrawn();
}
public boolean ticTacToe(int x, int y, int z){
/*
* check is x, y and z has the same value
*/
try{
Integer.parseInt(grid[x]);
return false;
}catch(NumberFormatException e){
if( grid[x].equals(grid[y])
&& grid[x].equals(grid[z]))
return true;
else
return false;
}
}
public String getSquare(int i){
return grid[i];
}
@Override
public String toString(){
String msg = "";
for(int i=0; i<grid.length; i++){
msg = msg + grid[i] + " ";
if(i==2 || i==5)
msg = msg+ "\n";
}
return msg;
}
public boolean isDrawn(){
/*
* check to see if there are any 'free' spaces on the board, if there are any
* return false, else return true
*/
for(int i=0; i<grid.length; i++){
try{
Integer.parseInt(grid[i]);
return false;
}catch(NumberFormatException e){
}
}
System.out.println("Game drawn");
return true;
}
public String[] getBoard(){
return grid;
}
public int noOfEmpty(){
//EFFECT: returns the number of empty squares
int count = 0;
for(int i=0; i<grid.length; i++)
if (!(grid[i].equalsIgnoreCase("X") || grid[i].equalsIgnoreCase("O")))
count++;
return count;
}
public int heuristicValue(Board b){
String MAX = "X", MIN = "O";
/*
* calculate a value that will be used as a heuristic function
* the function works for ever X in a row WITHOUT O: 1 point,
* for two X in a row WITHOUT a O: 5 points
* and 3 X in a row: 100 points
*/
//System.out.println("Computing heuristic");
//System.out.println("Computing horizontals");
int hCount = 0;
//sum up the horizontals
for(int i=0; i<9; i=i+3){
int tmpMAX = playerCount(b, MAX,i,i+1,i+2);
int tmpMIN = playerCount(b, MIN,i,i+1,i+2);
//System.out.println(tmpMAX);
//System.out.println(tmpMIN);
if(tmpMIN > 0){
//System.out.println("Min was zero");
}
else if(tmpMAX==1){
//System.out.println("has one");
hCount = hCount + 1;
}
else if(tmpMAX==2){
//System.out.println("was tw0");
hCount = hCount + 5;
}
else if(tmpMAX==3){
//System.out.println("full 100");
hCount = hCount + 100;
}
}
//System.out.println("Computing verticals");
//sum up the verticals
for(int i=0; i<3; i++){
int tmpMAX = playerCount(b, MAX,i,i+3,i+6);
int tmpMIN = playerCount(b, MIN,i,i+3,i+6);
if(tmpMIN > 0){}
else if(tmpMAX==1){
hCount = hCount +1;
}
else if(tmpMAX==2){
hCount = hCount + 5;
}
else if(tmpMAX==3){
hCount = hCount + 100;
}
}
//System.out.println("Computing diagonals");
//sum up diagonals
if(playerCount(b, MIN,0,4,8)==0){
if(playerCount(b, MAX,0,4,8)==1){
hCount = hCount + 1;
}
if(playerCount(b, MAX,0,4,8)==2)
hCount = hCount + 5;
if(playerCount(b, MAX,0,4,8)==3)
hCount = hCount + 100;
}
if(playerCount(b, MIN,2,4,6)==0){
if(playerCount(b, MAX,2,4,6)==1){
hCount = hCount + 1;
}
if(playerCount(b, MAX,2,4,6)==2)
hCount = hCount + 5;
if(playerCount(b, MAX,2,4,6)==3)
hCount = hCount + 100;
}
//System.out.println("Computing completed");
int hV = hCount;
return hV;
}
int playerCount(Board b, String player, int x, int y, int z){
int count = 0;
if(b.getSquare(x).equals(player))
count = count + 1;
if(b.getSquare(y).equals(player))
count = count + 1;
if(b.getSquare(z).equals(player))
count = count + 1;
//System.out.println("playerCount; " + count);
return count;
}
}
import java.io.*;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));
Board thisGame = new Board();
System.out.println("Start \n" + thisGame.toString());
MinMax.createTree(thisGame);
System.exit(0);
}
}
- bitte poste kompletten code, so können wir kompilieren und führen Sie es
- werde versuchen, aber es ist groß, der komplette code beinhalten 4 Klassen; Knoten, Baum -, Brett-und MinMax
- und es gibt eine main-Klasse, aber das ruft nur die createTree () - Methode MinMax
- keine main-Methode noch
Du musst angemeldet sein, um einen Kommentar abzugeben.
So, hier ist was ich tun würde in deinem Fall (minimax-tic-tac-toe):
Terminologie:
Haben Sie zu halten versuchen, alle Fälle bis: das Brett voll ist ODER ein Spieler gewonnen hat. So, Ihr Baum ist die Höhe, die ist
numberOfCells + 1
.Wenn wir vereinfachen das problem und Mach dir keine sorgen über das symmetrische Duplikate:
Jeder Knoten wird
numberOfcells - nodeDepth
childs.Knoten-Klasse:
this.board = new Board(b);
und nichtthis.board = b
. Sie wollen nicht, um die Wiederverwendung der gleichen Instanz von board geht, sondern um andere (also das ändern eines Knoten-board verändert nicht seine Eltern)Damit zum rekursiven Aufbau einer n-ary tree, ich würde dies tun:
Ich hoffe, es hilft.
Reihenfolge der Knoten Schöpfung mit diesem algo (auf binärer Baum):
populate(rootNode, treeHeight)
. Wenn Sie nur wollen, füllen Sie zwei Ebenen, Sie können einfach anrufenpopulate(rootNode, 2)
, und wenn Sie fortsetzen möchten, füllen Sie einen Baum, der bereits gestartet wurde, können Sie rufen Siepopulate()
auf jedem Knoten, den Sie wollen. Aber ich denke, es wäre eine gute Idee, ein bißchen zu erklären, was Sie wollen, zu tun (es sieht aus wie ein tic-tac-toe zu mir, aber ich finde es seltsam, zu verwenden, ein Baum ist).Ich denke, du hast einen falschen Ansatz.
Zuerst von allen, du machst eine Schleife und Rekursion, neben der Verwendung eines
depth
variable keine Bedeutung hat, da Sie nie überprüfen, ist es Wert, entweder zum Ende der Rekursion, oder, etwas darüber zu wissen, was Sie tun möchten.Verwenden Sie eine dynamische Funktion innerhalb der Schleife selbst ist nicht ganz gut, da die iteration sollte gut definiert aus den Anfang der Schleife.
i
ist nur nutzlos in Ihrem Kontext.Also, wenn ich verstehen Sie Ihren code ein problematischer Fall wäre ein Fall, wo es 3 leere Quadrate und 4 nicht leere Felder, denn Sie würden Durchlaufen
i
von 0 bis 3 und nichts tun, aber die Inkrementierungj
von 0 bis 3 beenden, weili
hätte erreichen 3.Natürlich ich kann mich irren, auf einige Punkte da ich nicht weiß, was
tree
ist, von wo kam es aus? ist das mit dem n? Was ist ein Brett.Ich hoffe mein Beitrag kann dir helfen und ich ermutige Sie, um nach mehr details zu klären, die Löcher und ermöglichen es mir, Ihnen zu helfen ein bisschen mehr.