Inteligencia Artificial

Prévia do material em texto

Os algoritmos são sequências organizadas de execuções que são utilizadas para se garantir que determinados problemas sejam resolvidos. No algoritmo de Dijkstra, isso não é diferente, pois o objetivo é ter uma entrada de dados que permita fazer o processamento e, finalmente, que gere uma saída na qual foi programada.
 
Considerando o exposto, sobre o algoritmo de Dijkstra, analise as afirmativas a seguir.
 
I. O ponto inicial é utilizado na letra “P” com o valor 1.
II. É atribuído o valor infinito para todos os vértices no início do algoritmo.
III. Nas interações do algoritmo, o infinito deve ser substituído pelos custos negativos encontrados nos trajetos.
IV. Se existir um valor de menor custo no cruzamento de determinado vértice e se o algoritmo encontrar um trajeto de menor custo entre dois vértices, então se sobrescreve o valor.
 
Está correto o que se afirma em:
Resposta correta. A alternativa está correta. A afirmativa II se apresenta de maneira adequada, pois, quando a rotina do algoritmo de Dijkstra é iniciada, todos os vértices existentes no grafo recebem o valor infinito. A afirmativa IV também se apresenta de maneira adequada, pois a função principal do algoritmo é buscar o menor peso (custo) entre os vértices do grafo.
II e IV, apenas.
O mapeamento dos custos de deslocamento é uma variável de extrema importância, principalmente quando estamos falando a respeito do planejamento da otimização de rotas. O grafo representado na seguinte figura demonstra o custo de deslocamento entre algumas cidades:
Fonte: Elaborada pelo autor.
 
Com base no algoritmo de Floyd-Warshall, os valores foram expressos na matriz evidenciada no seguinte quadro:
	
A
B
C
D
A
0
4
2
6
B
∞
0
3
4
C
∞
∞
0
∞
D
∞
∞
5
0
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, uma vez que o grafo não possui ligação com o direcionamento entre os vértices: B para A, C para A, C para B, C para D, D para A e D para B, totalizando seis. A asserção II também é uma proposição verdadeira e justifica a I, pois expressa que não existe um relacionamento naquela direção.
Um grupo de arqueólogos encontrou um mapa no qual é possível indicar uma grande construção subterrânea. Porém, após diversas análises, foi cogitada a possibilidade de desvendar o trajeto, caso seja aplicado o algoritmo de Kruskal. Esse mapa é demonstrado na seguinte figura:
Fonte: Elaborada pelo autor.
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas.
 
I. Não é possível aplicar o algoritmo de Kruskal no grafo.
Pois:
II. A quantidade de vértices no grafo é par, por isso, sempre será fechado um ciclo.
 
A seguir, assinale a alternativa correta.
As asserções I e II são proposições falsas.
Resposta correta. A alternativa está correta, pois a asserção I é uma proposição falsa, já que é possível aplicar o algoritmo de Kruskal no grafo. A asserção II também é uma proposição falsa, pois o fato de o grafo ter quantidade par ou ímpar não impede de se utilizar o algoritmo de Kruskal para se ter uma árvore geradora mínima.
Os algoritmos são ferramentas da lógica computacional que permitem organizar rotinas, a fim de se planejar o sequenciamento de ações sobre determinado conjunto de valores. Quanto à sua aplicação na teoria dos grafos, é essencial saber identificar as características do grafo, para, após isso, ser utilizada a análise algorítmica. Um exemplo de grafo, passível de análise, pode ser observado na seguinte figura:
A respeito do algoritmo de Dijkstra, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
 
I. ( ) São necessários 8 passos para se obter um trajeto otimizado de S para qualquer outro vértice.
II. ( ) Não é possível utilizar o algoritmo de Dijkstra na análise do grafo, pois ele está desenvolvido em árvore.
III. ( ) É preciso fazer todos os trajetos nas subárvores e seus respectivos custos. Somente após isso, deve-se passar para as subárvores adjacentes.
IV. ( ) Não é possível utilizar o algoritmo de Dijkstra na análise do grafo, pois existem custos negativos entre os vértices.
 
Assinale a alternativa que apresenta a sequência correta.
F, F, V, V.
Sua resposta está incorreta. A alternativa está incorreta, pois a afirmativa I é falsa, já que o algoritmo de Dijkstra não efetua análise em grafos em árvore. A afirmativa III é falsa, pois, no algoritmo de Dijkstra, busca-se o menor custo entre os vértices de um grafo valorado e em circuito, não sendo possível fazer uma análise em grafo em árvore. Desse modo, o método de busca descrito não funcionaria.
Leia o excerto a seguir.
 
“[...] o corte utilizado em cada iteração é o corte mínimo com probabilidade de, pelo menos, 1 / n2. Em qualquer estágio do algoritmo de Kruskal, o conjunto de vértices é particionado. As arestas elegíveis para serem adicionadas à árvore têm suas extremidades em componentes distintos.”
 
DASGUPTA, S. Algoritmos. Porto Alegre: AMGH, 2009. p. 140.
 
