Algorithme D'Ordonnancement Le Mieux Adapté
j'écris une émission avec un problème de programmation difficile. Il y a plusieurs événements, chacun avec plusieurs heures de réunion. Je dois trouver un arrangement des temps de réunion de sorte que chaque horaire contient n'importe quel événement donné exactement une fois, en utilisant un des temps de réunion multiples de chaque événement.
Évidemment, je pourrais utiliser la force brute, mais c'est rarement la meilleure solution. Je suppose que c'est un problème informatique relativement basique, que j'apprendrai une fois Je suis capable de commencer à prendre des cours d'informatique. En attendant, je préférerais n'importe quels liens où je pourrais lire sur ceci, ou même juste un nom que je pourrais Google.
4 réponses
je pense que vous devriez utiliser l'algorithme génétique parce que:
- il est le mieux adapté pour les grandes instances de problème.
- Il produit de la réduction du temps de la complexité sur le prix de la réponse inexacte(Pas l'ultime best)
- vous pouvez spécifier des contraintes et des préférences facilement en ajustant des punitions de fitness pour ceux qui ne sont pas rencontrés.
- vous pouvez spécifier le délai d'exécution du programme.
-
la qualité de la solution dépend de combien de temps vous avez l'intention de passer à résoudre le programme..
Algorithmes Génétiques Définition
il y a plusieurs façons de le faire
Une approche consiste à faire de programmation par contraintes. C'est un cas particulier de la programmation dynamique suggérée par feanor. Il est très intéressant d'utiliser une bibliothèque spécialisée qui peut faire le cadre et la ramification pour vous. (Google pour "Gecode" ou "comet-online" pour trouver des bibliothèques)
si vous êtes mathématiquement incliné alors vous pouvez également utiliser la programmation entière pour résoudre le problème. L'idée de base ici est de traduire votre problème en un ensemble d'inégalités linéaires. (Google pour "programmation entière de programmation" pour trouver de nombreux exemples de la vie réelle et google pour "Abacus COIN-ou" pour une bibliothèque utile)
ma conjecture est que la programmation contrainte est l'approche la plus facile, mais la programmation entière est utile si vous voulez inclure des variables réelles dans votre problème à un moment donné.
votre Description du problème n'est pas tout à fait claire, mais si tout ce que vous essayez de faire est de trouver un horaire qui n'a pas d'événements se chevauchant, alors c'est un problème simple correspondance bipartite .
vous avez deux ensembles de noeuds: événements et temps. Tracer le bord de chaque événement, à chaque heure de la réunion. Vous pouvez alors construire efficacement la correspondance (le plus grand ensemble possible d'arêtes entre les noeuds) en utilisant chemins augmentés . Cela fonctionne parce que vous pouvez toujours convertir un graphe biparti dans un équivalent graphique de flux.
un exemple de code qui fait cela est BIM . Les bibliothèques graphiques Standard telles que GOBLIN et NetworkX ont également des implémentations bipartites de mise en correspondance.
cela ressemble à cela pourrait être un bon candidat pour une programmation dynamique solution, spécifiquement quelque chose de similaire à la programmation d'intervalle problème.
Il y a quelques visuels ici pour l'intervalle problème de programmation particulier, ce qui peut rendre le concept plus clair. ici est un bon tutoriel sur la programmation dynamique globale.