ALGORITMO DO MENOR CAMINHO
Caros,
Devido a problemas pessoais e profissionais, confesso que nao estou conseguindo manter o foco no racicionio deste processo afim de resolver este problema como deveria.
Basicamente devo desenvolver um processo de caminhamento dentro dos vertices de um grafo ligados por suas arestas, cada qual com seu devido peso. O problema eh ue realmente nao consigo desenvolver a selecao de caminhos como eh solicitado.
O problema na funcionalidade abaixo (dentro de grafo.cs)
Qualquer ajuda para resolver o problema da seleção será bem vindo, posteriormente vou postar o código fonte ajustado para estudos.
Devido a problemas pessoais e profissionais, confesso que nao estou conseguindo manter o foco no racicionio deste processo afim de resolver este problema como deveria.
Basicamente devo desenvolver um processo de caminhamento dentro dos vertices de um grafo ligados por suas arestas, cada qual com seu devido peso. O problema eh ue realmente nao consigo desenvolver a selecao de caminhos como eh solicitado.
O problema na funcionalidade abaixo (dentro de grafo.cs)
public String EncontrarMenorCaminho(Vertice o, Vertice d)
{
String operacao = [Ô]Registro de operações realizadas:
[Ô];
Caminho caminho = new Caminho();
Caminho caminhomenor = null;
Aresta arestamenor = null;
List<Caminho> caminhos = new List<Caminho>();
List<Vertice> lista_aberta = new List<Vertice>();
List<Vertice> lista_fechada = new List<Vertice>();
operacao += [Ô]Tentando ir de [Ô] + o.Info.ToString() + [Ô] para [Ô] + d.Info.ToString() + [Ô]
[Ô];
lista_aberta.Add(o);
while(lista_aberta.Count > 0)
{
Vertice v = lista_aberta[0];
arestamenor = null;
operacao += [Ô]Visitando [Ô] + v.Info.ToString() + [Ô]
[Ô];
foreach (Vertice vz in EncontrarVizinhos(v))
{
if (!lista_fechada.Contains(vz))
{
Aresta az = GetAresta(v, vz);
if (az != null)
{
//if (arestamenor == null || az.Peso < arestamenor.Peso) arestamenor = az;
if (arestamenor == null) arestamenor = az;
if (az.Peso < arestamenor.Peso)
{
arestamenor = az;
lista_aberta.Add(vz);
}
if (vz.Equals(d))
{
operacao += [Ô] Achei [Ô] + d.Info.ToString() + [Ô], reiniciando caminho
[Ô];
caminhos.Add(caminho);
caminho = new Caminho();
/*
foreach (Aresta a in caminhos[caminhos.Count-1].Arestas)
{
if (!caminho.Arestas.Contains(a)) caminho.AddAresta(a);
}
*/
}
}
operacao += [Ô] Visitando [Ô] + v.Info.ToString() + [Ô] -> [Ô] + vz.Info.ToString() + [Ô] com peso [Ô] + az.Peso.ToString() + [Ô]
[Ô];
}
}
if (arestamenor != null)
{
caminho.AddAresta(arestamenor);
operacao += [Ô] Menor caminho é [Ô] + arestamenor.ToString() + [Ô]
[Ô];
}
lista_aberta.Remove(v);
lista_fechada.Add(v);
}
if (caminhos.Count > 0)
{
foreach (Caminho c in caminhos)
{
if (caminhomenor == null || c.PesoFinal < caminhomenor.PesoFinal) caminhomenor = c;
foreach (Aresta a in c.Arestas)
{
a.Origem.Selecionado = false;
a.Destino.Selecionado = false;
}
}
if (caminhomenor != null)
{
foreach (Aresta a in caminhomenor.Arestas)
{
a.Origem.Selecionado = true;
a.Destino.Selecionado = true;
}
}
}
operacao += [Ô]
[Ô];
operacao += caminhos.Count.ToString() + [Ô] caminhos encontrados:
[Ô];
foreach(Caminho c in caminhos)
{
operacao += [Ô]Caminho [Ô] + caminhos.IndexOf(c).ToString() + [Ô] ([Ô] + c.ToString() + [Ô]) tem peso : [Ô] + c.PesoFinal.ToString() + [Ô]
[Ô];
}
operacao += [Ô]
[Ô];
operacao += [Ô]O menor caminho escolhido foi:
[Ô];
if (caminhomenor == null)
{
operacao += [Ô]Não houve caminho encontrado !!!
[Ô];
}
else
{
operacao += caminhomenor.ToString() + [Ô] com peso [Ô] + caminhomenor.PesoFinal.ToString() + [Ô]
[Ô];
}
DesenharMapa();
return operacao;
}Qualquer ajuda para resolver o problema da seleção será bem vindo, posteriormente vou postar o código fonte ajustado para estudos.
Em anexo vai um código fonte de uma implementação de um path finder (A+ PathFinder)
Talvez refresque a tua memória
No aguardo do fonte para uma melhor ajuda.
Inté+
Talvez refresque a tua memória
No aguardo do fonte para uma melhor ajuda.
Inté+
Oi tudo bem
o caminho é chamado de um arquivo xml, e estruturado pelo um arraylist é isso que esta acima?
o caminho é chamado de um arquivo xml, e estruturado pelo um arraylist é isso que esta acima?
Na verdade eh txt, mas iso nao vem ao caso.
A questao eh a navegacao dos nos dentro de duas estruturas de listas...
A questao eh a navegacao dos nos dentro de duas estruturas de listas...
Glaucio
Confesso que gostei do teu exemplo, mas ele nao eh orientado a objetos no nivel que preciso alem disso esta bem mais complicado do que o meu projeto. Leia meu codigo e veja...
Confesso que gostei do teu exemplo, mas ele nao eh orientado a objetos no nivel que preciso alem disso esta bem mais complicado do que o meu projeto. Leia meu codigo e veja...
Caro web master.
O exemplo pode não estar em OOP como vc quer, mas não e interessante uma analise mais profunda a fim de verificar como ele resolveu alguns problemas?
ai voce adapta pra OOP...
O exemplo pode não estar em OOP como vc quer, mas não e interessante uma analise mais profunda a fim de verificar como ele resolveu alguns problemas?
ai voce adapta pra OOP...
Ja li varioas livros, tudo bem me acho meio lerdo para certas coisas mesmo... 
Os livros que vi encontram menores caminhos no grafo, nao o que va do ponto a para b
aqui esta a versao com matriz...nao eh o que eu queria nao, mas mesmo assim nao resolveu meu problema (
)
Isso ai ta encontrando os [Ô]n[Ô] menores caminhos, nao tem nada a ver com o ir de / para , mas eh o que os livros de algoritmo que encontrei me mostram (e olha, nao foi poucos nao).
Os livros que vi encontram menores caminhos no grafo, nao o que va do ponto a para b
aqui esta a versao com matriz...nao eh o que eu queria nao, mas mesmo assim nao resolveu meu problema (
)
private void Teste2(Vertice o, Vertice d)
{
int vertice_inicial = 0;
long vertice_minimo = 0;
int vertice_proximo = 0;
int vertice_de = Vertices.IndexOf(o);
int vertice_para = Vertices.IndexOf(d);
int tamanho = Vertices.Count;
int[] matriz_vertices = new int[tamanho];
long[,] matriz_global = new long[tamanho, tamanho];
long total = 0;
List<Aresta> selecionados = new List<Aresta>();
for (int i = 0; i < tamanho; i++)
{
for (int j = 0; j < tamanho; j++)
{
matriz_global[i, j] = 0;
}
}
for (int i = 0; i < Arestas.Count; i++)
{
vertice_de = Vertices.IndexOf(Arestas[i].Origem);
vertice_para = Vertices.IndexOf(Arestas[i].Destino);
matriz_global[vertice_de, vertice_para] = EncontrarAresta(Arestas[i].Origem, Arestas[i].Destino).Peso;
matriz_global[vertice_para, vertice_de] = EncontrarAresta(Arestas[i].Origem, Arestas[i].Destino).Peso;
}
for (int i = 0; i < tamanho; i++)
{
matriz_vertices[i] = vertice_inicial;
ZerarMatriz(matriz_global, matriz_vertices[i]);
vertice_minimo = EncontrarArestaMinima(matriz_global, matriz_vertices, out vertice_inicial, ref vertice_proximo);
if (vertice_minimo != 0)
{
total += vertice_minimo;
Aresta tmp = new Aresta();
tmp = EncontrarAresta(Vertices[vertice_proximo], Vertices[vertice_inicial]);
selecionados.Add(tmp);
}
}
foreach (Aresta a in selecionados)
{
Debug.Print(a.ToString());
a.Selecionado = true;
}
DesenharMapa();
}Isso ai ta encontrando os [Ô]n[Ô] menores caminhos, nao tem nada a ver com o ir de / para , mas eh o que os livros de algoritmo que encontrei me mostram (e olha, nao foi poucos nao).
Tópico encerrado , respostas não são mais permitidas