Algoritmo de Busca

25 de setembro de 2008 7 respostas

malstryx 25 de setembro de 2008

Ae…

To fazendo um algoritmo de busca por largura(puzzle 3x3). A estrutura esta montada tudo certo, só que pra cada estado novo cria um objeto novo que verifica novamente os estados possiveis, e por ai vai. Isso ta dando um erro (Exception in thread “main” java.lang.StackOverflowError), que dei uma olhada, e vi que é algo sobre quando se tem um looping infinito de objetos criados, a memória n suporta (é isso né? )…

Vi sobre pilha, isso resolveria? E queria saber como funciona… ela remove os objetos criados da memória, algo assim?

Se alguem puder ajudar, ou passar um link sobre o assunto, mas algo didático pois nunca trabalhei com isso…

Vlws abçs

7 Respostas

Jdanos 25 de set. de 2008

Põe o código ae q agente ajuda

eclipso 26 de set. de 2008

É um processo recusrsivo?

malstryx 26 de set. de 2008

Vou mostrar um esboço…

public class Node {

//Essa classe tem um ArrayList aonde armazeno os estados visitados para não repeti-los

estadosVisitados ev = new estadosVisitados();

// Fiz um construtor para receber os parâmetros

public Node(Node pai, int tabuleiro[][], int nivel) {
	        this.tabuleiro = tabuleiro;
	        this.pai = pai;
	        filho = new Node[4];
	        this.nivel = nivel;
	        grau = 0;
	        ev.estados.add(this.tabuleiro);	
	        
	        resolver();

	    }	    

// O método resolver chama o método para achar a posição "0", e depois o mover. 

public void resolver() {
	    	if(ehMeta(this.tabuleiro) == false) {
	    		acharPosicaoZero(this.tabuleiro);

// Toda vez que ele acha uma nova posição ele adiciona no ArrayList estados visitados da outra classe, sendo que ele sempre verifica se já está criado.
	    		mover(this.linha,this.coluna);
	    	}
	    		else {
	    			System.out.println("Solução!");
	    	}
	    }

// Esse método, sempre que o mover achar um movimento true, ele o usa.
// Aqui eu crio um novo objeto Node, e no contrutor ele chama o método resolver() novamente para o novo estado, e assim vai, e da um looping infinito, por isso o erro.

public void setFilho(int tabuleiro[][]) {
	        filho[grau] = new Node(this, tabuleiro, nivel + 1);
	        grau++;
	        ev.estados.add(tabuleiro);
	        
	    } 


// E no main() eu instancio o primeiro objeto setando o estado inicial, e começa o "looping"...

Alguém dá um help ???

vlws abçs.

Jdanos 27 de set. de 2008

Então cara ainda fica um pouco confuso (pelo menos pra mim, que sou noao em java tbm) , mas assim ao que parece vc tem um loop infinito de criação de objetos, ou seja uma hora o Heap num vai ter mais espaço para criação de objetos (lembre-se objetos residem no Heap).

Continuando… o que parece é que existe pouca tarefa pra muito objeto, vc já tentou fazer um fluxograma antes de escrever um programa? as vezes p;arece que não mas agente perde um bocado de tempo tentando resolver este tipo de problema programando quando uma caneta, régua e papel fariam todo o trabalho, mas sei também que quando estamos querendo aprender a escrever não nos preucupamos muito com a qualidade de nossa letra.

Mas é isso ae espero ter ajudado.

Caso esteja afim, coloque o programa todo, eu posso roda-lo aqui na minha máquina e t ajudar a resolver o problema.

sergiotaborda 27 de set. de 2008

malstryx:
Ae…

To fazendo um algoritmo de busca por largura(puzzle 3x3). A estrutura esta montada tudo certo, só que pra cada estado novo cria um objeto novo que verifica novamente os estados possiveis, e por ai vai. Isso ta dando um erro (Exception in thread “main” java.lang.StackOverflowError), que dei uma olhada, e vi que é algo sobre quando se tem um looping infinito de objetos criados, a memória n suporta (é isso né? )…

É isso.

O seu exemplo é confuso. Primeiro vc fala que está pequisando um puzzle mas depois a sua classe chama-se Nodo ? Afinal o que vc está fazendo ?

Se o objetivo é encontrar alguma coisa na arvore e está precisando ler todos os nodos o padrão recomendado é Visitor ( aliás a variável estadosVisitados já indica que deve ser isso que vc precisa). Sem saber realmento o que vc quer - porque não entendi nem o codigo nem a aplicação, é o maximo que dá para dizer…

malstryx 27 de set. de 2008

import java.util.*;
public class estadosVisitados {
	
