Problemas com HashSet (grande) de Inteiros [RESOLVIDO]

Programação
#1

Boa noite pessoas. Bom, estou tendo problemas com HashSet. Após consultar diversos tópicos aqui, ainda continuo sem entender o que estou fazendo de errado. Pois bem, Vamos começar:

/**
 * Resolve um problema pelo metodo da busca em arvore.
 * @return os passos para resolver o problema, caso haja
 * solucao.
 */
public String[] busca() {
	List<No> borda = estrategia.criaLista(); // criando a borda
	Collection<Long> gerados = new HashSet<>(); // estados gerados
	No no;
	
	// Adiciona o no do estado inicial a borda
	borda.add(new No(null, problema.getEstadoInicial(), null, 0, 0));
	nos = 0;
	profundidade = 0;
	
	while (true) {
		// Se a borda for vazia, entao retorna fracasso
		if (borda.isEmpty()) 
			
			return new String[] {};
		
		// Remove o primeiro no da borda
		no = borda.remove(0);
		// Diga que este estado ja foi gerado
		gerados.add(no.getEstado().getId());
		nos ++;
		profundidade = no.getProfundidade();
		
		// Se o estado atual for o estado objetivo, entao
		if (no.getEstado().eObjetivo())
			// retorne a solucao do problema
			return solucao(no);
		
		// Senao, expande o no e adiciona os seus sucessores a borda
		estrategia.adiciona(borda, expande(no, gerados));
	}
}

Para cada nó visitado (como visto acima), eu guardo o seu ID gerado pelo método getId(). Estou fazendo isso para que, no método abaixo, não haja a possibilidade de algum estado gerado anteriormente (de mesma ID) entre novamente na lista e seja expandido futuramente:

/**
 * Expande um no e retorna a lista de nos sucessores, ou seja, os
 * outros estados que podem ser alcancados a partir deste no.
 * @param no no do estado atual do ambiente
 * @param gerados lista dos estados gerados anteriormente
 * @return a lista de estados sucessores do estado do no atual
 */
private List<No> expande(No no, Collection<Long> gerados) {
	List<No> sucessores = estrategia.criaLista();
	Acao acao;
	Estado resultado;
	
	// Para cada (acao, sucessor) em sucessor(estado) faca
	for (Object[] ar : problema.sucessor(no.getEstado())) {
		acao = (Acao) ar[0];
		resultado = (Estado) ar[1];
		
		// Se o estado ainda nao foi gerado anteriormente, entao
		if (!gerados.contains(resultado.getId()))
			// adicione ele a lista de sucessores
			sucessores.add(new No(no, resultado, acao,
					resultado.distancia(no.getEstado()) +
					resultado.heuristica() + no.getDistancia(),
					1 + no.getProfundidade()));
	}
	
	return sucessores;
}

Como funciona a funcao ID no caso do problema? Dada a seguinte matriz (quebra cabeça de 8 onde 0 é o espaco vazio):
±-±-±-+
| 6 | 0 | 4 |
±-±-±-+
| 5 | 2 | 3 |
±-±-±-+
| 1 | 7 | 8 |
±-±-±-+
id = 871325406

Aqui está a implementação da função ID:

@Override
public long getId() {
	// TODO Auto-generated method stub
	int i, j, id;
	
	id = 0;
	
	for (i = 0; i < 3; i++)
		for (j = 0; j < 3; j++)
			id = id * 10 + pecas[i][j];
	
	return id;
}

Pelo que andei lendo, A funcao HashCode retorna o próprio valor do Integer guardado no HashSet. Porém estados repetidos estão sendo analisados mais de uma vez resultando em 458138 nós que é superior a 9!/2 = 181440. Já não sei mais o que fazer e não sei o que estou fazendo de errado.

#2

Quem se interessar, aqui está o projeto completo :slight_smile: abraços

#3

O problema deve estar no cálculo:

id += pecas[i][j] * (int) Math.pow(10, 3*i + j);

Supondo que pecas variam de 0 a 8, então quando for (i,j) = (0,3) e (i,j) = (1,0), somará a mesma casa decimal, podendo aparecer o dígito 9.

Não sei se resolve, mas poderia tentar:

id = id * 10 + pecas[i][j];

#4

Opa, vou testar está solução. Não pensei por este lado. Muito obrigado pela observação :wink: estou com uma semana muito corrida e eu realmente não parei pra observar este detalhe

#5

Falha minha, testei aqui e os índices estão corretos, j não pode ser 3.

Vc tem certeza que todas as peças são de 0 a 8?

#6

Verifiquei que na classe Tabuleiro, o getId está diferente do que vc postou aqui, lá está:

id += pecas[i][j] * (int) Math.pow(10, 8 - 3*i + j);

que é diferente:

id += pecas[i][j] * (int) Math.pow(10, 3*i + j);

#7

Eu dei uma alterada no código do git. Mas estou usando a solução que sugeriu eu estou estudando HashSet, HashMap e Collection para ver onde estou errando. Mas sim, estou garantindo que o intervalo das peças do tabuleiro sejam de 0 a 8 :slight_smile:

#8

Foi um erro de lógica meu mesmo. Durante a depuração, o HashSet estava com o tamanho correto (181440), ou seja, todos os estados possíveis foram gerados. Porém, as vezes ocorria do estado não estar na lista de gerados e ele, por consequência, entra na borda (nos a serem expandidos) mais de uma vez (as vezes um estado A gera um estado C e um outro estado B pode gerar C mais de uma vez em decorrência de movimentos inválidos para este estado). Como C não está na lista de gerados, logo ele se torna elegível para ser expandido mais de uma vez no decorrer da execução. Então estou informando a lista de gerados em dois momentos: quando retiro o nó e durante a sua expansão. Muito obrigado pela atenção :slight_smile: