Duvida no código

[cryteck]

Boas.

Eu tenho o seguinte código para a descoberta do caminho mais curto, ou seja o caminho com menor incisão entre os pesos de um grafo.

Este código está a funcionar realmente dá me o caminho mais curto entre dois vértices mas não estou a compreender bem a sua forma de "trabalhar". Já tentei perceber mas nunca chego a uma conclusão será que me podiam explicar mais ou menos como está a funcionar se faz favor o código é o seguinte:

/******************************************************************
 Returns an iterator that contains the indices of the vertices
 that are in the shortest path between the two given vertices.
  ******************************************************************/
  protected Iterator<Integer> iteratorShortestPathIndices(int startIndex, int targetIndex)
  {
  int index;
  double weight;
  int[] predecessor = new int[numVertices];
  Heap<Double> traversalMinHeap = new Heap<Double>();
  ArrayUnorderedList<Integer> resultList =new ArrayUnorderedList<Integer>();
  LinkedStack<Integer> stack = new LinkedStack<Integer>();
  int[] pathIndex = new int[numVertices];
  double[] pathWeight = new double[numVertices];
  for (int i = 0; i < numVertices; i++)
	 pathWeight[i] = Double.POSITIVE_INFINITY;
  boolean[] visited = new boolean[numVertices];
  for (int i = 0; i < numVertices; i++)
	 visited[i] = false;
  if (!indexIsValid(startIndex) || !indexIsValid(targetIndex) ||
				   (startIndex == targetIndex) || isEmpty())
	 return resultList.iterator();
  pathWeight[startIndex] = 0;
  predecessor[startIndex] = -1;	
  visited[startIndex] = true;
  weight = 0;
  /** Update the pathWeight for each vertex except the
	  startVertex. Notice that all vertices not adjacent
	  to the startVertex  will have a pathWeight of
	  infinity for now. */
  for (int i = 0; i < numVertices; i++)
  {
	 if (!visited[i])
	 {
		pathWeight[i] = pathWeight[startIndex] +adjMatrix[startIndex][i];
		predecessor[i] = startIndex;
		traversalMinHeap.addElement(new Double(pathWeight[i]));
	 }
  }
  do
  {
	 weight = (traversalMinHeap.removeMin()).doubleValue();
	 traversalMinHeap.removeAllElements();
	 if (weight == Double.POSITIVE_INFINITY)  // no possible path
		return resultList.iterator();
	 else
	 {
		index = getIndexOfAdjVertexWithWeightOf(visited, pathWeight,weight);
		visited[index] = true;
	 }
	 /** Update the pathWeight for each vertex that has has not been
		 visited and is adjacent to the last vertex that was visited.
		 Also, add each unvisited vertex to the heap. */
	 for (int i = 0; i < numVertices; i++)
	 {
		if (!visited[i])
		{
		   if((adjMatrix[index][i] < Double.POSITIVE_INFINITY) &&
			  (pathWeight[index] + adjMatrix[index][i]) < pathWeight[i])
		   {
			  pathWeight[i] = pathWeight[index] + adjMatrix[index][i];
			  predecessor[i] = index;
		   }	  
		   traversalMinHeap.addElement(new Double(pathWeight[i]));
		}
	 }
  } while (!traversalMinHeap.isEmpty() && !visited[targetIndex]);
  index = targetIndex;
  stack.push(new Integer(index));
  do
  {
	 index = predecessor[index];
	 stack.push(new Integer(index));
  } while (index != startIndex);

  while (!stack.isEmpty())
	 resultList.addToRear((stack.pop()));
  return resultList.iterator();
  }

/******************************************************************
 Returns an iterator that contains the shortest path between
 the two vertices.
  ******************************************************************/
  public Iterator<T> iteratorShortestPath(int startIndex, int targetIndex)
  {
  ArrayUnorderedList templist = new ArrayUnorderedList();
  if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
	 return templist.iterator();
  Iterator<Integer> it = iteratorShortestPathIndices(startIndex,targetIndex);	
  while (it.hasNext())
	 templist.addToRear(vertices[(it.next()).intValue()]);
  return templist.iterator();
  }