Considerando o exposto, sobre o algoritmo de Kruskal, analise as afirmativas a seguir.
 
I. O algoritmo de Kruskal utiliza a recursividade para determinar o menor custo.
II. O algoritmo de Kruskal prioriza os custos negativos antes dos positivos.
III. O algoritmo de Kruskal não permite gerar grafo com característica hamiltoniana.
IV. O algoritmo de Kruskal busca fazer a eliminação de vértices que, ao passarem pelas arestas, retornam à origem do caminho.
 
Está correto o que se afirma em:
Sua resposta está incorreta. A alternativa está incorreta, pois, na afirmativa I, expõe-se que é utilizada a recursividade, não sendo uma verdade, porque o algoritmo seleciona a aresta de menor custo que não fecha um circuito. A afirmativa II está incorreta, pois o algoritmo de Kruskal não utiliza pesos negativos.
I, II e IV, apenas.
 
O algoritmo de Floyd teve a contribuição de três pesquisadores quanto ao seu desenvolvimento, tornando-se uma das mais importantes contribuições para áreas ligadas à matemática, à estatística, à ciência da computação, à pesquisa operacional, entre outras. Nesse sentido, assinale a alternativa que apresenta corretamente o funcionamento do algoritmo de Floyd-Warshall.
Resposta correta. A alternativa está correta, pois o funcionamento do algoritmo de Floyd-Warshall consiste em encontrar o trajeto de menor custo entre dois vértices de um grafo. Para o algoritmo, a ordem com que será percorrido o trajeto pelas arestas existentes é indiferente. Com isso, retorna um trajeto otimizado.
Encontrar o caminho de menor custo entre dois vértices, em um grafo valorado.
O algoritmo de Kruskal foi desenvolvido pelo PhD Joseph Bernard Kruskal Júnior (1928 - 2010) para efetuar algumas análises em grafos. A forma de atuação desse algoritmo foi inovadora, pois, além de encontrar caminhos mínimos, ele propôs uma transformação no formato do grafo. A respeito do exposto, assinale a alternativa que apresenta corretamente o funcionamento do algoritmo de Kruskal
Resposta correta. A alternativa está correta, pois o funcionamento do algoritmo de Kruskal consiste em encontrar a árvore geradora mínima em um grafo que tenha custo entre os vértices. O intuito é eliminar as arestas do grafo que, se utilizadas no trajeto, irão formar um circuito fechado.
Encontrar a árvore geradora mínima em um grafo valorado.
Uma das etapas encontradas no algoritmo de Bellman-Ford está no processo de verificação de ciclos negativos, importante para se garantir que os resultados gerados sejam condizentes com as análises proporcionadas pelos algoritmos implementáveis na teoria dos grafos.
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas.
 
I. O primeiro processo do algoritmo de Bellman-Ford faz a padronização dos valores de vértices não relacionados.
Pois:
II. O processo que precede a verificação é o relaxamento, o qual é responsável por buscar o menor caminho de menor custo entre os vértices.
 Resposta correta. A alternativa estácorreta, pois a asserção I é uma proposição verdadeira, já que a primeira etapa dos processos do algoritmo visa à padronização dos vértices não relacionados. A asserção II também é uma proposição verdadeira e não justifica a I, pois se expõe que o processo de relaxamento busca o menor custo e isso está correto, porém, em cada asserção, é explicado o funcionamento, mas ambas não se justificam.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
O mapeamento dos custos de deslocamento entre algumas cidades foi representado na seguinte figura:
Considerando um trajeto de A para E e com base no algoritmo de Dijkstra, os valores foram expressos na matriz evidenciada no seguinte quadro:
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas.
 
I. Foram fixados os valores na linha A (0, A) e na linha B (1, A).
Pois:
II. Não haverá custo de A para A pela ausência de laço, não sendo encontrado um custo menor de B para C.
 
A seguir, assinale a alternativa correta.
Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, porque foram fixados os valores encontrados nos trajetos de A para A como 0 (zero), uma vez que não existe laço no vértice A. Já o custo entre os vértices A para B foi fixado em 1, pois, se for feito qualquer outro trajeto entre os dois pontos, o custo será maior.
A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa.
O algoritmo de Dijkstra é semelhante ao algoritmo de Bellman-Ford, pois, entre outras coisas, pode calcular o trajeto mínimo entre dois vértices de determinado grafo valorado. Porém, em Dijkstra, possui diferenças em relação ao algoritmo de Bellman-Ford. Nesse sentido, assinale a alternativa que apresenta corretamente outra diferença nos algoritmos de Dijkstra e de Bellman-Ford.
Resposta correta. A alternativa está correta, pois o algoritmo de Dijkstra não consegue efetuar uma tratativa quando, no relacionamento entre os vértices por meio das arestas, são encontrados valores negativos. Para esse tipo de grafo com valores negativos, o indicado é utilizar o algoritmo de Bellman-Ford.
O algoritmo de Dijkstra não efetua cálculos com valores negativos.