Le Père Noël peut-il être à la fois juste et efficace?

Comme le montre le réseau à feuilles persistantes The Physics of Santa , il est physiquement impossible pour le Père Noël d'offrir un cadeau à tous les enfants de la planète. Planification d' itinéraire ne sera pas beaucoup d' aide là - bas, mais peut un bon algorithme de planification au moins faire en sorte que chaque enfant reçoit un cadeau de temps en temps en Père Noël aussi sert autant d'enfants que possible chaque année?

Considérons un graphique complet avec des poids réels réels et un constant . Nous voulons résoudre une variante du problème des vendeurs itinérants:$k$

Existe-t-il un itinéraire circulaire de longueur au plus qui dessert plus de nœuds?$k$$m$

La version d'optimisation serait:

Maximisez le nombre de nœuds qui peuvent être desservis avec un itinéraire circulaire de longueur au plus .$k$

Cela est motivé par les limitations réelles des itinéraires: le Père Noël a une nuit pour livrer autant de cadeaux que possible, un vendeur a huit heures pour l'itinéraire d'un jour, etc.

La première question, mais pas la dernière, est: à quel point ce problème est-il difficile? Supposons que nous pouvons commencer à n'importe quel nœud, mais cela ne devrait pas faire trop de différence.

Maintenant, afin de modéliser l'équité, supposons qu'il existe nœuds et que nous pouvons visiter au plus à chaque visite. Idéalement, nous voudrions que chaque nœud soit visité fois au cours de visites efficaces. Puisqu'il peut y avoir des nœuds goulots d'étranglement qui doivent être visités plus souvent afin d'assurer que les itinéraires visitent de nombreux nœuds, certains devront inévitablement être visités moins souvent. Cela exclut également l'approximation triviale de la suppression des nœuds une fois visités jusqu'à ce que tous aient été visités.$N$$M$$t\cdot\frac{M}{N}$$t$

Voici donc la dernière question. Soit le nombre de tours nécessaires jusqu'à ce que tous les nœuds aient été visités par des tours efficaces . Comment déterminer algorithmiquement la valeur minimale de (et toutes les routes nécessaires)? Quelle est la complexité de ce problème?$T$ $k$$T$

Je suppose que c'est vraiment un problème multi-critères: chaque visite doit visiter autant de nœuds que possible alors que nous voulons garder les visites aussi disjointes que possible.

Je suis un peu confus. Si est une constante, alors vous pouvez essayer tous les tours possibles. Le problème est donc dans .$k$$O(n^k)$${\sf P}$

Cependant, si fait partie de l'entrée, le problème de décision est -complete. Cela peut être montré en réduisant au problème, par la réduction suivante.$k$${\sf NP}$$\text{HAM-CIRCUIT}$

Supposons que nous voulons déterminer si un graphe -vertte a un circuit hamiltonien. Ensuite, nous prenons le graphe complet avec la fonction de distance suivante De plus, nous choisissons et .$n$$G$$K_n$

Permettez-moi de vous expliquer pourquoi il s'agit d'une réduction. Si$G$ a un circuit hamiltonien, alors il y a une tournée$K_n$ avec longueur $n$. En d'autres termes, un itinéraire circulaire de longueur$\le n$ qui sert $> (n-1)$nœuds. D'un autre côté, s'il y a un Santa-tour qui visite$>(n-1)$Les nœuds doivent visiter tous les nœuds. Puisque le tour du Père Noël ne peut avoir qu'une longueur$\le n$ et chaque longueur de bord est d'au moins 1, tous $n$ les bords de cette tournée ont une longueur 1. Par conséquent, cette tournée correspond à un circuit hamiltonien $G$.