Tive problemas para criar a lógica do solução desse problema se puderem me ajudar seria ótimo:
se tem um conjunto de nós em uma rede no qual todos devem ser interligados direta ou indiretamente, cada interligação entre nós tem um custo e é preciso dar a implementação mais barata através do modo de colocar as interligações:
de que modo faço a verificação?
Se eu não me engano isso é árvore geradora minima, da uma olhada em Prim ou Kruskal q esse problema morre.
[]s!
Leonardo Gloria
Tinha pensado em pegar
nó inicial, nó final e custo
como por exemplo:
(N é a sigla para Nó)
N1 a N2 custa 10
N1 a N3 custa 11
N2 a N3 custa 12
N1 a N4 custa 13
enumerar as posições:
(L é sigla para ligação)
L1: N1 a N2
L2: N1 a N3
L3: N2 a N3
L4: N1 a N4
(ligações possíveis)
depois testar as ligações de acordo o grupo com combinações iguais a 3 que é o mínimo de ligações para quatro nós
e comparar qual o grupo de ligações mais barato:
Sequência 1: L1 L2 L3
Sequência 2: L1 L2 L4
Sequência 3: L1 L3 L4
Sequência 4: L2 L3 L4
(demais sequências conforme o aumento do numero de nós)
custoL1 + custoL2 + custoL3 = custo da Sequência 1
custoL1 + custoL2 + custoL4 = custo da Sequência 2
custoL1 + custoL3 + custoL4 = custo da Sequência 3
custoL2 + custoL3 + custoL4 = custo da Sequência 4
Só não sei se a lógica está correta…
Isso se resume a um algoritmo ligado a grafo onde você precisa descobrir o caminho de menos custo a dois vértices distintos, não é isso?
Você pode usar algoritmos prontos: Prim e Kruskal como já disse nosso colega acima.
[quote]For a graph with V vertices E edges, Kruskal’s algorithm runs in O(E log V) time and Prim’s algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.[/quote]
http://stackoverflow.com/questions/1195872/kruskal-vs-prim
Se eu não me engano, para problemas como esse o pessoal prefere Kruskal, mas não estou muito certo.
Renato, a preferência por Kruskal pode ser pela facilidade de implementação. Prim, Prim Colorido e Boruvka, perto do Kruskal, pelo menos na minha opinião, são um pouco mais complexos de implementar.
Exatamente! Se vc tiver pensando a nivel de competição e tentar comparar as possiveis soluções vai dar o famoso TLE!
[]s!
Leonardo Gloria
Decidi utilizar o algoritmo de Prim, sabem um bom exemplo de implementação para o algoritmo?
Eu iria sugerir Kruskal tambem… basta voce ordenar todas as arestas e sempre ir pegando a menor e ver se os dois componentes ja estao conectados. Se nao estao, adiciona a aresta e conecta os dois, ai verifica a proxima aresta. Eu era bom de Kruskal na maratona de programacao :).
E, se voce nao precisa de velocidade, nao precisa implementar o union-find (apesar de quem em Java fica bem facil com HashSets)
Pow Paulo n sabia que você era maratonista se não trocava umas idéias contigo após a sua palestra sobre JPA no Jboss in bossa!
=)
[]s!
Leonardo Gloria
Obrigado pela ajuda pessoal!
Usando o algoritmo de Prim fiz meu próprio código na unha e até ficou legal.
Implementei uma classe Grafos que cria um grafo em um tipo de matriz e encontra o percurso mínimo:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package redeotica;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
*
* @author David Kennedy S. A.
*/
public class Grafo {
private int numeroDeVertices, numeroDeArestas;
private int[][] arestasAComparar = new int[100][3];//CRIAR METODO MAIS EFICIENTE PARA DEFINIR NUMERO DE ARESTAS MÁXIMO A COMPARAR
private int indiceDoArray = 0;
private boolean[] vertices;
private int[][] arestas;
public Grafo(int quantidadeDeVertices, int quantidadeDeArestas) {
numeroDeVertices = quantidadeDeVertices;
numeroDeArestas = quantidadeDeArestas;
vertices = new boolean[quantidadeDeVertices + 1]; //desconsiderar o vertice de indice 0
arestas = new int[quantidadeDeArestas][3]; //o numero de colunas é fixo "3"
}
private void adicionaArestaParaComparar (int verticeInicial,int verticeFinal,int comprimento) {
arestasAComparar[indiceDoArray][0] = verticeInicial;
arestasAComparar[indiceDoArray][1] = verticeFinal;
arestasAComparar[indiceDoArray][2] = comprimento;
indiceDoArray++;
}
protected void adicionaArestaParaComparar (int[] partida) {
for (int i = 0; i < partida.length; i++) { //corre as partidas
for (int j = 0; j < numeroDeArestas; j++) {
if (arestas[j][0] == partida[i] && vertices[arestas[j][1]] == false) {
adicionaArestaParaComparar(arestas[j][0], arestas[j][1], arestas[j][2]);
}
}
}
}
private void adicionaArestaParaComparar (Object[] partida) {
for (int i = 0; i < partida.length; i++) { //corre as partidas
for (int j = 0; j < numeroDeArestas; j++) {
if (arestas[j][0] == partida[i] && vertices[arestas[j][1]] == false) {
adicionaArestaParaComparar(arestas[j][0], arestas[j][1], arestas[j][2]);
}
if (arestas[j][1] == partida[i] && vertices[arestas[j][0]] == false) {
adicionaArestaParaComparar(arestas[j][0], arestas[j][1], arestas[j][2]);
}
}
}
}
protected void limpaArestasComparadas() {
for (int i = 0; i < arestasAComparar.length; i++) {
arestasAComparar[i][0] = 0;
arestasAComparar[i][1] = 0;
arestasAComparar[i][2] = 0;
}
indiceDoArray = 0;
}
private int[] menorCaminho() {
int[] aresta = new int[3];
int comp = 9999999;
for (int i = 0; i < arestasAComparar.length && arestasAComparar[i][2] != 0; i++) {
if (arestasAComparar[i][2] < comp) {
aresta[0] = arestasAComparar[i][0];
aresta[1] = arestasAComparar[i][1];
aresta[2] = arestasAComparar[i][2];
comp = arestasAComparar[i][2];
}
}
return aresta;
}
protected void imprimeMenorCaminho() {
int[] aresta = menorCaminho();
//troca aresta[1] e aresta[0] de lugar deixando sempre aresta[0] < aresta[1]
int aux;
if (aresta[0] > aresta[1]) {
aux = aresta[0];
aresta[0] = aresta[1];
aresta[1] = aux;
}
System.out.printf("%d %d %d\n", aresta[0], aresta[1], aresta[2]);
}
private boolean marcaVerticeDoMenorCaminho() {
int[] aresta = menorCaminho();
//retorna "true" se o vertice inicial estiver marcado
if (vertices[aresta[0]] == true){
vertices[aresta[1]] = true;
return true;
} else {
return false;
}
}
protected void imprimeSituacaoDosVertices() {
for (int i = 1; i < numeroDeVertices; i++)
System.out.println("Vertice " + i + " = " + vertices[i]);
}
protected void imprimeArestasParaComparação() {
for (int i = 0; i < 10; i++) {
System.out.print(arestasAComparar[i][0]);
System.out.print(" " + arestasAComparar[i][1]);
System.out.println(" " + arestasAComparar[i][2]);
}
}
public void leEConstroiTabela() {
Scanner scan = new Scanner(System.in);
for (int i = 0; i < numeroDeArestas; i++) {
int x = scan.nextInt(); //lê o nó inicial e coloca em contagem do 0
int y = scan.nextInt(); //lê o nó final e coloca em contagem do 0
int z = scan.nextInt(); //lê o custo ambiental
arestas[i][0] = x; //atribui o indice do vertice inicial
arestas[i][1] = y; //atribui o inice do vertice final
arestas[i][2] = z; //atribui o comprimento da aresta
}
}
public void encontraCaminhoMinimo() {
List<Integer> partida = new ArrayList<Integer>();
partida.add(1);
vertices[1] = true;
for (int i = 0; i < (numeroDeVertices - 1); i++) {
adicionaArestaParaComparar(partida.toArray());
imprimeMenorCaminho();
partida.add(menorCaminho()[1]);
marcaVerticeDoMenorCaminho();
limpaArestasComparadas();
}
}
}agora é fácil usar uma classe com método principal para criar o grafo e encontrar o caminho mínimo
como por exemplo:
[code]public class TestMainGrafo {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int numeroDeVertices, numeroDeArestas;
System.out.print("Qual o numero de vertices? ");
numeroDeVertices = scan.nextInt();
System.out.print("Qual o numero de arestas? ");
numeroDeArestas = scan.nextInt();
System.out.println("Insira os valores da tabela:\n(vertice [espaço] vertice [espaço] comprimento)");
Grafo g = new Grafo(numeroDeVertices, numeroDeArestas);
g.leEConstroiTabela();
System.out.println("\nCaminho mínimo:\n");
g.encontraCaminhoMinimo();
}
}[/code]
Exemplo de saída:
[quote]Qual o numero de vertices? 3
Qual o numero de arestas? 3
Insira os valores da tabela:
(vertice [espaço] vertice [espaço] comprimento)
1 2 10
2 3 10
3 1 10
Caminho mínimo:
1 2 10
1 3 10[/quote]
ainda tem problemas para definir o tamanho de private int[][] arestasAComparar = new int[100][3];
na linha 19
Agora que o problema foi basicamente resolvido tenho problemas com o tamanho dos valores que o meu programa pode suporta… Alguma idéia de como aumentar sua capacidade para cálculos maiores