Oi Taz, pois eh, exemplos assim ficam mais faceis de entender… bem, o que estou fazendo eh estudano varias coisas de IA, muita coisa ja sei, mas agora resolvi implementar tudo, soh na teoria naum da certo 
… estou tentando fazer um conjunto de classes a principio que fazem buscas de solucoes para problemas de IA, como distancia entre cidade, solucao do jogo dos 8, problema das 8 rainhas, monges e canibais enfim, a pessoa define o estado do problema, o estado solucao e executa uma busca especifica (busca extensao, profundidade, bidirecional, A*, tabu, profundidade iterativa, etc etc etc). A principio eu estou menos preocupado em implementar os varios algoritmos e mais preocupado em melhorar a performasse.
Basicamente meu modelo de testes esta para o jogo dos 8 em uma busca por extensao ou profundidade (o que eh o jogo dos 8: http://www.cos.ufrj.br/~ines/courses/cos740/leila/cos740/apres_ia.pdf). O que um algoritmo de busca faz eh a partir de um estado inicial por exemplo:
gerar estados sucessivos ateh encontrar uma estado objetivo
Por exemplo, fazer uma busca por extensao (bem facinho de implementar, a mais simples) iria colocar o estado inicial em uma fila, e comecaria um looping: enquanto tem itens na Fila OU naum achou estado objetivo, remove da Fila e gera os sucessores do estado, entao a principio estado inicial gera os seguintes sucessores:
1 3 5 1 3 5
2 7 6 2 7 X
8 X 4 e 8 4 6
O estado inicial sai da Fila e os sucessores entram, e assim por diante. Cada sucessor guarda a referencia do seu pai, assim quando chegar a um estado objetivo, eu percorro de volta atraves do seu pai ateh o estado inicial sabendo o caminho da solucao.
Tah, isso que falei naum eh invensao nada, eh um algoritmo de busca bemmm simples… mas como vc pode imaginar, nesse jogo eu posso chegar por diversos caminhos a um estado, e se eu ja analisei e coloquei na fila esse estado, naum eh interessante analisar ele de novo, isso eh uma “otimizacao” para os algoritmos de buscas (chamada de busca em grafo, otimizacao entre “” porque as vezes naum eh interessante usar, em buscas por profundidade por exemplo que a vantagem eh o baixo consumo de memoria, mas depende do problema geralmente). Quando a busca lembra dos estados ja expandidos, eh dito que ela tem uma memoria… e essa memoria que eu quero implementar com Set, pois as buscas ai tem que ser muito rapidas, principalmente nesse tipo de busca por “forca bruta” que geram milhares ou milhoes de estados (dependendo do problema). Bem, mas por exemplo nesse jogo, eu posso chegar de varias formas ao mesmo estado, mas os caminhos para chegar ateh ele podem ser diferentes (ou ateh infinitos caminhos), por exemplo para eu chegar no estado:
eu posso dar uma volta animal ou simplesmente mexer uma peca, entao se eu chegar a um estado ja analisado, aquele estado pode ser o pai de um estado que tem um sucessor que chega ateh a solucao, entao eh bom que eu saiba sempre o menor caminho ateh chegar a qualquer estado do problema, entao naum me interessa apenas saber se ele ja foi analisado (se esta no Set), eu quero saber quantos passos tive que dar para chegar ateh aquele que tenho em memoria, se esse numero de passos for maior que o numero de passos que encontrei agora, eu naum vou espandir ele, mas vou trocar o pai daquele que tenho gravado para ser o pai desse que achei (o algoritmo dijstra - caminho minimo - funciona mais ou menos dessa forma)… tai minha necessidade de conseguir ler um objeto de um set que contem NohDaBusca, e que possui um estado e um pai, posso achar outro NohDaBusca com o mesmo estado (entao eles saum iguais), mas o caminho ateh chegar nele eh diferente, e pode ser melhor que o que tenho gravado.
Bem, pensei em usar um HashMap<HashCode do estado, NohDaBusca>, preciso gravar o noh da busca e naum o int do numero de passos porque nem todos problemas tem melhor solucao pelo numero de passos, as vezes existe custo ou alguma particularidade descrita no problema etc etc. Mas apenas pelo fato de eu ter um integer num hashMap a mais, ja me causa uma perda de memoria consideravel (se expandir 1kk de estados, vou ter 1kk de Integer’s no HashMap a mais)…
Fiz testes aqui com TreeSet, TreeMap, HashMap e HashSet
- Sobre a memoria, os melhores foram:
TreeSet -> HashSet -> HashMap -> TreeMap (tah eu naum entendi porque TreeSet consegui inserir mais que em HashSet, ja que TreeSet usa TreeMap, na real nem cheguei a ver muito… mas consegui inserir mais objetos ateh dar OutOfMemory nele no que no HashSet)
- Sobre a performasse de insercao melhores foram:
HashSet -> TreeSet -> TreeMap -> HashMap
- Sobre a performasse das buscas, que eh a performasse que mais me interessa, todos foram muito rapidos, ou pelo menos naum tenho tanta memoria assim no meu pc para conseguir causar uma diferenca heheh.
Enfim, por isso queria usar Set (naum precisa nem ser TreeSet, assim naum preciso obrigar a definicao de um Comparator para estados), ele tem uma performasse de insercao melhor, consome menos memoria (segundo meus testes)… mas naum consigo retornar o key, entao imagino que vou ter que partir para a solucao HashMap<HashCode do estado, NohDaBusca> acho…
Eh isso ai, para isso que quero… pelo que conheco de java, naum consegui achar uma estrura melhor do que Set’s e Map’s para implementar a memoria da minhas buscas…
Valeu 
e naum me chamem de maluco, eh que essa eh a area da comp que eu gosto eheh muito mais do que ficar configurando xml’s para desenvolvimento web eheh :razz: [/code]
