Recherche d'un sous-ensemble d'intervalles disjonctifs avec des poids maximaux

Question

Je cherche un algorithme que je pourrais utiliser pour résoudre ce problème, pas le code. Je me suis demandé comment utiliser la programmation linéaire avec la relaxation, mais peut-être y a-t-il des moyens plus efficaces pour résoudre ce problème?

Le problème

J'ai mis des intervalles avec des poids. Les intervalles peuvent se chevaucher. J'ai besoin de trouver la somme maximale des poids des sous-ensembles d'intervalles disjonctifs.

Exemple

Intervalles avec des poids:

|--3--|   |---1-----| 
    |----2--| |----5----|

Réponse: 8

Answer 1

J'ai un exact O (nlog n) DP algorithme à l'esprit.Comme ceci est un devoir, voici un indice:

Triez les intervalles par position du bord droit comme le suggère Saeed, puis numérotez-les de 1. Définissez f (i) comme étant le plus haut poids possible en utilisant seulement les intervalles qui ne le sont pas. étendre à droite du bord droit de l'intervalle i.

EDIT: Indice 2: Calculez chaque f (i) dans l'ordre croissant de i. Gardez à l'esprit que chaque intervalle sera présent ou absent. Pour calculer le score du cas "présent", vous devrez rechercher l'intervalle "le plus à droite" compatible avec l'intervalle i, ce qui nécessitera une recherche binaire à travers les solutions que vous avez déjà calculées.

C'était un trop grave, pas sûr que je peux donner plus d'indices sans totalement orthographe dehors;)

Answer 2

Vous pouvez formuler ce problème comme un problème général IP (programmation entier) avec des variables binaires indiquant si un intervalle est sélectionné ou non. La fonction objectif sera alors une combinaison linéaire pondérée des variables. Vous auriez alors besoin de contraintes appropriées pour imposer la disjonction entre les intervalles ... Cela devrait suffire compte tenu de l'étiquette homework. De même, tout simplement parce qu'un problème peut être formulé comme un programme entier (résolvant NP-Hard) cela ne signifie pas que la classe de problème elle-même est NP-Hard. Ainsi, comme le souligne Ulrich, il peut y avoir une formulation/algorithme polynomial-solvable tel que formuler/résoudre le problème en tant que programme linéaire.

Answer 3

S'il n'y a pas de poids, il est facile d'utiliser un algorithme glouton en triant les intervalles à leur heure de fin, et d'obtenir à chaque étape le plus petit intervalle possible.

mais dans votre cas je pense que c'est NPC (devrait y penser), mais vous pouvez utiliser un algorithme glouton similaire par Valeur chaque intervalle par Poids/Longueur, et chaque fois obtenir un des intervalles possibles en format trié, peut utiliser un recuit simulé, signifie chaque fois que vous obtiendrez la meilleure réponse par la valeur ci-dessus avec la probabilité P (p est proche de 1) ou sélectionnez un autre intervalle avec probabilité 1- P. vous pouvez le faire en boucle pendant n fois pour trouver une bonne réponse.

Answer 4

est ici une idée:

Tenir compte le graphique suivant: Créer un nœud pour chaque intervalle. Si l'intervalle I1 et l'intervalle I2 ne se chevauchent pas et que I1 vient avant I2, ajoutez un bord dirigé du nœud I1 au nœud I2. Notez que ce graphique est acyclique. Chaque noeud a un coût égal à la longueur de l'intervalle correspondant. Maintenant, l'idée est de trouver le chemin le plus long dans ce graphe, qui peut être trouvé en temps polynomial pour les graphes acycliques (en utilisant la programmation dynamique, par exemple). Le problème est que les coûts sont dans les nœuds, pas dans les bords. Voici un truc: divisez chaque nœud v en v 'et v' '. Toutes les arêtes entrant dans v entreront maintenant v 'et tous les bords quittant v quitteront maintenant v' '. Ensuite, ajoutez un bord de v 'à v' 'avec le coût du noeud, dans ce cas, la longueur de l'intervalle. Eh bien, si je ne me trompe pas, le plus long chemin dans ce graphique correspondra à l'ensemble des intervalles disjoints avec somme maximale.

Answer 5

solution correcte (bout à bout) est expliqué ici: http://tkramesh.wordpress.com/2011/02/03/dynamic-programming-1-weighted-interval-scheduling/