Algoritmo para uma ferramenta de planejamento

Question

Eu estou escrevendo um pequeno aplicativo de software que precisa servir como uma ferramenta de planejamento simples para uma escola local. O 'problema' que precisa resolver é bastante básico. Ou seja, os professores precisam de falar com os pais de todas as crianças. No entanto, algumas crianças têm, é claro, irmãos e irmãs em diferentes grupos, de modo que essas negociações precisam ser agendadas lado uns dos outros, para evitar as situações foram pais têm uma conversa às 6 da tarde e outra às 10 horas. Assim, em suma, dada uma coleção de n crianças, onde algumas crianças têm 1 ou mais irmãos ou irmãs, gerar uma agenda onde todas as conversas dessas crianças são planejadas ao lado do outro.

Agora, talvez o problema pode ser resolvido extremamente fácil, mas por outro eu tenho um sentimento que este pode ser um problema bastante complicado, que as necessidades e pode ser resolvido com algum tipo de algoritmo. Elegantemente. Mas estou certo? Existe? Eu olhei para o Húngaro alorithm mas não chega a aplicar a este problema particular.

Edit:. Eu esqueci de mencionar, que todas as negociações de ter a mesma quantidade de tempo

Obrigado!

Answer 1

Eu acho que é bastante fácil.

primeiro grupo as crianças que pertencem juntos, porque eles compartilham os pais. Agendar as crianças dentro de um grupo consecutivamente, agendar o resto como aleatório.

Outra forma de abstrair-lo e tornar o problema mais fácil é olhar a partir da perspectiva dos pais, ver irmãos e irmã como "criança" e dar-lhes mais tempo. Depois, é só agendar os pais de forma aleatória, mas alguns precisam de mais tempo (porque eles têm vários childeren).

Answer 2

Uma abordagem woul dbe para definir o problema em uma linguagem declarativa restrição e, em seguida, deixá-lo resolver o problema para você. A última vez que fiz isso, eu usei Eclipse , que é uma linguagem pouco bacana onde você define o seu espaço do problema por restrições e depois deixá-lo encontrar valores permitidos que satisfazem essas restrições.

Por exemplo, eu acredito que você tem duas classes de restrições:

1. Um professor pode ter apenas uma conferência em um momento
2. Todos os alunos na mesma must família têm slots consecutivos

Depois de definir estes em Eclipse, ele irá calcular valores para cada aluno que satisfazem os requisitos. Se você percorrer esse caminho, você também pode facilmente adicionar restrições como você precisa. Por exemplo, é fácil dizer que um ensina não está disponível para ranhura Y, ou os professores devem se revezam fazendo trabalho administrativo, etc.

Answer 3

Isso classifica sente como um tipo de "algoritmo mochila" do problema. Você precisa agrupar os membros de uma família, em seguida, preencher as vagas de forma adequada.

Se você google "algoritmo mochila", você verá o suficiente write-ups para fazer girar a cabeça e também alguns bons codificado soluções.

Answer 4

Eu acho que se cada palestra poderia ser reduzido a "atividades" em que cada atividade tem um tempo de início e uma hora de fim você poderia usar o algoritmo de seleção de atividade estudados em ciência da computação. Ele baseia-se numa abordagem ávido e poderia ser resolvido em O (n) (em que n é o número de actividades). Você pode encontrar mais informações aqui . Tenho certeza que você vai precisar de ter que fazer um pré-processamento aqui para ser capaz de reduzir a emissão irmão / irmã como actividades do mesmo tipo.