Trabalho Ciência da Computação

[pic 1]

                        

INSTITUTO FEDERAL DE MINAS GERAIS

Bacharelado em Ciência da Computação

Disciplina: Matemática Discreta

Trabalho Prático 01

Professor: Diego Mello da Silva

                Integrantes:         Alessandro Kennedy                     0026898

                                            Igor Wagner                                  0026496

                                            Patrícia Pieroni                             0011334

                                             Pedro Veloso                                 0002346

Formiga-MG

26 de novembro de 2016

Sumário

1. Instruções
2. Sub-rotinas: Funções e procedimentos
3. Comentários
4. Resultados

1)  Instruções

Este trabalho visa apresentar soluções do problema clássico em teoria de grafos,  conhecido por Problema de Cobertura de Vértices (PCV). Esse é um problema de otimização combinatória, o qual, consiste em computar qual é a menor cobertura de vértices do grafo G informado como entrada. Para a resolução do PCV, utilizamos o Método Guloso e o Aproximado

Os dados dos grafos de entrada, foram disponibilizados pelos benchmarks, o qual, consiste em conjuntos de instâncias para um dado problema combinatório onde são disponibilizados arquivos de entrada, valores ótimos (quando conhecidos) para cada entrada, ou melhor resultado documentado. 

Para a compilação do código via terminal, deve-se abrir o terminal na pasta onde se encontra os arquivos vcp-solver.pas, o arquivo de entrada desejado (instância) e o script run.sh, já no terminal, deve-se realizar os seguintes passos para a compilação:        

        . Digite fpc vcp-solver.pas e compile;

        . Após, digite ./run.sh;

O arquivo run.sh, é onde esta sendo estipulado a quantidade de repetições desejadas, qual a instância de grafo e algoritmo utilizado, sendo definidos por uma váriavel ‘g’, para o guloso e ‘a’ para  o  aproximado , nele, é tambem definido o nome do arquivo de saída de texto.

O ambiente de desenvolvimento utilizado para a codificação do algoritmo foi o free pascal, sendo compilado pelo terminal do Ubuntu Linux.

2) Sub-rotinas: Funções e procedimentos

Estrutura de dados:

• Matriz: grafo;
• Vetor: vertices,arestas,conjuto;
• Registro: aresta,vertice;

Sub-rotinas não utilizadas, mas implementadas :

• function copiarArestas(original : arestas): arestas;
• function uniaoVertices(conj1, conj2 : vertices): vertices;
• function uniaoArestas(conj1, conj2 : arestas): arestas;
• function diferencaVertices(conj1, conj2 : vertices): vertices;
• function diferencaArestas(conj1, conj2 : arestas): arestas;
• function selecaoVertices(conj : vertices; vIni, vFim : Integer): vertices;
• function selecaoArestas(conj : arestas; aIvIni, aIvFim, aFvIni, aFvFim : Integer): arestas;
• procedure mostrarGrafo(g : grafo);
• procedure saidaTerminal(nVertices, nArestas, semente, cover : int64; heuristica, arquivo, saida : String);

Sub-rotinas utilizadas:

• function lerArquivo(nome : String; var ver : vertices; var ar : arestas): grafo;
• function cardinalidadeArestas(conj : arestas): int64;
• function cardinalidadeVertices(conj : vertices): int64;
• function verticeMaiorGrau(g : grafo): int64;
• function aproximadoPCV(ar : arestas): conjunto;
• function gulosoPCV(g : grafo; ar : arestas): conjunto;

3) Comentários

Sub-rotinas não utilizadas:

• Função para copiar arestas.

[pic 2]

• Procedimento para mostrar o Grafo: este procedimento mostra os valores do grafo.

[pic 3]

• Função para realizar a união de vértices e função para realizar a união de arestas: Primeiramente define o tamanho do vetor do conj3, o qual, no caso é o vetor união do conj1 e conj2. Após definido  o tamanho do vetor conj3, este vai receber o id e verificar se o conj1 ou conj2 pertencem, se sim, o conj3 na determinada posição ira receber 1.

[pic 4]

[pic 5]

• Função diferença de vértices e diferença de arestas:  Primeiramente, é setado o tamanho do conj3, que será o conjunto resultante da diferença entre o conj1 e conj2.

[pic 6]

[pic 7]

• Função para selecionar arestas.

[pic 8]

Sub-rotinas utilizadas

• Função para leitura do arquivo:  se o arquivo  passado como parametro não existe, uma mensagem de erro é informada ao usuário. Determina-se o caminho do arquivo e inicializa o contador de arestas, realizando a leitura do arquivo, verificando a linha inicial de comentário e desprezando essa, já pegando o numéro de vértices e arestas , salva o número de nós e arcos, assim atualizando os conjutos universos de vérices e arestas e determinando o tamanho da matriz do grafo. É tambem tratado o caso de erro se o grafo for 0x0. Se todas as arestas forem lidas é retornado o grafo.

[pic 9]

[pic 10]

• Funções para encontrar a cardinalidade de vértices e  arestas:  nestes métodos é verificado qual o tamanho do conjunto de vértices e do conjunto de arestas.

[pic 11]

[pic 12]

• Função para encontrar o vértice de maior grau: este método procura pelo maior grau no grafo e também se existem repetições, se sim é criado um vetor com os vértices repetidos, assim sorteia um dos vértices com o maior grau.[pic 13]

• Função Algoritmo Aproximado para PCV:  este algoritmo recebe o conjunto com todas as arestas do grafo. Enquanto houver uma aresta neste conjunto, ele sorteia uma delas e retira ela do conjunto universo. Os vértices que estavam ligados a essa aresta são adicionados ao conjunto solução e depois remove todas as arestas ligadas aos vértices removidos.

[pic 14]

• Função Algoritmo Guloso para PCV:  este algoritmo recebe o grafo em forma de matriz e o conjunto de arestas. A matriz é usada para determinar o grau de um vértice mais facilmente. De resto, é parecido com o algoritmo aproximado, porém, ao invés dele sortear uma aresta, esse pega o vértice de maior grau (ou sorteia entre os vértices de maior grau se houver mais de um ).[pic 15]

• Função saída do arquivo:  neste é definido como os dados serão demonstrados.

[pic 16]

Para a saída do arquivo tem de ser  informado a Instância,  que refere-se ao nome do arquivo que descreve o grafo correspondente,  nós e arcos , os quais, referem-se, respectivamente, ao número de nós e arcos do grafo,  a semente, que é o valor inteiro de semente informada pelo usuário que será usada para inicializar o gerador de números aleatórios, o método, caracter que indica qual método utilizar: ‘g’ para algoritmo guloso, ‘a’ para método aproximado e cover, que é a cobertura.

...