Mon fils de 8 ans s'est ennuyé à créer des labyrinthes conventionnels et a commencé à créer des variantes qui ressemblent à ceci:
L'idée est de partir de x et d'atteindre o via les règles normales. De plus, vous pouvez "sauter" de tout entier à tout autre entier , mais vous devez payerdollars pour le privilège. Le but est de résoudre le labyrinthe au moindre coût. Dans l'exemple ci-dessus, nous pourrions passer de x à o via x-14-18-27-28-o au coût 5, mais il est moins cher de passer x-13-11-9-8-29-28-o pour seulement 4.
Voici donc ma question: quelle est la meilleure solution (en termes de temps de fonctionnement asymptotique) à laquelle vous pouvez penser pour résoudre ce problème? Vous pouvez faire des hypothèses raisonnables sur le format d'entrée.
Remarque: J'utilise la balise "puzzles" ici parce que j'ai une réponse en tête, mais je ne suis pas sûr qu'elle soit optimale et j'aimerais voir si quelqu'un d'autre peut améliorer ma solution. (Ici est le nombre d'entiers dans le labyrinthe.)
Réponses:
Vous pouvez résoudre ce problème en utilisant une variante de l'algorithme de Dijkstra. Nous pouvons éviter de ne pas effectuer toutes les mises à jour de distance lorsque nous visitons un nouveau nœud. Si nous visitons un nœud , nous devons seulement mettre à jour les distances de tout ce qui peut être parcouru de à 0, et mettre à jour les distances aux deux nœuds et avec les valeurs les plus proches de inférieures et supérieures à qui ne l'ont pas été encore choisi.O(nlogn) y y y− y+ y y
Ces mises à jour sont suffisantes pour garder le tas renvoyant l'élément minimum car tout nœud le plus proche vers lequel vous sautez doit avoir été numériquement juste au-dessus ou juste en dessous d'un nœud déjà visité.
Chaque nœud est mis à jour à 0 au plus une fois (si nous sortons tous les nœuds à distance nulle de la file d'attente pour éviter un comportement quadratique), et chaque fois que nous ajoutons un nœud, nous ne faisons O (1) que d'autres mises à jour. Trouver les valeurs et peut être fait en temps linéaire si nous gardons également une liste ordonnée à double liaison de tous les nœuds, triée par leurs valeurs entières. La création de cette liste à double liaison prend du temps , et enfin les mises à jour et les sauts du tas prennent du temps , pour un temps d'exécution total dey− y+ O(nlogn) O(n) O (nlogn) O(nlogn)
la source
Je pense que pourrait être le meilleur que vous puissiez obtenir.O(n2)
Il semble naturel de convertir cela en un problème de chemin le plus court avec un nœud de départ spécial (x) et un nœud de fin (0). Il y aurait également un autre nœud pour chacun des nombres. Les deux x et 0 ont des bords de poids 0 à tous les nœuds numériques qui sont accessibles dans le labyrinthe. Tous les nœuds numériques sont connectés soit avec un poids 0 (si les nombres sont accessibles en labyrinthe), soit avec la différence entre les nombres (si ce n'est pas le cas avec le labyrinthe).
Le chemin le plus court dans ce graphique ne peut pas être résolu en moins de car le graphique a à peu près n 2 arêtes et, dans le pire des cas, il faudrait voir chaque cas une fois. En tant que tel, l'algorithme de Dijkstra'a pour le chemin le plus court prend du temps O ( n 2 ) et est optimal dans le pire des cas.O(n2) n2 O(n2)
la source