Questões - Trabalho de Grafos

Prévia do material em texto

PROBLEMA 1: MELHOR CAMINHO 
 
Descrição 
O problema de melhor caminhoéumproblemaclássicodealgoritmosdegrafos.                         
Ele consiste de um grafo com N vértices e M arestas. Cada aresta possui um                             
peso que no nosso caso é a distância em quilômetros entre dois vértices. 
 
Tal problema pode ser utilizado para determinar uma rota para sistemas de                       
entrega (Delivery). Dessa forma, seu trabalho édesenvolverumalgoritmoque                     
dadoumgrafoGeumconjuntodevérticesV={V0,V1,V2,…,Vn},determineo                              
melhor caminho possível que vá de V0 até Vn passando por todos os demais                           
vértices na ordem fornecida. 
 
Exemplo de entrada 
Dois arquivos serão fornecidos: 
1.Instânciadografo:umarquivocontendotodasasinformaçõesarespeito                    
do grafo. 
a.Nomedoarquivo:GRAPH_NUM,noqualNUMéuminteiroqueinformao                       
número de vértices do grafo; 
b.Cada linha do arquivo fornece as informações sobre o vértice de                     
origem,ovérticedestinoeadistâncientreosvértices,comopor                    
exemploalinha:1215significaqueocustodeirdovértice1o                         
vértice 2 é 15. 
2.Instância do problema: um arquivo contendo vários instâncias a serem                   
solucionadas. 
a.Nome do arquivo: INST_10, noqualNUMéuminteiroqueinformao                         
número de vértices do grafo; 
b.Cada linha fornece um problema a ser solucionado, na qual a                     
sequênciaapresentadaéasequênciaaserseguidapeloentregador.                
Porexemplonalinha:13586910seualgoritmodevepartirdo                             
vértice1echegaraovértice10passandopelosvértices3,5,8,                        
6 e 9 exatamente nesta ordem. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
PROBLEMA 2: CAMINHO MAIS RÁPIDO 
 
Descrição 
Um problema comum enfrentado pelos motoristas é encontrar o caminho mais                     
rápido até seu destino. Neste caso, o espaço percorrido não é importante ao                         
ponto de ser decisivo para a escolha de uma rota. Em muitoscasos,caminhos                           
mais curtos podem ser mais demorados por conta dos engarrafamentos. 
 
Considerando este problema, faça uma solução para encontrar o caminho mais                     
rápido entre dois pontos A e B. Você deve considerar um grafo que possui a                             
informaçãodetodasasarestasdografocomduasinformaçõesparacadaaresta:                         
a distância em quilômetros e a velocidade média máxima para aquele trecho. 
 
Para determinar o tempo para percorrer uma aresta (trecho), considere que o                       
motorista sempre utilizará a velocidade média informada no grafo. Não é                     
precisoconsiderartempodeesperaemsinaisdetrânsito,paradasdepedestres                       
e etc. 
 
É importante considerar que se existe um caminho entre A e B, não é                           
obrigatório existir um caminho entre B e A, e 
 
Exemplo de entrada 
Dois arquivos serão fornecidos: 
3.Instânciadografo:umarquivocontendotodasasinformaçõesarespeito                    
do grafo. 
a.Nomedoarquivo:GRAPH_NUM,noqualNUMéuminteiroqueinformao                       
número de vértices do grafo; 
b.Cada linha do arquivo fornece as informações sobre o vértice de                     
origem, o vértice destino, a distância entre os vértices e a                     
velocidade média no trecho; 
c.Um exemplo da instância é a linha: 1 2 1.5 40 significa que a                           
distânciaentreosvértices1e2éde1.5kmeavelocidademédia                       
no trecho é de 40km/h. 
4.Instância do problema: um arquivo contendo vários instâncias a serem                   
solucionadas. 
a.Nome do arquivo: INST_10, noqualNUMéuminteiroqueinformao                         
número de vértices do grafo; 
b.Cada linha fornece um problema a ser solucionado, no qual o                     
primeironúmeroéopontoinicialeosegundonúmeroéodestino,                       
porexemplo:110seualgoritmodevepartirdovértice1echegar                       
ao vértice 10. 
 
 
 
 
 
 
PROBLEMA 3: REDE DE COMPUTADORES 
 
Descrição 
Umdosproblemasemredesdecomputadoresestárelacionadooenviodepacotes                        
paraumservidor.Paraestasolução,várioscomputadoresestãoconectadosaum                      
switch, que por sua vezpodecomunicar­secomoutroswitcheestabeleceruma                         
comunicação até que o pacote seja enviado ao servidor. 
 
Seu algoritmo deve solucionar tal problema conhecido como Spanning Tree que                     
deve prover o melhor caminho para conectar todos os nós (switches) ao                       
servidor. Vale ressaltar que um nó pode receber pacotes de quantos nós for                         
possível. O custo para enviar o nó de um vértice para outro é sempre 1. 
 
Exemplo de entrada 
Dois arquivos serão fornecidos: 
5.Instânciadografo:umarquivocontendotodasasinformaçõesarespeito                    
do grafo. 
a.Nomedoarquivo:GRAPH_NUM,noqualNUMéuminteiroqueinformao                       
número de vértices do grafo; 
b.Cada linha do arquivo fornece as informações sobre o vértice de                     
origem e o vértice destino; 
c.Um exemplo de instância é a linha: 1 2 significa que existe uma                         
conexãoentreovértice1eovértice2decusto1,comodescrito                         
anteriormente. 
6.Instância do problema: um arquivo contendo vários instâncias a serem                   
solucionadas. 
a.Nome do arquivo: INST_10, noqualNUMéuminteiroqueinformao                         
número de vértices do grafo; 
b.Cadalinhaforneceumproblemaasersolucionado,noqualonúmero                     
fornecido é o servidor para o qual os pacotes serão enviados.