Ce problème de déplacement optimal dans les délais est-il dur pour les arbres?

Un de mes amis me pose le problème de planification suivant sur l'arbre. Je trouve que c'est très propre et intéressant. Y a-t-il une référence pour cela?

Problème: Il y a un arbre , chaque arête a un coût de déplacement symétrique de 1 . Pour chaque sommet , il existe une tâche qui doit être effectuée avant son échéance . La tâche est également désignée par . Chaque tâche a la valeur uniforme 1. Le temps de traitement est de 0 pour chaque tâche , c'est-à-dire que la visite d'une tâche avant son échéance équivaut à sa fin. Sans perte de généralité, soit la racine et en supposant qu'il n'y a pas de tâche située à . Il y a un véhicule à $T(V,E)$ $v_i$ $d_i$ $v_i$ $v_0$ $v_0$ $v_0$ au temps 0. Par ailleurs, nous supposons que pour chaque sommet $d_i \ge dep_i$ , représente la profondeur de . Cela va de soi, le sommet avec une échéance inférieure à sa profondeur doit être considéré comme aberrant. Le problème demande de trouver une planification qui termine autant de tâches que possible. $dep_i$ $v_i$

Le progrès:

Si l'arborescence est limitée à un chemin, elle se trouve alors en via une programmation dynamique. $\mathsf{P}$
Si l'arbre est généralisé à un graphe, alors il est en complet. $\mathsf{NP}$
J'ai un algorithme gourmand très simple que l'on croit apporoximation à 3 facteurs. Je ne l'ai pas complètement prouvé. Maintenant, je suis plus intéressé par les résultats NP-hard. :-)

Merci pour vos conseils.

ds.algorithms graph-algorithms np-hardness Peng Zhang
la source

Sur un graphique complet, la tâche serait facile non? Utilisez simplement un algorithme simple et gourmand ...

Joe

@Joe: Oui. Parce que chaque bord a besoin d'une unité de déplacement, il n'y a donc aucune préférence parmi les "carrefours". Êtes-vous toujours intéressé par ce problème, si oui. nous pouvons peut-être parler par e-mail. :-)

Peng Zhang

Et si tous les délais sont les mêmes et / ou si nous demandons seulement si toutes les tâches peuvent être terminées?

domotorp

@domotorp: S'il demande de terminer toutes les tâches avec un seul délai, la réponse est OUI si et seulement si le délai uniforme

. Juste une première recherche approfondie. Quant au problème optimal sur le cas

, Je ne sais pas si c'est facile. Il existe de nombreuses variantes à ce problème, par exemple en considérant si les délais prennent des valeurs à partir d'un ensemble fini dont la cardinalité est une constante? Merci beaucoup pour votre commentaire.

d \geq | V |

$d\ge |V|$

d < | V |

$d< |V|$

Peng Zhang

Je dirais NP-difficile de voir le zoo de programmation , sauf si j'ai mal compris votre problème.

Gopi

Réponses:

Pas sûr que ce soit votre réponse (voir ci-dessous) mais un peu trop long pour les commentaires.

Je pensais que votre problème était quelque chose comme: $(P|tree;p_i=1|\Sigma T_i)$ , où:

représente des processeurs homogènes identiques, $P$
"arbre" signifie contrainte de priorité sous la forme d'un arbre,
représente le poids des tâches est égal à 1, et $p_i=1$
signifie minimiser la somme des retards (c'est-à-dire le nombre de tâches qui se terminent après leur échéance). $\Sigma T_i$

Si tel est le cas, votre problème est NP-difficile: vous pouvez le voir comme une généralisation de la minimisation du retard total sur une seule machine avec des contraintes de priorité . En effet, cet article indique que pour plusieurs chaînes linéaires, il est NP-dur sur un seul processeur. La transformation facile consiste à prendre les arbres de la forme une racine et les chaînes linéaires à partir de la racine.

Cependant, je suis surpris parce que vous semblez dire que pour le cas d'une seule chaîne linéaire, vous utiliseriez la programmation dynamique. Je ne vois pas pourquoi vous auriez besoin de DP, car il me semble que lors de la programmation d'une seule chaîne linéaire, vous n'avez pas beaucoup de choix en raison des contraintes de priorité: un seul choix. Alors j'ai peut-être mal compris votre problème.

Gopi
la source

Mon problème semble différent du vôtre. Le mien est "un arbre enraciné, un temps unitaire de coût de déplacement, chaque sommet avec une tâche avec son échéance, la tâche n'a pas besoin de temps pour précessionner. A partir de la racine, combien de tâches peuvent être terminées?". Il n'y a donc pas de priorité, il n'y a pas de temps nécessaire pour traiter une tâche. Merci beaucoup.

Peng Zhang

@PengZhang, S'il s'agit d'un arbre enraciné, alors il y a priorité? Quant au coût sur les bords (priorité?) Ou sur les tâches, il me semble que c'est la même chose. Je ne vois vraiment pas la différence entre les deux. Enfin, combien de tâches peuvent être terminées, si vous minimisez le nombre de tâches qui se terminent après leur échéance, cela revient à maximiser le nombre de tâches qui peuvent être terminées. Peut-être pourriez-vous dessiner une image de ce que vous attendez?

Gopi

Je ne vois pas la relation claire entre deux problèmes. Dans le problème d'origine, le coût de la visite d'un nœud suivant dépend du nœud visité à l'étape précédente. Dans la planification avec priorité de priorité, le coût d'un prochain travail à traiter ne dépend pas du travail qui a été traité à l'étape précédente, tant que la contrainte de priorité est satisfaite.

Yoshio Okamoto

1, 2, \dots, n

$1,2,\cdots, n$

f (t, l, r)

$f(t,l,r)$

[l, r]

$[l,r]$

t

$t$

l

$l$

g (t, l, r)

$g(t,l,r)$ désignent la même chose que

sauf que le véhicule se trouve à

f (t, l, r)

$f(t,l,r)$

r

$r$

f (t, l, r)

$f(t,l,r)$

{f (\cdot, l + 1, r), g (\cdot, l, r - 1)

$\{f(\cdot,l+1,r), g(\cdot,l,r-1)$

t, l, r

$t,l,r$

Peng Zhang

@PengZhang, ok, je pense avoir une meilleure compréhension de ce que tu veux dire. Je crois toujours que l'on peut facilement adapter le papier que j'ai donné, en considérant des arbres spéciaux où les branches sont des chemins (d'où des chemins enracinés).

Gopi

Pour que cela soit vrai, nous devons faire quelques hypothèses. Voir les commentaires ci-dessous

$t_a$ $t_b$

$|V|$

Joe
la source

Pouvez-vous me montrer la récurrence? J'ai essayé la même chose que la vôtre avant, que

f [a, t, t^{'}]

$f[a, t, t']$

a

$a$

[t, t^{'}]

$[t,t']$

a

$a$

le point (1) n'est pas autant un problème que le point (2). Pour que mon idée fonctionne comme je l'avais envisagée pour la première fois, il faut que vous ne quittiez pas et que vous n'entriez pas plusieurs fois dans un sous-arbre. Il n'est pas évident que la meilleure solution ne saute pas tout autour de l'arbre: obtient une feuille et quelque chose près de la racine et marche vers une feuille, puis vers une autre feuille loin des 2 autres, etc. Vous pourriez peut-être d'exploiter le fait que vous obtiendrez tous les nœuds sur n'importe quel chemin que vous parcourez. En particulier, si un enfant a été visité, le parent est déjà visité.

Joe

: Dans ma pensée, le point (1) est en effet un problème . Pour le point (2), j'ai appelé la contrainte "pas de retour" comme contrainte "Depth First Search". La contrainte DFS est couramment adoptée dans les littératures. Et sous cette contrainte, mon problème est bien polynomial, tant que le degré maximum de l'arbre est une constante . Je me demande donc que ma question est NP-difficile. Merci beaucoup.

Peng Zhang

Concernant la contrainte DFS, il est facile de construire un exemple où la séquence optimale viole cette contrainte. Considérons un arbre binaire complet et équilibré avec 7 nœuds. Laissez les 2 feuilles dans le sous-arbre gauche avoir les délais 2 et 12, les 2 feuilles dans le sous-arbre droit ont les délais 8 et 6 et les nœuds internes ont les délais 100. Vous pouvez visiter tous les nœuds en visitant les feuilles dans l'ordre 2,6,8 , 12; toute autre commande viole au moins un délai.

mhum

Le problème d'obtenir une approximation constante pour ce cas ou de le prouver NP-Hard est toujours ouvert et tout résultat ferait une bonne publication. Certains cas spéciaux ont été résolus. Avec d'autres, j'ai des résultats partiels qui résolvent des cas spéciaux comme les araignées, les arbres à hauteur constante. Mais, le problème général des arbres n'est pas résolu.

vgta
la source