	ArrayList estados = new ArrayList();

}

import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Node {
		
		estadosVisitados ev = new estadosVisitados();
	
	    int tabuleiro[][];
	    Node pai;
	    Node filho[];  
	    
	    int ehMeta[][] = {{1, 2, 3},
                {4, 5, 6},
                {8, 9, 0}};
	    
	    int nivel, linha, coluna, grau, mover = 1, tamanho = 3;
	  
	    public Node(Node pai, int tabuleiro[][], int nivel) {
	        this.tabuleiro = tabuleiro;
	        this.pai = pai;
	        filho = new Node[4];
	        this.nivel = nivel;
	        grau = 0;
	        ev.estados.add(tabuleiro);
	        
	        resolver();

	    }	    
	    
	    public void setFilho(int tabuleiro[][]) {
	        filho[grau] = new Node(this, tabuleiro, nivel + 1);
	        grau++;	        
	    } 
	    
	    public void acharPosicaoZero(int tabuleiro[][]) {
	    	
	    	boolean encontrado = false;
	    	
	    	while (encontrado == false) {
	    		for(int l = 0; l < tabuleiro.length; l++) {
	    			for(int c = 0; c < tabuleiro.length; c++) {
	    			
	    			if(tabuleiro[l][c] == 0) {
	    				encontrado = true;
	    				
	    				linha = l;
	    				coluna = c;
	    				
	    				}
	    		 	}
	    		}	
	    	}    	
	    }
	    
	    public void mover(int l, int c) {
	    	
	    	int[][] tabuleiroClonado = new int[tamanho][tamanho];	
	    		try{
	    			tabuleiroClonado = clonarTabuleiro(tabuleiro);
	    			tabuleiroClonado[l][c] = tabuleiroClonado[l][c - mover];
	    			tabuleiroClonado[l][c - mover] = 0;			
	    			
	    			if(ev.estados.contains(tabuleiroClonado)) {
	    				tabuleiroClonado[l][c] = tabuleiroClonado[l][c + mover];
	        			tabuleiroClonado[l][c + mover] = 0;
	    			}
	    			else {
	    				 this.setFilho(tabuleiroClonado);
	    				 System.out.println(toString(tabuleiroClonado));	
	    			}
	    		}
	    		catch(Exception e){}
	    		
	    		try{
	    			tabuleiroClonado = clonarTabuleiro(tabuleiro);
	    			tabuleiroClonado[l][c] = tabuleiroClonado[l][c + mover];
					tabuleiroClonado[l][c + mover] = 0;
					
					if(ev.estados.contains(tabuleiroClonado)) {
						tabuleiroClonado[l][c] = tabuleiroClonado[l][c - mover];
						tabuleiroClonado[l][c - mover] = 0;
					}
					else{
						this.setFilho(tabuleiroClonado);
						System.out.println(toString(tabuleiroClonado));	 
					}
				}
	    		
	    		catch(Exception e){}
	    		try{
	    			tabuleiroClonado = clonarTabuleiro(tabuleiro);
					tabuleiroClonado[l][c] = tabuleiroClonado[l - mover][c];
					tabuleiroClonado[l - mover][c] = 0;
					
					if(ev.estados.contains(tabuleiroClonado)) {
						tabuleiroClonado[l][c] = tabuleiroClonado[l + mover][c];
						tabuleiroClonado[l + mover][c] = 0;					
					}
					else {
						this.setFilho(tabuleiroClonado);
						System.out.println(toString(tabuleiroClonado));	   
					}
			}
	    		catch(Exception e){}
	    		try{
	    			tabuleiroClonado = clonarTabuleiro(tabuleiro);
					tabuleiroClonado[l][c] = tabuleiroClonado[l + mover][c];
					tabuleiroClonado[l + mover][c] = 0;
					
					if(ev.estados.contains(tabuleiroClonado)) {
						tabuleiroClonado[l][c] = tabuleiroClonado[l - mover][c];
						tabuleiroClonado[l - mover][c] = 0;
					}
					else {
						this.setFilho(tabuleiroClonado);
						System.out.println(toString(tabuleiroClonado));	     				    			
					}
			}
	    		catch(Exception e){}
	    	}
	    private int[][] clonarTabuleiro(int[][] tabuleiro) {
	        int[][] novo = new int[tabuleiro.length][tabuleiro[0].length];
	        for (int i = 0; i < tabuleiro.length; i++) {
	            for (int j = 0; j < tabuleiro[0].length; j++) {
	                novo[i][j] = tabuleiro[i][j];
	            }
	        }
	        return novo;
	    }
	    public String toString(int[][] tabuleiro) {
	        String codigo = "";
	        for (int i = 0; i < tabuleiro.length; i++) {
	            for (int j = 0; j < tabuleiro[i].length; j++) {
	                codigo += tabuleiro[i][j];
	            }
	        }
	        return codigo;
	    }
	    
	    public void resolver() {
	    	if(ehMeta(this.tabuleiro) == false) {
	    		acharPosicaoZero(this.tabuleiro);
	    		mover(this.linha,this.coluna);
	    	}
	    		else {
	    			System.out.println("Solução!");
	    			System.exit(0);
	    	}
	    }

	    
	    private boolean ehMeta(int [][]tablero){	
	    	
 		   if(  tablero[0][0] == ehMeta[0][0] &&
 				tablero[1][0] == ehMeta[1][0] &&
 				tablero[2][0] == ehMeta[2][0] &&
 				tablero[0][1] == ehMeta[0][1] &&
 				tablero[0][2] == ehMeta[0][2] &&
 				tablero[1][1] == ehMeta[1][1] &&
 				tablero[2][2] == ehMeta[2][2] &&
 				tablero[1][2] == ehMeta[1][2] &&
 				tablero[2][1] == ehMeta[2][1]) {
 		
 		return true;
 }
 		   else {
 			   return false;
 		   }
	}
}

import java.awt.event.*;
import java.util.ArrayList;
import javax.swing.*;

import javax.swing.JButton;

public class Jogo {
	private int tabuleiro[][];
	private final int tamanho = 3; 

    
	public Jogo() {
		tabuleiro = new int[tamanho][tamanho];		
	}
	
	public static void main(String[] args) {
		Jogo jogo = new Jogo();
			jogo.inicializarTabuleiro();
			
		Node node = new Node(null,jogo.getTabuleiro(),0);
	}	
	public int[][] getTabuleiro() {
		return tabuleiro;
	}
	public void inicializarTabuleiro() {
	   	 
    	ArrayList lista = new ArrayList();
            for (int i = 0; i <= 8; i++) {
                lista.add(new Integer(i));
            }
 
            for (int i = 0; i < tabuleiro.length; i++) {
                for (int j = 0; j < tabuleiro[i].length; j++) {
                    int indice = (int) (Math.random() * (lista.size()));
                    tabuleiro[i][j] = ((Integer) lista.get(indice)).intValue();
                    lista.remove(indice);
            }
        } 
    }
}

malstryx 28 de set. de 2008

Alguém???

Criado 25 de setembro de 2008

Ultima resposta 28 de set. de 2008

Respostas 7

Participantes 4

7 Respostas

Topicos relacionados