Será que me podiam dar uma ajuda pois este algoritmo utiliza uma Heap e um ArrayUnorderedList e uma Stack três estruturas para quê?

Sei que retorna um iterador mas como o iterador é construído?

Tou mesmo a nora na compreensão do código era mesmo uma explicaozita pequena que precisava.

Cumps,

Luís Sousa

Edited February 20, 2013 at 10:30 PM by cryteck

[HappyHippyHippo]

a chave para a compreensão do algoritmo está neste código:

double[] pathWeight = new double[numVertices];
for (int i = 0; i < numVertices; i++)
   pathWeight[i] = Double.POSITIVE_INFINITY;

boolean[] visited = new boolean[numVertices];
for (int i = 0; i < numVertices; i++)
   visited[i] = false;

estes arrays são arrays auxiliares usados para verificar :

- pathWeight : peso/distância de chegar ao nó

- visited : marcador que o nó já foi visitado

o que o código faz é uma BFS que verifica um nó na lista de nós a verificar (traversalMinHeap) ainda não visitados, actualizando os pesos/distâncias sempre que o nó é verificado.

a stack é usada para construir o caminho, através do arrays de precedentes

(explicar por palavras é um bocado complicado ...)

[cryteck]

Obrigado desde já pela tua disponibilidade e compreensão.

Será que podias fazer uns comentáriozinhos em português no código para eu tentar perceber melhor o código, pois eu vou tentar perceber custe o que custar pois tenho mesmo de saber explicar para amnhã.

Muito obrigado sei que é difícil explicar pelo pc mas mais uma vez obrigado pelo esforço.

Cumps,

Luís Sousa

Edited February 20, 2013 at 11:10 PM by cryteck

[HappyHippyHippo]

seria mais fácil anotares quais as partes que não percebes ...

[cryteck]

O que faz precisamente o array predecessor sabes tou com duvidas aí e quando faz removes na traversalMinHeap é para quê?

[HappyHippyHippo]

o array predecessor serve para guardar o índice dos nós precedentes de cada nó após da construção do caminho, é por isso que é usada a stack para a construção do caminho no processo final

tu removes da Heap quando pretendes processar um nó ainda não visitado, isto porque os nós na Heap serão os nós adjacentes do nó recentemente visitado que ainda não foram processados.

o nó removido é o nó com menor peso/distância.

ok ... talvez seja melhor leres sobre o assunto : http://en.wikipedia.org/wiki/Dijkstra's_algorithm

[cryteck]

O nó removido da heap e depois é adicionado na stack?

Já agora um nó adjacente é um nó que tem uma aresta com o visitado ?

Uma pergunta que o professor me fez foi como é que o algoritmo sabe que á outro caminho melhor do que está escolhido até ao momento e eu fiquei sem conseguir explicar ?

[HappyHippyHippo]

O nó removido da heap e depois é adicionado na stack?

não ...

tira da Heap um nó ainda não visitado

adicionar à stack é somente depois de ter visitado todos para se "reconstruir" o caminho de menor peso

Já agora um nó adjacente é um nó que tem uma aresta com o visitado ?

sim

Uma pergunta que o professor me fez foi como é que o algoritmo sabe que á outro caminho melhor do que está escolhido até ao momento e eu fiquei sem conseguir explicar ?

o algoritmo escolhe sempre o melhor caminho isto porque o algoritmo é feito nos seguintes pressupostos:

- se ainda não foi encontrado um caminho

- visitar um nó ajdacente a qualquer nó já visitado, ainda não visitado, que custa menos visitar

o que podes ter, é um outro caminho alternativo que não é melhor mas também não é pior (é igual).

isso é algo que o código não verifica porque a pesquisa para imediatamente que encontra um caminho até ao destino (estás a visitar o nó destino)

o fundamental a reter é : cada passo do ciclo cria/estende um sub-grafo em que o caminho de chegar do nó origem até ao nó visitado é sempre o menor (e não existe ciclos, porque não voltas a visitar nós já visitados)

[cryteck]

Mas imagina este tres vertices n1 n2 n3

Quero saber o caminho mais curto entre o n1 e n3

n1->n2 peso 200

n1-> n3 peso 350

n2-> n3 peso 400

Segundo o k tu me explicaste .

Visita o n1, o n1 tem duas hipoteses ir para o n2 ou n3, explicaste que escolhe sempre o de menor peso ia para o n2 e do n2 para o n3. ou seja caminho dava n1->n2->n3 peso 600.

Enquanto que o caminho mais curto era n1->n2 com peso de 350.

Aí é que está a minha dúvida de voltar atrás ou não percebeste a minha dúvida ?

Edited February 21, 2013 at 12:21 AM by cryteck

[HappyHippyHippo]

o que disse foi :

visitar um nó ajdacente a qualquer nó já visitado, ainda não visitado, que custa menos visitar

o que isto quer dizer é que, depois de teres escolhido a aresta n1->n2, o que irás escolher é a aresta n1->n3, nunca chegas a processar a aresta n2->n3

[cryteck]

Essa frase é mesmo complicada de perceber 😁 , ainda não percebi mesmo.

Nunca chega a processar a aresta n2->n3 porquê? O que tu dizes tem lógica processar antes a aresta n1->n3 pois tem menor peso no total para chegar ao destino mas não tou a ver como o código faz isso

Foi nesta parte que o professor me lixou da outra vez tenho de perceber ...

[HappyHippyHippo]

imagina que tens N nós (não interessa), já visitaste N-M (não interessa)

vou chamar ao grupo de nós já visitados de X, e ao grupo de nós não visitados (N-X) de Y

o que o algoritmo faz é verificar qual é a aresta com menor peso que liga um nó já visitado (no pertencente a X) a um nó ainda não visitado (nó pertencente a Y)

não interessa se estás no nó Ni, o que interessa é a aresta que vais processar e por consequente, o próximo nó a ser visitado

--------

lembrei-me que tinha explicado isso (à um tempo atrás) graficamente

https://www.portugal-a-programar.pt/topic/54706-ajuda-mostspanningtree/?do=findComment?comment=465192

ps : o algoritmo é para criação de uma minimum spamming tree, mas é praticamente a mesma coisa

Edited February 21, 2013 at 12:54 AM by HappyHippyHippo

[cryteck]

Deixa me ver se percebi

o que interessa é a aresta que vais processar e por consequente, o próximo nó a ser visitado

No meu exemplo ele processa o n1->n2 mas como depois como vê que a proxima aresta a ser visitada ia n2->n3 e ia dar um peso maior processa antes a aresta n1->n3 ? É isso?

Edited February 21, 2013 at 01:11 AM by cryteck

[HappyHippyHippo]

No meu exemplo ele processa o n1->n2 mas como depois como vê que o proximo nó a ser visitado ia n2->n3 e ia dar um peso maior processa antes o n1->n3 ? É isso?

não confundas nó com aresta (e o seu peso) !

não tem nada haver com o próximo nó mas sempre com a aresta a ser processada

[jsWizard]

off topic..

passo-me com o povo que não usa chavetas nos IFs, FORs... só porque só têm uma linha de código.. quando tiverem de fazer debug de muitos milhares de linhas de código (possivelmente escritos por N pessoas ao longo dos anos) e descobrirem que o problema era uma instrução fora do IF ou do LOOP.. passaram a usar sempre as chavetas.. até porque é muito mais legível!

Inté! 😄

Edited February 26, 2013 at 05:16 PM by jsWizard