Maratona de Filmes
Autores:

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 41 3 1 2 11 13 314 15 310 16 210 14 111 17 211 14 313 15 314 15 112 16 412 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

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

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

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

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.