Bom dia pessoal
tenho um trabalho da facul pra fazer um algoritmo para encontrar um caminho entre dois pontos. Fiz ele utilizando lista, mas agora o professor pediu pra que encontre o melhor caminho entre esses 2 pontos, os grafos são não valorados. Alguém ai sabe se tem como fazer isso por listas? Ou uma idéia inicial que eu deva seguir?
Dúvida Grafos
A
12 Respostas
mostra ae pra gente o q vc fez! fiquei interessado em ver como vc fez o 1º
vlw
A
public class Caminho {
private boolean temSaida = true;
private boolean caminhoEncontrado;
private Pilha caminho;
public Caminho(){
caminho = new Pilha();
caminhoEncontrado = false;
}
public void insereNoCaminho(Vertice v){
caminho.push(v);
caminhoEncontrado = true;
System.out.println("Caminho encontrado \n"+ toString());
System.exit(0);
}
//procura um caminho entre os 2 vertices
public void buscaCaminho(Grafo g, Vertice origem, Vertice destino){
//coloca o vertice na pilha q representa o caminho
caminho.push(origem);
origem.setVisited(true);
temSaida = origem.hasArestas();
if(temSaida){
for(Aresta a: origem.getArestas()){
if(!a.isVisited()){
a.setVisited(true);
temSaida = true;
System.out.print(a.getFirst()+" - ");
System.out.println(a.getLast());
if(a.getLast().equals(destino)){
insereNoCaminho(a.getLast());
return;
}else if(a.getFirst().equals(destino)){
insereNoCaminho(a.getFirst());
return;
}
}
}
}
else{
if (caminho.size() >1 ){
System.err.println("volta");
caminho.pop();
temSaida = true;
buscaCaminho(g, caminho.pop(), destino);
}
}
for(Vertice v: origem.getAdjacentes()){
if(!v.isVisited()) buscaCaminho(g, v, destino);
}
if (!caminhoEncontrado) {
System.out.println("Caminho não Encontrado");
System.exit(0);
}
}
public String toString(){
return caminho.toString();
}
}
import java.util.LinkedList;
public class Vertice {
private LinkedList<Vertice> adjacentes;
private String nome;
private boolean visited;
private LinkedList<Aresta> arestas;
public Vertice(String nome){
this.nome = nome;
visited = false;
adjacentes = new LinkedList<Vertice>();
arestas = new LinkedList<Aresta>();
}
public boolean hasArestas(){
for (Aresta a: arestas){
System.out.println(a + " = " +a.isVisited());
if(!a.isVisited())
return true;
}
return false;
}
public void addAresta(Aresta a){
arestas.add(a);
}
public void addAdjacente(Vertice adjacente){
adjacentes.add(adjacente);
}
public boolean isVisited(){
return visited;
}
public boolean equals(Vertice v){
return nome.equals(v.getNome());
}
//verifica se existem vertices adjacentes q ainda nao foram visitados
public boolean hasNoVisited(){
for (Vertice v: adjacentes){
if(v.visited == false)
return true;
}
return false;
}
public String toString(){
return nome;
}
public LinkedList<Vertice> getAdjacentes() {
return adjacentes;
}
public void setAdjacentes(LinkedList<Vertice> adjacentes) {
this.adjacentes = adjacentes;
}
public String getNome() {
return nome;
}
public void setNome(String nome) {
this.nome = nome;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public LinkedList<Aresta> getArestas() {
return arestas;
}
public void setArestas(LinkedList<Aresta> arestas) {
this.arestas = arestas;
}
}
só que ainda ta dando uns bugs, tipo
tem caminho que ele encontra num sentido, mas no sentido contrário não encontra...
e ainda não consegui resolver isso.
Olá tente buscar algoritmo de busca em profundidade e busca em largura… Eu os vi na disciplina de análise de algoritmo…
A
DHS
eu fiz esse ai baseado num algoritmo de busca em profundidade
Da uma olhada no “caxeiro viajante”.
Ola Angelo
Voce implentou a busca por profundidade. Ela acha um caminho, mas nao necessariamente o menor caminho. Para um grafo sem peso nas arestas, voce pode usar a busca em largura, ela garante achar o menor caminho (basta voce usar uma fila, ir visitando os filhos do no atual e adicionando-os no final da fila, e ai pega o proximo pra visitar do comeco da fila)
Considerando que voce tem os vertices orgiem e destino, ficaria algo como:
LinkedList<Vertice> fila = new LinkedList<Vertice>();
fila.add(origem);
Vertice atual = origem;
while(atual != destino) {
for(Aresta a: atual.getArestas()){
if (!a.isVisited()){
a.setVisited(true);
fila.add(a.getLast());
}
atual = fila.removeFirst(); // cuidado! pode estar vazio se nao houver caminho
}
Pra voce pegar o caminho, mantenha em uma estrutura de dados paralela com qual aresta voce chegou a cada no, ai é so percorrer inversamente.
A
Jauns
acho que o problema do caixeiro viajante não se aplica aqui porque nao vou utilizar arestas valoradas
Paulo Silveira
vou tentar ver se da certo
A
tentei fazer desse jeito:
LinkedList<Vertice> fila = new LinkedList<Vertice>();
LinkedList<Vertice> caminho = new LinkedList<Vertice>();
fila.add(origem);
caminho.add(origem);
Vertice atual = origem;
caminhoEncontrado = true;
while(!atual.equals(destino)){
caminho.add(atual);
if(fila.isEmpty()){
caminhoEncontrado = false;
break;
}else{
for(Vertice v: atual.getAdjacentes()){
if (!v.isVisited()){
v.setVisited(true);
fila.addLast(v);
System.out.println("insere vértice" + v);
}
}
atual = fila.removeFirst();
System.out.println("remove vértice" + atual);
}
}
if(caminhoEncontrado)
System.out.println("Caminho Encontrado\n" + toString());
else
System.out.println("Caminho não encontrado");
mas ainda está bugando
o erro esta aqui:
caminho.add(atual);
nao é para adicionar todos que voce visita!!!
depois que achou o caminho, precisa fazer o caminho de volta. pra isso, toda vez que visita um vertice, precisa anotar com qual aresta voce chegou al (vai precisar de um aresta.setUsedForBestPath(true) ou guardar uma estrutura de dados paralela (mais elegante)).
A
bom, o código ficou assim:
for(Vertice v: g.getVertices())
v.setVisited(false);
if(origem == destino) return 0;
caminho = new LinkedList<Vertice>();
fila = new LinkedList<Vertice>();
fila.add(origem);
Vertice atual = origem;
caminhoEncontrado = true;
while(!atual.equals(destino)){
if(fila.isEmpty()){
caminhoEncontrado = false;
}else{
for(Vertice v: atual.getAdjacentes()){
if (!v.isVisited() || atual.getArestas().size() == 1){
v.setVisited(true);
fila.addLast(v);
for(Aresta a:atual.getArestas()){
if(a.getLast().equals(v) || a.getFirst().equals(v))
v.setCameFrom(a);
}
}
}
atual = fila.removeFirst();
}
}
/*
* faz o caminho de volta para armazenar o caminho em uma lista
*/
if(caminhoEncontrado){
arestas = new LinkedList<Aresta>();
atual = destino;
while(!atual.equals(origem)){
caminho.addFirst(atual);
Aresta a = atual.getCameFrom();
arestas.addFirst(a);
atual = a.getVizinho(atual);
}
caminho.addFirst(origem);
System.out.println("Caminho Encontrado\n" + caminho.toString());
return arestas.size();
}
else {
System.out.println("Caminho não encontrado");
return Integer.MAX_VALUE;
}
ele encontra o caminho, porém dependendo do vértice na hora de fazer o caminho de volta ele está dando
java.lang.OutOfMemoryError: Java heap spacejava.lang.OutOfMemoryError: Java heap space
na linha arestas.addFirst(a);
A
up
A
eh o seguinte
agora preciso achar o melhor caminho com arestas valoradas
fiz e estava funcionado
testei um caminho e encontrou o melhor caminho, mais invertendo a ordem dos vertices ele encontrou um otro caminho
segue ai o codigo
public class Caminho {
private Vertice destino;
private int custo;
private LinkedList<Vertice> vertices;
public Caminho(Vertice inicial){
vertices = new LinkedList<Vertice>();
destino = inicial;
custo = 0;
vertices.add(inicial);
}
public Caminho(Caminho origem, Aresta aresta) {
vertices = (LinkedList<Vertice>) origem.getVertices().clone();
destino = aresta.getVizinho(vertices.getLast());
custo = origem.getDestino().getDistanciaDaOrigem() + aresta.getPeso();
vertices.add(destino);
vertices.getLast().setDistanciaDaOrigem(custo);
System.out.println("novo caminho: "+this);
}
}
public class Tabela {
private LinkedList<Caminho> listaCaminhos;
private Caminho menorCaminho;
public Tabela(){
listaCaminhos = new LinkedList<Caminho>();
}
public void buscaCaminho(Vertice origem, Vertice destino){
Vertice atual = origem;
menorCaminho = new Caminho(origem);
do{
adicionaCaminhos(menorCaminho);
menorCaminho = menorCaminho();
if(menorCaminho == null){
System.out.println("Caminho não encontrado");
System.exit(0);
}
System.out.println("menor: "+menorCaminho);
listaCaminhos.remove(menorCaminho);
atual = menorCaminho.getDestino();
}while(atual != destino);
System.out.println(menorCaminho);
}
@SuppressWarnings("unchecked")
public void adicionaCaminhos(Caminho c){
Vertice atual = c.getDestino();
for(Aresta a: atual.getArestas()){
if(!a.isVisited()){
a.setVisited(true);
Caminho caminho = new Caminho(c,a);
if(listaCaminhos.isEmpty())
listaCaminhos.add(caminho);
else{
LinkedList<Caminho> listaAux = (LinkedList<Caminho>) listaCaminhos.clone();
for(Caminho ca: listaCaminhos){
if(ca.getDestino() == caminho.getDestino()){
if(ca.getCusto() > caminho.getCusto()){
listaAux.add(caminho);
break;
}
}else{
listaAux.add(caminho);
System.out.println("Adiciona " + caminho);}
}
listaCaminhos = (LinkedList<Caminho>) listaAux.clone();
}
}
}
}
public Caminho menorCaminho(){
int custo = Integer.MAX_VALUE;
Caminho menor = null;
for(Caminho c: listaCaminhos){
if(c.getCusto() < custo){
menor = c;
custo = c.getCusto();
}
}
return menor;
}
}
Criado 28 de março de 2010
Ultima resposta 16 de abr. de 2010
Respostas 12
Participantes 5
Alura Git Flow: entenda o que é, como e quando utilizar Entenda o que é Git Flow, como funciona seu fluxo com branches como Master, Develop, Feature, Release e Hotfix, além de vantagens e desvantagens.
Casa do Codigo Ontologias e Web Semantica: Do conceito a aplicacao Por Ivam Galvao Filho — Casa do Codigo