Legal a discussão.
Desculpem mais uma vez. Para o tipo de matriz em foco, eu não posso colocar zeros quando não existem as ligações. Matriz errada novamente. Estava pensando na matriz de incidência, cujas células são preenchidas com 1, caso exista a ligação, e 0 quando não existe. Esta seria a representação da rede. Para o cálculo, normalmente coloca-se as distâncias reais, quando existe a ligação direta, e um número muito grande (99999, por exemplo, para representar o infinito) quando ela não existe. Isso, é claro, vai depender da estrutura de dados e dos algoritmos utilizados.
O exemplo que citei sobre valores diferentes de zero na diagonal, foi um pouco fora do objetivo da discussão, mas serve para adicionar um outro ponto que pode ser tratado com o uso de uma matriz. Geometricamente não faz sentido, mas logicamente, porque não? Seriam atividades que ocorrem no nó da rede. Eu posso trabalhar com áreas (bairros de uma cidade, por exemplo) que são representadas, para efeitos de montar a rede, por pontos localizados nos seus centros geométricos (centróides). Eu tenho viagens que ocorrem entre áreas, que simplifico nas ligações entre centróides, e viagens que ocorrem dentro da área, que posso armazenar na diagonal da matriz. Esse arranjo não é comum, mas não me parece incorreto. Bom, mas isso foge do objetivo da conversa.
Se o objetivo é ter um banco de dados com todas as distâncias, acho que pode-se montar uma rede e armazenar as informações dos pares para os quais existam ligações diretas. Posteriormente, pode-se usar um algoritmo de caminhos mínimos para encontrar a menor distância e a rota (cidades por onde passa) entre essas cidades. Nunca trabalhei com uma rede tão grande para esse tipo de aplicação, mas acredito que a resposta saia em segundos ou frações.
Não sei qual é o objetivo do Leandro ao montar essa matriz, mas essa "brincadeira" pode ficar interessante. Você pode acrescentar links com diferentes modos de transportes. Se for para transportar pessoas, pode-se usar automóveis, ônibus, trens, barcos, aviões, ... São distâncias (km) diferentes, custos (R$) diferentes, tempos (horas) diferentes. Na hora de gerar a solução do "menor caminho" pode-se escolher o mais curto, o mais barato ou o mais rápido. É algo que o Google Maps e serviços similares fazem.
Infelizmente, ainda não usei o R para esse tipo de aplicação. Por isso, posso estar "chovendo no molhado" na opinião de alguns de vocês. Algumas vezes cubro tópicos já presentes em mensagens anteriores. É só para dar uma certa continuidade ao texto.
Abs.
Mário
2011/11/5 Cesar Rabak
<cesar.rabak@gmail.com>
Em 5/11/2011 12:44, Mario Azevedo escreveu:
Oi Cesar,
Eu sei disso. Não deixei claro, mas estava pensando na parte do
processamento da matriz. Seria, talvez, um quarto item na sua lista.
Nem sempre o programa aceita ou a pessoa sabe programar para
"eliminar" (evitar que o computador reserve espaço de memória) para
uma matriz da qual só lhe interessam poucas células, neste caso, só
uma das partes triangulares sem a diagonal.
Sim. Esse é um tipo de conhecimento mais específico.
Posso ilustrar um pouco mais a importância dessa questão? Este
problema, que simplificamos (distâncias euclidianas), fica maior
quando consideramos que não existem ligações diretas (estradas) entre
todos os pares de cidades.
Corretíssimo. Aliás isso enseja uma discussão entre as assim chamadas
(pelo menos assim era quando estudei isso) distâncias geográficas versus
distâncias geométricas.
Aí o armazenamento dessa matriz cheia de zeros demanda cuidado,
principalmente se for muito grande.
Na verdade para essa matriz (ou objeto de armazenagem apropriado) ser
usável do ponto de vista matemático, nos pares de pontos (cidades) que
não haja caminho direto você precisaria colocar ou algo entendível pelo
R como +Inf ou um código especial para sinalizar esse caso. Armazenar
_zeros_ nessas posições seria um erro crasso (posso escrever ex-cátedra).
Pode, também, não ser simétrica. No ambiente urbano, por exemplo, nem
sempre a "distância" de i para j é a mesma de j para i.
Esse caso está coberto na minha discussão, mas imagino que para
distâncias entre cidades esse problema não seja tão influente (embora
reconheço que para conexão entre certas cidades às vezes é necessário
passar "por dentro de alguma outra".
Na minha área de trabalho (planejamento de transportes), algumas
vezes a diagonal principal pode estar preenchida com valores
diferentes de zero, se eu considerar a extensão média das viagens. Os
nós da minha rede representam centróides de zonas (setores
censitários do IBGE, por exemplo) e ocorrem viagens dentro das
zonas.
Não entendi bem o quê você quer dizer com "extensão média de viagens".
SE a granularidade da sua matriz for uma subdivisão de um município,
obviamente é a distância entre essas subunidades que se deve discutir,
senão entramos em inconsistências tanto lógicas como matemáticas.
Acima, coloquei distância entre aspas porque no meu caso, que
trabalho com transportes, ela pode não ser representada pela extensão
em km e sim pelo tempo em minutos, ou alguma misturas destes dois
e/ou outros. A "distância" é expressada por um custo para percorrer
determinado trecho da rede.
OK. Eu tenho bastante experiência com esse conceito¹!
Espero ter esclarecido. Obrigado por corrigir a confusão que a minha
mensagem possa ter causado.
Esclarecendo, vamos ajudando o OP a encontrar uma solução para um
problema que deve ser não só dele como de muita gente >
[]s
[1] http://www.teses.usp.br/teses/disponiveis/3/3141/tde-24062005-190210/