Busca em profundidade e busca em largura  XML
Índice dos Fóruns » Java Básico
Autor Mensagem
Thiago Dantas
Thread.start()

Membro desde: 08/03/2007 18:12:12
Mensagens: 44
Offline

Estou com uma grande dúvida sobre a implementação do conceito de busca em profundidade e busca em largura.

Sei que o mesmo é aplicado sobre arvores porém, como fazer para representar o grafo em árvore, desculpem a ignorância, mas não consegui fazer isso.

Se houver como exemplificar para mim. Não estou pedindo o algoritmo pronto, só quero entender o conceito.
claudneto
JavaEvangelist
[Avatar]

Membro desde: 12/08/2008 15:09:47
Mensagens: 490
Localização: Mogi das Cruzes
Offline

Se isso for nubice...eu sou noob tbm...pq eu não entendi nem o que vc quer dizer!

Mas td bem...alguem vai te ajudar!



UsuarioGUJ us = new UsuarioGUJ();
if (us.visitar(Use a porra do Google)) {
us.sendString("Eu não mando mensagens sem pesquisar!");
else {
us.sendString("Eu mando mensagens sem pesquisar!");
}
[Email] [MSN]
ViniGodoy
Moderador
[Avatar]

Membro desde: 11/12/2006 08:22:01
Mensagens: 25339
Localização: Curitiba/PR
Offline

Primeiro de tudo, toda árvore é um grafo.

Existem várias formas de representar árvores:
1. Através de listas de adjacencia: Essa é uma forma comum para se representar grafos, de uma maneira geral. Cada nó possui uma lista, dizendo em que nós está ligado.
2. Através de uma matriz de adjacência: Faz-se uma matriz, NxN onde N é o número de nós. Na interseção dos nós está a informação sobre a interligação daqueles dois nós.
3. No caso específico de árvores, pode-se representa-las através do padrão de projetos composite: Ou seja, cria-se uma interface. Dessa interface surgem uma classe para o nó e outra classe que é uma lista de nós. Note que essa outra classe também implementa a interface do nó e, portanto, podemos inserir listas dentro de listas.
4. Pode-se usar uma estrutura onde cada nós possui o link para dois outros nós, situados a esquerda e a direita dele. Nesse caso, teríamos a estrutura de árvore binária. Os nós a esquerda seriam "menores" que o nó em questão e os da direita "maiores". A vantagem desse tipo de estrutura é que é que os elementos estão sempre ordenados, com um custo muito baixo.

Qual dessas estruturas escolher varia muito de acordo com que tipo de aplicação você vai desenvolver.

@ViniGodoy - Lattes

Novo no fórum? Leia nosso How to.

Ponto V! - Desenvolvimento de Jogos Profissional - @Pontov - Facebook
Projeto Towel - Swing de uma forma inteligente (Novo lar do ObjectTableModel e do Auto-Filtro).

Ei... você está usando DefaultTableModel no seu projeto??
Não faça isso! Veja: http://www.guj.com.br/posts/list/15/199067.java#1001295
[WWW]
ViniGodoy
Moderador
[Avatar]

Membro desde: 11/12/2006 08:22:01
Mensagens: 25339
Localização: Curitiba/PR
Offline

claudneto wrote:Se isso for nubice...eu sou noob tbm...pq eu não entendi nem o que vc quer dizer!

Mas td bem...alguem vai te ajudar!


Que tipo de mensagem é essa? Só para aumentar o seu "post count"?

Aliás, pra que esse contador aí na sua assinatura? Se ainda fosse um nível de personagem num MMORPG eu até entenderia, mas ter mais mensagens que alguém aqui no fórum não te dá vantagem nenhuma...

This message was edited 1 time. Last update was at 24/09/2008 12:27:47


@ViniGodoy - Lattes

Novo no fórum? Leia nosso How to.

Ponto V! - Desenvolvimento de Jogos Profissional - @Pontov - Facebook
Projeto Towel - Swing de uma forma inteligente (Novo lar do ObjectTableModel e do Auto-Filtro).

Ei... você está usando DefaultTableModel no seu projeto??
Não faça isso! Veja: http://www.guj.com.br/posts/list/15/199067.java#1001295
[WWW]
Thiago Dantas
Thread.start()

Membro desde: 08/03/2007 18:12:12
Mensagens: 44
Offline

entendi tudo quanto vc escreveu. Aliás isso somou com tudo que já tinha pesquisado vlw... Dessas aplicações implementei o conceito de lista de adjacência. Vou mostrar as classes já criadas:

Obs.: O código foi escrito em C#, mas vou migra-lo para Java



Essa é classe que representa o nó a ligação com seus adjacentes.

Pra implementação ( atividade da faculdade ), utilizamos um grafo disponibilizado pelo professor. a classe de teste seria algo como:



A pergunta é: Nessa estrutura é possível aplicar a busca por profundidade e por largura. Se sim, como seria? um exemplo

carutcho
HelloWorld

Membro desde: 11/09/2008 16:18:35
Mensagens: 12
Offline

ViniGodboy:

Tipo, interessante esse assunto, eu sinceramente nunca tinha ouvido falar, claro q não estou no java a muito tempo, mas acho que quanto mais conceitos eu pegar e coisas eu entender melhor, portanto.
Poderia me dizer na pratica eu usaria essa métodologia ? Poderia me dizer alguma coisa q eu pudesse me informar melhor sobre isso ?


Absss
[MSN]
ViniGodoy
Moderador
[Avatar]

Membro desde: 11/12/2006 08:22:01
Mensagens: 25339
Localização: Curitiba/PR
Offline

Então.

Para a busca em largura, vc pega o nó raiz e verifica se ele é o que contém a resposta. Se for, ok. Se não for, vc abrirá o primeiro nó da lista de adjacência e verificará. Se esse nó não contiver a resposta, vc abre o segundo nó da lista de adjacência. E assim vai, até acabar a lista.

Só quando a lista acabar, vc inicia a busca pela lista de adjacência dos filhos.


No caso da busca em profundidade, vc pega o nó raiz e verifica se ele contém a resposta. Se ele não contiver, vá até o primeiro nó da lista de adjacência e verifique se está lá. Se não estiver lá, abra o primeiro nó da lista de adjacência do filho e veja se está lá também... e vá assim até chegar numa folha. Quando chegar na folha, volte um nível e pegue o nó vizinho.


Entendeu? Se for preciso eu ponho um desenho e um exemplo.

@ViniGodoy - Lattes

Novo no fórum? Leia nosso How to.

Ponto V! - Desenvolvimento de Jogos Profissional - @Pontov - Facebook
Projeto Towel - Swing de uma forma inteligente (Novo lar do ObjectTableModel e do Auto-Filtro).

Ei... você está usando DefaultTableModel no seu projeto??
Não faça isso! Veja: http://www.guj.com.br/posts/list/15/199067.java#1001295
[WWW]
claudneto
JavaEvangelist
[Avatar]

Membro desde: 12/08/2008 15:09:47
Mensagens: 490
Localização: Mogi das Cruzes
Offline

ViniGodoy wrote:
claudneto wrote:Se isso for nubice...eu sou noob tbm...pq eu não entendi nem o que vc quer dizer!

Mas td bem...alguem vai te ajudar!


Que tipo de mensagem é essa? Só para aumentar o seu "post count"?

Aliás, pra que esse contador aí na sua assinatura? Se ainda fosse um nível de personagem num MMORPG eu até entenderia, mas ter mais mensagens que alguém aqui no fórum não te dá vantagem nenhuma...


Ele disse que talvez fosse ignorância...eu disse que tbm não entendi! Apenas isso...

Não quero ter vantagem por ter mais mensagens...e outra coisa...a assinatura é minha...coloco o que quiser! Vc não acha?

A quantidade de mensagens (ao meu ver) é o quanto eu ajudo ou sou ajudado pelos usuarios do GUJ...e isso pra mim é importante...pq eu postei mais ajudas do que pedidos de ajudas...isso pra mim é bom...

Agora não é só pq vc participa do fórum a mais tempo que eu, ou tem mais mensagens, ou sabe mais de Java que vc pode vir falando da assinatura dos outros! Cada um cuida da sua vida.

Se eu quiser colocar msn errado aqui eu coloco, uma foto que não seja eu, eu coloco!

Enquanto eu não tiver ofendendo alguem...eu posso colocar qualquer coisa na assinatura!



UsuarioGUJ us = new UsuarioGUJ();
if (us.visitar(Use a porra do Google)) {
us.sendString("Eu não mando mensagens sem pesquisar!");
else {
us.sendString("Eu mando mensagens sem pesquisar!");
}
[Email] [MSN]
Thiago Dantas
Thread.start()

Membro desde: 08/03/2007 18:12:12
Mensagens: 44
Offline

entendi sim cara... vlw mesmo... claro q fosse possível e se vc não achar é claro q seria abuso, gostaria de visualizar o exemplo do código, para ter uma idéia de implementação.

Obs.: Please


Vlw...
ViniGodoy
Moderador
[Avatar]

Membro desde: 11/12/2006 08:22:01
Mensagens: 25339
Localização: Curitiba/PR
Offline

Esqueci de perguntar, para quê é o grafo?
Dependendo do tipo de grafo, você poderia usar a busca heurística que é muito mais rápida.


carutcho, vini "godboy" foi ótima. heehhhehehe
Você pode pesquisar mais sobre essa técnica no livro "Programming Game AI by Example" do Mat Buckland. Uma das melhores introduções de IA que eu já vi. Se quiser ir bem a fundo e estiver disposto a encarar um linguajar mais acadêmico, procure o livro "Inteligência Artificial" do Norvig.



Calma claudneto, não tô te xingando não. Eu só não entendi muito o porque do contador. Como você falou, a assinatura é sua, você faz dela o que quiser.

Só discordo uma coisa de vc: Todo mundo pode falar da assinatura de todo mundo. Esse é um fórum e um país livre, e temos liberdade de expressão. Se você publicou, eu e outros usuários lêem, portanto, sua assinatura passou a fazer parte da nossa vida também, e podemos falar dela.

Aliás, vc também pode falar da minha e se quiser achar ridículo eu fazer propaganda do meu próprio blog, pode achar. =D

Mas não se ofenda. O texto não dá nem sempre expressa a entonação de quem escreve, e temos a tendência de achar que é mais agressivo do que realmente é. Não foi a intenção de ofender, foi só curiosidade mesmo.

@ViniGodoy - Lattes

Novo no fórum? Leia nosso How to.

Ponto V! - Desenvolvimento de Jogos Profissional - @Pontov - Facebook
Projeto Towel - Swing de uma forma inteligente (Novo lar do ObjectTableModel e do Auto-Filtro).

Ei... você está usando DefaultTableModel no seu projeto??
Não faça isso! Veja: http://www.guj.com.br/posts/list/15/199067.java#1001295
[WWW]
ViniGodoy
Moderador
[Avatar]

Membro desde: 11/12/2006 08:22:01
Mensagens: 25339
Localização: Curitiba/PR
Offline

Há exemplos de código na wiki americana:
http://en.wikipedia.org/wiki/Breadth-first_search (largura)
http://en.wikipedia.org/wiki/Depth-first_search (profundidade)

@ViniGodoy - Lattes

Novo no fórum? Leia nosso How to.

Ponto V! - Desenvolvimento de Jogos Profissional - @Pontov - Facebook
Projeto Towel - Swing de uma forma inteligente (Novo lar do ObjectTableModel e do Auto-Filtro).

Ei... você está usando DefaultTableModel no seu projeto??
Não faça isso! Veja: http://www.guj.com.br/posts/list/15/199067.java#1001295
[WWW]
Thiago Dantas
Thread.start()

Membro desde: 08/03/2007 18:12:12
Mensagens: 44
Offline

vlw Brother... sério mesmo... vlw mesmo...
carutcho
HelloWorld

Membro desde: 11/09/2008 16:18:35
Mensagens: 12
Offline

Grande ViniGogoboy rsssss brincadeira.

Saca só, valeus pelas dicas e eu adiconei aqui no meu caderinho "futuro mago do Java rs".
Parece piada ou loucura mas eu resolvi por na minha cabeça que eu queria ganhar dinheiro e que queria ter novos desafios na vida, evoluir bem mais do que eu ja consegui chegar , então achei que deveria estudar java e tenho me dedicado mt, pq até então eu programava só para a web (php, javascript etc).

Eu pequisei e achei muita coisa legal no java , porém sei que ainda não vi nem 1/3.
Por exemplo, com relação a IA, com java eu posso entrar em que tipo de mercado ? apenas com mobile e jogos ? a seu ver qual é o maior patamar de java?
Pq tipo, eu tenho procurado atualmente mirar no mais alto q eu consigo e se eu acertar mais embaixo um pouco, é lucro endente ? Eu estou procurando ver qual área do java tem se valorizado mais, vendo qual delas que eu mais gosto e principalmente procurando ver a tendência do mercado.
Então estou me desafiado para ver até onde eu consigo chegar.

Obrigado pela referencia, vou procurar mais sobre o assunto.


Absss
[MSN]
Andre Brito
JWizard

Membro desde: 21/07/2007 17:44:31
Mensagens: 2485
Localização: Paraná
Offline

ViniGodoy wrote:Esqueci de perguntar, para quê é o grafo?
Dependendo do tipo de grafo, você poderia usar a busca heurística que é muito mais rápida.


Grande ViniGodoy.
Busca heurística é mais rápida?? Tem certeza cara? Porque nas competições nós usamos sempre em profundidade ou em largura (depende do problema, claro). Eu sempre achei que eram as mais rápidas... E ainda são utilizadas em IA nas buscas, né? Você poderia me explicar?

claudneto,
Vai com calma cara. Ninguém tá aqui pra arrumar treta com ninguém. Muito pelo contrário, quanto mais ajudar e conversar com o pessoal, mais pessoas você conhece pra arranjar um emprego no futuro. Além de que, os spammers decentes aqui do GUJ são gente finíssimas.
Não quero defender ninguém, mas o ViniGodoy é um cara que você deve ter como amigo. Procure (usando a Busca) pelo nick dele. Você só encontra agradecimentos. Ps.: eu também concordo com ele da sua assinatura. Pensei a mesma coisa quando vi ela pela primeira vez. Acredite, eu tenho 900 mensagens, mas não ajudei o povo nem um décimo do que o VG ajudou.

Abraço.

[editado]
cartucho, (deixa eu me intrometer )
Você pode entrar no mercado de I.A. com qualquer linguagem.
Java oferece algumas vantagens (que eu nunca usei porque gosto de fazer na mão), como alguns frameworks pra Redes Neurais Artificias e afins. Se você quer ir pra área de jogos usando Java e I.A., beleza... agora, quer desenvolver jogos usando I.A. não consigo te recomendar Java, mas sim C++. O blog do ViniGodoy e dos comparsas dele são excelentes se você quer desenvolver jogos em C++. Não estou falando que se você quer desenvolver jogos fuja de Java. Muito pelo contrário... se desafie pra lançar alguma coisa no mercado pra causa impacto no pessoal e pra eles dizerem "sai coisa muito boa de Java para jogos" (veja JMonkeyEngine).
Quer fazer "robôs" físicos? Até pode usar Java (J2ME). Procure por Java Mars (aquele treco que foi pra marte, DISQUE foi feito em Java). O que eu estou querendo dizer é que I.A. e Algoritmos em geral independem da linguagem. A aplicação é que pode "forçar" você a usar alguma outra linguagem. Vejo muita gente falando mal de Java. Ingore essas pessoas, porque elas geralmente querem colocar minhocas na sua cabeça. Tenha opinião própria
Eu acho que Java é bastante forte em Web e sistemas empresariais. Eu nunca mais espero desenvolver aplicações usando Swing e Java. Então o nível meio que já parte para Java com Web e coisas a fins. RIAs também estão forte no mercado (eu acho pelo menos)... sem contar que as interfaces gráficas de RIAs e coisas do tipo são muito bonitas.

Abraço

ps.: veja esse link:http://www.guj.com.br/posts/list/53776.java
[/editado]

This message was edited 3 times. Last update was at 24/09/2008 17:22:51


Como organizar o GUJ.
Meu Twitter.
Meu blog.
Future proofing means making code easy to change, not trying to anticipate every possible way your code might need to change.
[WWW]
carutcho
HelloWorld

Membro desde: 11/09/2008 16:18:35
Mensagens: 12
Offline

Grannnde André Brito

Po cara, uma coisa q eu tenho q concordar com vc é que a maioria da galera aqui do forum é mt legal mesmo, eu infelizmente não tenho como trocar tal conhecimento com a galera ainda, to engatinhando no java, sou um cara que possui uma boa lógica, entendo conceitos, programo a um tempo e tals mas ainda não tenho a pratica com java, portanto pergunto mais e fico mais na filosofia q ajudando, porém pretendo daqui a algum tempo ja estar trabalhando com java e contribuindo com esse mundo que é mt legal.

Tipo, o engraçado de tudo André , é que realmente vejo muita gente reclamando do java, muita gente dizendo que o java é mt complicado, que o java da muita volta para fazer coisas simples, que tem mt tecnologia de web que são mais simples que o java e que isso e aquilo. Eu sinceramente faço como vc fala
Vejo muita gente falando mal de Java. Ingore essas pessoas, porque elas geralmente querem colocar minhocas na sua cabeça. Tenha opinião própria
.
Eu atualmente tenho perguntado mt e pesquisado um bucado sobre tecnologia, eu até então no inicio estava desnorteado, não sabia pra que linguagem correr ja que php ganhava pouco e eu não tinha mais desafios, então arrisquei dar o chute no java, e me emburaquei num curso no Infent "curso no RJ". Cara na boa, me fascinei pela linguagem, tenho estudado bastante ela e pesquisando qual é a tendência dela no mercado, fico em dúvida se continuo no ramo de web q sempre foi meu foco ou se eu caio para mobile que eu acredito cegamente que é a proxima tendência do mercado no futuro, ja que não é atoa que google, microsft e outras empresas tem disputado mt esse mercado, e não é por menos, pq tem mais pessoas com celulares que com computadores, ou quem sabe conseguir arrumar uma solução inovadora que junte as 2 tecnologias.

Bem basicamente é isso, eu perguntei sobre a IA pq eu sei que é um assunto bem interessante, mas esse acho que tem que dedicar MT, portem tenho q ver se eu gosto para poder me dedicar.

Bem rsrsrs, chega de escrever, valeu pela atenção de vo6 e pelas dicas, pode ter certeza que me ajudaram bastante.

[editando]

Mt maneiro o link q vc passou hein, e o joguinho tb é show de bola, vou procurar dar uma olhada com mais calma.. valewsss

Abssss

This message was edited 1 time. Last update was at 24/09/2008 22:11:41

[MSN]
 
Índice dos Fóruns » Java Básico
Ir para:   
Powered by JForum 2.1.8 © JForum Team