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.
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!
Primeiro de tudo, toda árvore é um grafo.
Existem várias formas de representar árvores:
Qual dessas estruturas escolher varia muito de acordo com que tipo de aplicação você vai desenvolver.
[quote=claudneto]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![/quote]
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…
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
using System;
using System.Collections.Generic;
namespace Faculdade.IA.BuscaProfundidade
{
public class No
{
#region Atributos
private string valor;
private bool visitado;
private Queue<No> adjacentes;
#endregion
#region Construtores
public No()
{
visitado = false;
adjacentes = new Queue<No>();
}//-- Fim do construtor
#endregion
#region Propriedades
public string Valor
{
get { return valor; }
set { valor = value; }
}//-- Fim da propriedade Valor
public bool Visitado
{
get { return visitado; }
set { visitado = value; }
}//-- Fim da propriedade Visitado
public Queue<No> Adjacentes
{
get { return adjacentes; }
}//-- Fim da propriedade Adjacentes
#endregion
#region Métodos
public void SetListNo( No no )
{
adjacentes.Enqueue( no );
}//-- Fim do método SetListNo
#endregion
}//-- Fim da classe No
}//-- Fim da namespace Faculdade.IA.BuscaProfundidadeEssa é 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:
using System;
using System.Collections.Generic;
namespace Faculdade.IA.BuscaProfundidade
{
public class Program
{
public static void Main( string[] args )
{
//-- Criação do objetos Nodos que guardam referênicas para seu adjacentes
No no1 = new No();
No no2 = new No();
No no3 = new No();
No no4 = new No();
No no5 = new No();
No no6 = new No();
No no7 = new No();
No no8 = new No();
//-- Adicionando Valores para os nodos
no1.Valor = "1";
no2.Valor = "2";
no3.Valor = "3";
no4.Valor = "4";
no5.Valor = "5";
no6.Valor = "6";
no7.Valor = "7";
no8.Valor = "8";
//-- Criando a árvore
no1.SetListNo(no2);
no1.SetListNo(no5);
no2.SetListNo(no1);
no2.SetListNo(no3);
no2.SetListNo(no4);
no3.SetListNo(no2);
no3.SetListNo(no4);
no3.SetListNo(no6);
no4.SetListNo(no2);
no4.SetListNo(no3);
no5.SetListNo(no1);
no5.SetListNo(no7);
no6.SetListNo(no3);
no6.SetListNo(no7);
no7.SetListNo(no5);
no7.SetListNo(no6);
no7.SetListNo(no8);
no8.SetListNo(no7);
}//-- Fim do método Main
}//-- Fim da classe Program
}//-- Fim do namespace Faculdade.IA.BuscaProfundidadeA pergunta é: Nessa estrutura é possível aplicar a busca por profundidade e por largura. Se sim, como seria? um exemplo
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
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.
[quote=ViniGodoy][quote=claudneto]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![/quote]
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…[/quote]
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!
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…
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.
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)
vlw Brother… sério mesmo… vlw mesmo…
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
[quote=ViniGodoy]Esqueci de perguntar, para quê é o grafo?
Dependendo do tipo de grafo, você poderia usar a busca heurística que é muito mais rápida.
[/quote]
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]
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 [quote] 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 [/quote].
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
[quote=Andre Brito]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?[/quote]
Desde que seja possível usar, a busca heurística é muitíssimo mais rápida. Isso por que a heurística guia a função diretamente para o resultado. Baixe os exemplos do buckland nesse site aqui:
http://www.wordware.com/files/ai/files/Buckland_AIExecutables.zip
E veja os exemplos do capítulo 5. Ali tem um programa que compara a busca em profundidade, largura, Dijkstra e heurística (A*). Você vai ver como o A* é rápido. Só perde para a busca em profundidade caso, por uma obra do acaso, o destino está no caminho da busca do algoritmo. Mas não podemos contar com isso sempre, certo?
Valeu.
[quote][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).
[/quote]
Cartucho, se você tem ambição em entrar no mercado de jogos profissional, por exemplo, ser contratado na EA, Ubisoft, etc, o caminho hoje é o C++. Se seu desejo é só fazer joguinhos por hobby, pode escolher até o python (aliás, a Pygame também é muito bem falada, mesmo para 3D). O negócio é começar por algum lugar. Tem muita teoria legal para se aprender.
Falou e disse. A maior parte da falação de Java são mitos, a maioria infundados, exageros ou pré-conceitos vindos do Java 1.1 (que tinha mesmo seus problemas, antes da HotSpot VM).
Esses links também valem a pena:
http://www.guj.com.br/posts/list/69961.java
http://www.guj.com.br/posts/list/48344.java
http://www.cokeandcode.com/tutorials
Olá.
Vini esses executáveis do livro “Programming Game AI by Example”, o cara aprende a fazer todos seguindo o livro?
Poxa achei interessantíssimo, vou ver se acho o livro pra comprar.
Valeu !
Sim. Aprende.
Recomendadíssimo o livro.
Eu comprei o meu na Amazon, valeu cada centavo.
Ele dá uma introdução prática aos principais tópicos da IA para jogos.
Galera… eu to querendo aprender essa parada tbm, mas empaquei com uma dúvida meio básica… mais ou menos a que o Thiago Dantas teve, mas ele sacou logo e eu não…
Tipo: quando eu implemento o grafo, eu quero fazer uma busca em largura, certo? Eu sei que eu tenho que escolher um vértice, e visitar os adjacentes.
Segundo o Cormen, o vértice que eu estou visitando, ficaria cinza caso tivesse outros adjacentes e preto caso não tivesse mais filhos (e no começo todos brancos)… Eu sei que ele quis dizer: “Bota um boolean na parada…”, mas minha humilde pergunta é: COMO?
Tipo, eu tô ligado mais ou menos no algoritmo, mas na hora de implementar eu não tô conseguindo… então vão as perguntas…
1ª Eu preciso criar uma classe pro grafo?
Tipo:
[code]class Grafo {
Lista[] adj;
public Grafo(int i) {
this.adj = new Lista[i];
for(int j = 0; j < i; j++) {
this.adj[i] = new Lista();
}
}
}[/code]
2ª Onde diabos eu coloco um boolean pra marcar q eu visitei o vértice? 
Na classe nó da lista?
p.s.: ViniGogoboy foi muito bom… hehehe brincadeira…
Abraço a todos!!
[quote=Thiago Dantas]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
using System;
using System.Collections.Generic;
namespace Faculdade.IA.BuscaProfundidade
{
public class No
{
#region Atributos
private string valor;
private bool visitado;
private Queue<No> adjacentes;
#endregion
#region Construtores
public No()
{
visitado = false;
adjacentes = new Queue<No>();
}//-- Fim do construtor
#endregion
#region Propriedades
public string Valor
{
get { return valor; }
set { valor = value; }
}//-- Fim da propriedade Valor
public bool Visitado
{
get { return visitado; }
set { visitado = value; }
}//-- Fim da propriedade Visitado
public Queue<No> Adjacentes
{
get { return adjacentes; }
}//-- Fim da propriedade Adjacentes
#endregion
#region Métodos
public void SetListNo( No no )
{
adjacentes.Enqueue( no );
}//-- Fim do método SetListNo
#endregion
}//-- Fim da classe No
}//-- Fim da namespace Faculdade.IA.BuscaProfundidadeEssa é 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:
using System;
using System.Collections.Generic;
namespace Faculdade.IA.BuscaProfundidade
{
public class Program
{
public static void Main( string[] args )
{
//-- Criação do objetos Nodos que guardam referênicas para seu adjacentes
No no1 = new No();
No no2 = new No();
No no3 = new No();
No no4 = new No();
No no5 = new No();
No no6 = new No();
No no7 = new No();
No no8 = new No();
//-- Adicionando Valores para os nodos
no1.Valor = "1";
no2.Valor = "2";
no3.Valor = "3";
no4.Valor = "4";
no5.Valor = "5";
no6.Valor = "6";
no7.Valor = "7";
no8.Valor = "8";
//-- Criando a árvore
no1.SetListNo(no2);
no1.SetListNo(no5);
no2.SetListNo(no1);
no2.SetListNo(no3);
no2.SetListNo(no4);
no3.SetListNo(no2);
no3.SetListNo(no4);
no3.SetListNo(no6);
no4.SetListNo(no2);
no4.SetListNo(no3);
no5.SetListNo(no1);
no5.SetListNo(no7);
no6.SetListNo(no3);
no6.SetListNo(no7);
no7.SetListNo(no5);
no7.SetListNo(no6);
no7.SetListNo(no8);
no8.SetListNo(no7);
}//-- Fim do método Main
}//-- Fim da classe Program
}//-- Fim do namespace Faculdade.IA.BuscaProfundidadeA pergunta é: Nessa estrutura é possível aplicar a busca por profundidade e por largura. Se sim, como seria? um exemplo
[/quote]
Segue o código em JAVA, não sei se fiz o Parse da melhor maneira possível (sou novo em Java):
package Arvore;
class Queue<E> {
private E data;
public void add (E x) {
data = x;
}
public boolean isEmpty() {
return data == null;
}
public E pop() {
return data;
}
}
public class BuscaProfundidade {
private String valor;
private boolean visitado;
private Queue<BuscaProfundidade> adjacentes;
public BuscaProfundidade() {
visitado = false;
adjacentes = new Queue<BuscaProfundidade>();
}
public void Valor(String v) {
valor = v;
}
public String Valor() {
return valor;
}
public void Visitado(boolean v) {
visitado = v;
}
public boolean Visitado() {
return visitado;
}
public Queue<BuscaProfundidade> Adjacentes() {
return adjacentes;
}
public void SetListNo(BuscaProfundidade no) {
adjacentes.add(no);
}
}
private static void estudoBuscaProfundidade(){
// -- Criação do objetos Nodos que guardam referênicas para seus adjacentes
BuscaProfundidade no1 = new BuscaProfundidade();
BuscaProfundidade no2 = new BuscaProfundidade();
BuscaProfundidade no3 = new BuscaProfundidade();
BuscaProfundidade no4 = new BuscaProfundidade();
BuscaProfundidade no5 = new BuscaProfundidade();
BuscaProfundidade no6 = new BuscaProfundidade();
BuscaProfundidade no7 = new BuscaProfundidade();
BuscaProfundidade no8 = new BuscaProfundidade();
// -- Adicionando Valores para os nodos
no1.Valor("1");
no2.Valor("2");
no3.Valor("3");
no4.Valor("4");
no5.Valor("5");
no6.Valor("6");
no7.Valor("7");
no8.Valor("8");
// -- Criando a árvore
no1.SetListNo(no2);
no1.SetListNo(no5);
no2.SetListNo(no1);
no2.SetListNo(no3);
no2.SetListNo(no4);
no3.SetListNo(no2);
no3.SetListNo(no4);
no3.SetListNo(no6);
no4.SetListNo(no2);
no4.SetListNo(no3);
no5.SetListNo(no1);
no5.SetListNo(no7);
no6.SetListNo(no3);
no6.SetListNo(no7);
no7.SetListNo(no5);
no7.SetListNo(no6);
no7.SetListNo(no8);
no8.SetListNo(no7);
}Att,