• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

20_LESI

Problema NP-completo

8 mensagens neste tópico

Não sabia bem em que secção colocar esta questão, mas a complexidade da mesma, bem como o facto de não ser bem uma dúvida, pois ainda só perdi tempo no planeamento desta questão, levou-me a colocar este problema nesta secção, em vez de o colocar numa outra de dúvidas!

Vou começar por contextualizar... Trata-se de umas alíneas do meu trabalho de Algoritmos e Complexidade, uma das cadeiras TOP do meu curso! Consiste na implementação de um programa que receba uma lista de alunos, contendo a média e outros parâmetros dos alunos, e que realize uma alocação dos mesmos aos 16 mestrados que temos à escolha. A primeira fase (já implementada e a funcionar), consiste numa alocação simples, tendo em conta apenas os factores de decisão para a alocação dos alunos.

Após algumas operações que não interessam para o problema que apresentei, fiquei com os alunos guardados numa AVL, e depois foi só colocá-los nas diversas UCEs (usei um array de 16 estruturas UCEs, contendo em cada posição, uma lista ligada de alunos e um inteiro com o número de vagas) para realizar esta alocação. De notar que cada aluno tem associada uma lista de pares do tipo:

1. Sistemas de Suporte à Decisão

1. Criptografia

2. Engenharia de Planeamento

2. Metodos Formais

2. Sistemas de Suporte à decisão

3. Computação gráfica

4. BioInformatica

5. Programação Certificada

6. Computação Movel e Ubíqua

6. Um riso qualquer de mestrado

Agora vem a parte complicada... Após esta primeira alocação, temos de realizar uma alocação definitiva, tendo agora em conta o dia da semana em que irá funcionar cada UCE:

-> Considerando que em cada dia da semana não poderão funcionar mais de 4 UCEs

-> Um aluno não poderá frequentar duas UCEs no mesmo dia

Tenho de realizar esta alocação, garantindo que sejam efectuadas o mínimo de alterações possíveis à primeira alocação. Se isto não for considerado um problema NP-completo, peço desculpa! Mas ao implementar a primeira fase do trabalho, fiquei sem tempo para estudar esta parte da matéria...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sinceramente não percebi bem o problema, nomeadamente: o que é uma UCE? O que é aquela lista?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu acho que não se enquadra na secção pois não tens a solução do desafio. É mais um pedido de ajuda.

Partes de alguns pressupostos como sabermos o que é um problema NP-Completo, AVL e UCE. Eu sei o que são os dois primeiros mas UCE não faço ideia, cada UCE é um mestrado?

O problema parece semelhante ao problema de alocação de professores (que é NP-completo). Mas não descreveste suficientemente bem os critérios de alocação para aferir esta questão correctamente. Isso em prolog usando restrições até nem era dificil de resolver, mas acho que não dava para minimizar o número de alterações à alocação inicial. Esta alocação é greedy?

PS: qual é a vantagem em ter uma AVL com os alunos?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sinceramente não percebi bem o problema, nomeadamente: o que é uma UCE? O que é aquela lista?

Cada mestrado é denominado de UCE! Aquela lista indica a ordem de preferências do candidato! Neste caso, se ele tivesse média, e tivesse concorrido a duas UCEs, iria ser alocado em Sistemas de Suporte à Decisão e Criptografia. Caso não tivesse média, íamos às UCEs com preferência imediatamente a seguir (2) procurar uma UCE em que o pudessemos alocar

O problema parece semelhante ao problema de alocação de professores (que é NP-completo). Mas não descreveste suficientemente bem os critérios de alocação para aferir esta questão correctamente.

Desconheço esse problema, até porque o meu conhecimento destes problemas é muito pequeno! Que mais dados preciso de enunciar?

Isso em prolog usando restrições até nem era dificil de resolver, mas acho que não dava para minimizar o número de alterações à alocação inicial. Esta alocação é greedy?

PS: qual é a vantagem em ter uma AVL com os alunos?

O trabalho é em C! Um algoritmo greedy é um que resolva o problema, "no matter what", certo? Penso que não seja o ideal...

A vantagem da AVL é poder tê-los ordenados! Quando vou alocar os alunos às variadas UCEs, é so percorrer a AVL da direita para a esquerda

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ou seja, se ele tiver média, vai ser colocado em todos os número 1, senão, em todos os número 2, etc?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O trabalho é em C! Um algoritmo greedy é um que resolva o problema, "no matter what", certo? Penso que não seja o ideal...

Aproveitando um antigo post:

Greedy algorithm não é um algoritmo por si só. É uma técnica de concepção de algoritmos.

Um algoritmo é ganancioso (greedy) se em cada passo da sua execução explora apenas uma opção (que é a opção correcta com vista a obter a solução óptima).

Exemplo recente dum problema do google code jam:

Dados 2 vectores de inteiros, encontrar uma permutação de cada vector de modo a minimizar o seu produto escalar. Neste caso, basta ordenar um vector de forma ascendente e outro de forma descendente e efectuar o produto escalar.

Ou seja, um exemplo seria fazer uma alocação gananciosa por média (colocar o aluno com melhor média no UCE que quer, depois o 2º melhor, etc) e depois tentar melhorar essa colocação para satisfazer aquelas 2 restrições que referiste.

Quanto ao problema da colocação de professores (enganei-me ao escrever "alocação"), podes ver na página 22 destes slides uma descrição do problema.

O que falta saber é aquilo que o Warrior perguntou...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ou seja, se ele tiver média, vai ser colocado em todos os número 1, senão, em todos os número 2, etc?

Não. Cada candidato pode candidatar-se a uma ou duas UCEs. Em cada estrutura do tipo aluno guardo essa parametro. Imaginemos que ele se candidata apenas a uma UCE e apresenta a lista que apresentei em cima, não tendo média para as UCEs com preferência 1. Em seguida o programa procura nas UCEs com preferência 2, para ver se pode alocar lá o aluno. Se não conseguir, avança para as UCEs com preferência 3. E assim em diante, até conseguir alocar o aluno, ou até chegar ao fim da lista de preferências, não tendo o aluno sido alocado.

Ou seja, um exemplo seria fazer uma alocação gananciosa por média (colocar o aluno com melhor média no UCE que quer, depois o 2º melhor, etc) e depois tentar melhorar essa colocação para satisfazer aquelas 2 restrições que referiste.

Antes do tal melhoramento, o que definiste foi a alocação provisória, que já está implementada. Falta a parte do melhoramento, que tem obrigatoriamente de ser posterior, havento a tal fase intermédia.

Quanto ao problema da colocação de professores (enganei-me ao escrever "alocação"), podes ver na página 22 destes slides uma descrição do problema.

Uma vista de olhos rápida levou-me a crer que seja basicamente o mesmo! Vou ler melhor, e já aqui venho dizer algo...

[EDIT] É semelhante, mas apenas com a primeira fase do meu trabalho, a tal alocação provisória.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu não vejo nada melhor do que brute-force - uma função recursiva a experimentar colocar os alunos e ficar com a solução que minimiza o número de alterações.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora