Classement topologique positif

Supposons que j'ai un graphe acyclique dirigé avec des pondérations en nombre réel sur ses sommets. Je souhaite trouver un ordre topologique du groupe de disponibilité de base de données dans lequel, pour chaque préfixe de cet ordre topologique, la somme des poids est non négative. Ou si vous préférez la terminologie théorique, j'ai un ordre partiel pondéré et je souhaite une extension linéaire telle que chaque préfixe ait un poids non négatif. Que sait-on de ce problème? Est-ce NP-complet ou soluble en temps polynomial?

Ce problème semble être très similaire à SEQUENCER POUR MINIMISER LE COÛT CUMULATIF MAXIMAL, problème [SS7] dans Garey & Johnson . En être témoin:

INSTANCE: Set des tâches, ordre partiel ≺ sur T , un "coût" c ( t ) ∈ Z pour chaque t ∈ T (si c ( t ) < 0 , il peut être considéré comme un "profit"), et constante K ∈ Z .$T$$\prec$$T$$c(t) \in Z$$t \in T$$c(t) < 0$$K \in Z$

QUESTION: Existe-t-il une planification à processeur unique pour T qui respecte les contraintes de priorité et qui a pour propriété que, pour chaque tâche t ∈ T , la somme des coûts de toutes les tâches t ′ avec σ ( t ′ ) ≤ σ ( t ) est au plus K ?$\sigma$$T$$t \in T$$t'$$\sigma(t') \leq \sigma(t)$$K$

Je suis certain que le problème reste NP-complet quand est fixé à 0. mention G & J que le problème reste NP-complet si c ( t ) ∈ { - 1 , 0 , 1 } pour tout t ∈ T .$K$$c(t) \in \{-1,0,1\}$$t \in T$

Eh bien, ma réponse est ma question à partir de laquelle il s'avère que si vous pouviez résoudre ce problème en P, vous pourriez également résoudre un autre problème ouvert: l' ordre topologique positif, prenez 3

Édition: Ce problème s’est également avéré être NP-complet; votre problème est donc déjà complet si votre DAG n’a que deux niveaux, c’est-à-dire s’il n’existe aucun chemin dirigé à deux arêtes.

Si je comprends bien le problème, je pense que le problème de planification lié à une seule machine contraint par la priorité afin de minimiser la somme pondérée des temps d’exécution (1 | prec | \ sum wc) peut être réduit au problème qui vous intéresse. Dans le problème 1 | prec | \ sum wc, nous avons n emplois, chacun avec un poids non négatif et un temps de traitement, un poset sur les emplois et nous souhaitons une extension linéaire des emplois telle que la somme pondérée des temps de réalisation des emplois minimisé. Le problème est NP-complet même si nous supposons que le temps de traitement de chaque travail est égal à 1. Cela a-t-il un sens?

Et si nous prenions toujours l'élément maximal (dans l'ordre partiel) avec le moins de poids. Après avoir épuisé les éléments, nous les renvoyons dans l'ordre inverse.

Ce problème me rappelle beaucoup d'arbres de décision. Je considérerais ce type de solution, qui essaie toujours de choisir le chemin le plus prometteur, mais en regardant le sous-graphique entier:

En partant de nœuds de puits, avancez vers les sources, un niveau à la fois. Pendant que vous faites cela, donnez un poids à chaque bord. Ce poids doit représenter le montant minimum que vous devrez "payer" ou "gagner" en parcourant le sous-graphe en partant du nœud vers lequel pointe le bord. Supposons que nous sommes au niveau i + 1 et que nous progressons vers le niveau i. Voici ce que je ferais pour attribuer un poids à une arête pointant vers un nœud de niveau i:

1. edge_weight = pointing_node_weight.
2. Trouver le bord à partir du "noeud de pointage" avec le poids maximal. Laissez ce poids être next_edge_weight.
3. edge_weight + = next_edge_weight

Ensuite, construisez la commande comme suit:

1. Soit S la frontière de recherche, c’est-à-dire l’ensemble des nœuds à sélectionner dans la suite.
2. Sélectionnez le noeud pour que (node_weight + maximum_edge_weight) soit maximisé.
3. Supprimez le nœud du graphique et S. Ajoutez les «enfants» du nœud à S.
4. Si le graphique n'est pas vide, passez à l'étape 1.
5. Arrêt.

L'idée est de parcourir ces sous-graphes qui donneront le plus grand gain possible en premier, afin de pouvoir supporter le coût des sous-graphes de poids négatif plus tard.