Maratona de Filmes

Autores:

michael_jackson

Introdução

Você quer passar todos os dias de um final de semana assistindo ao máximo de filmes possível, mas há restrições quanto aos horários disponíveis e ao número de títulos que podem ser vistos em cada categoria, como por exemplo comédia, drama, ação, etc.

Inputs

Os inputs para esse projeto seguem a estrutura a seguir:

10 4
1 3 1 2
11 13 3
14 15 3
10 16 2
10 14 1
11 17 2
11 14 3
13 15 3
14 15 1
12 16 4
12 13 4
  • a primeira linha indica que há 10 filmes a serem considerados e 4 categorias;
  • a segunda linha indica qual o máximo de filmes que cada categoria pode ter;
  • da terceira linha em diante você vai encontrar os n filmes, suas respectivas hora de início, hora de término e categoria pertencente.
📚

Para mais detalhes sobre como geramos nossos inputs, clique aqui.

Heurística Gulosa

duck_donald

A primeira etapa do nosso projeto consiste na implementação de uma heurística gulosa (greedy) para a escolha dos filmes.

Ela ordena os filmes por hora de fim crescente e escolhe aqueles que começam primeiro e não conflitam com os filmes já escolhidos, além de verificar se há vagas disponíveis na categoria do filme.

📚

Para mais detalhes sobre a heurística gulosa implementada, clique aqui.

Aleatorização

dices

A aleatoriedade é uma estratégia bastante comum para construção de algoritmos de busca local, podendo ser usada de forma isolada ou de forma complementar a outra estratégia de varredura de um espaço de soluções.

Assim, a segunda parte do projeto consiste na adaptação da heurística gulosa para incluir aleatoriedade, de forma que durante a seleção de um filme tenhamos 25% de chance de selecionar um filme aleatório que respeite os horários disponíveis.

📚

Para mais detalhes sobre a implementação da aleatorização clique aqui.

Busca Exaustiva

exhausted

A terceira etapa do projeto consiste na implementação de um algoritmo de busca exaustiva para encontrar a melhor solução possível para o problema.

Para isso, geramos todas as possíveis combinações de filmes que podem ser assistidos, fazemos isso com um for loop que vai de 0 até 2^N, onde N é o número de filmes. Para cada número gerado, convertemos ele para binário e verificamos se a permutação atual é válida, ou seja, se não há conflitos de horário entre os filmes e se não há mais filmes do que o permitido em cada categoria. Caso a permutação seja válida, ela é adicionada a um vetor de permutações válidas. Então verificamos qual é aquela que tem o maior número de filmes assistidos e retornamos ela como a melhor solução.

📚

Para mais detalhes sobre a implementação da paralelização clique aqui.

Comparação de resultados

king_kong_godzilla

Por fim, a última etapa desse projeto se concentra em analisar o desempenho dos dois algoritmos criados nas duas partes

Parte 1: Heurística Gulosa (greedy) vs Aleatorização (randomness)

Quando testamos diferentes inputs, variando tanto a quantidade de filmes, quanto a quantidade de categorias. Para isso geramos uma série de inputs, com diferentes quantidades de filmes e categorias e gráficos para comparar os resultados dos algoritmos. Além de realizar o profiling dos algoritmos, para verificar onde eles gastam mais tempo.

📚

Para mais detalhes sobre o desempenho dos algoritmos da parte 1, clique aqui.

Parte 2: Comparação de Busca Exaustiva Entre Paralelismos (CPU vs GPU)

A segunda parte da comparação de resultados consiste em comparar o desempenho do algoritmo sem paralelisação de busca exaustiva e paralelizados com OpenMP e Thrust. Para isso, geramos uma série de inputs, com diferentes quantidades de filmes e categorias, gerando um output com a quantidade de filmes que podem ser encaixados na agenda. A partir dos outputs, foram gerados gráficos para comparar os resultados da performance dos algoritmos.

📚

Para mais detalhes sobre o desempenho dos algoritmos da parte 2, clique aqui.