Je vais tenter de prouver mon algorithme est optimal.
L'algorithme est "prendre le train le plus rapide qui n'a pas de dépassement de votre destination".
Combien d'arrêts c'est un peu délicat.
Coder les deux arrêts comme des nombres binaires. Je demande que l'identique d'un préfixe peut être négligée; le problème de passer d' a de b est le même que le problème de passer d' a+2^n de b+2^n si 2^n > b, comme les arrêts entre 2^n et 2^(n+1) sont juste les arrêts entre 0 et 2^n changé au cours.
À partir de cela, nous pouvons réduire un voyage d' a de b garantir que le bit élevé de b est réglé, et le même "haute" peu d' a est pas définie.
Pour résoudre allant de 5 (101) à 7 (111), nous n'avons qu'à résoudre allant de 1 (01) 3 (11), puis shift notre arrêt des nombres jusqu'à 4 (100).
Pour aller d' x de 2^n + yoù y < 2^n (et donc de l' x est), nous voulons d'abord aller à l' 2^n, car il n'y a pas de trains qui saute 2^n qui ne sont pas aussi ignorer 2^n+y < 2^{n+1}.
Donc, n'importe quel ensemble d'arrêts entre x et y faut arrêter d' 2^n.
Ainsi, le nombre optimal de stations de l' x de 2^n + y le nombre de stations de l' x de 2^n, suivi par le nombre de stations de l' 2^n de 2^n+y, inclusivement (ou d' 0 de y, qui est la même).
L'algorithme que je propose pour l'obtenir à partir d' 0 de y est de commencer avec le bit de haute ensemble, et de prendre le train qui vous arrive là, alors allez sur le bas de la liste.
Réclamation: pour générer un numéro d' k 1s, vous devez prendre au moins k des trains. Comme preuve, si vous prenez un train et il ne cause pas de portage de votre numéro de l'arrêt, il définit 1 bit. Si vous prenez un train et il est la cause d'un report, le nombre a au plus 1 plus de bit de départ.
Pour obtenir de x de 2^n est un peu plus compliqué, mais peut être simple par le suivi des trains, vous prenez en arrière.
Cartographie s_i de s_{2^n-i} , et en inversant les marches du train, toute solution pour passer d' x de 2^n décrit une solution pour passer d' 0 de 2^n-x. Et toute solution optimale pour l'avant on est optimale pour l'arrière, et vice-versa.
À l'aide de la suite pour obtenir d' 0 de y, on obtient alors que l'itinéraire optimal à partir d' a de b où b plus élevé ensemble de bits est - 2^n et a n'ont que peu ensemble est #b-2^n + #2^n-aoù # "signifie" le nombre de bits de la représentation binaire". Et en général, si a et b ont un préfixe commun, il suffit de déposer le préfixe commun.
Une règle locale qui génère le nombre d'étapes est de "prendre le train le plus rapide de votre position actuelle qui n'a pas de dépassement de votre destination".
Pour la partie allant de la 2^n de 2^n+y nous l'avons fait de manière explicite dans notre preuve ci-dessus. Pour la partie allant de la x de 2^n c'est plus difficile à voir.
Tout d'abord, si le bit de poids faible de x est défini, il faut évidemment prendre le premier et le seul train que nous pouvons prendre.
Deuxièmement, imaginez x a une certaine collection de unset bits, dire m d'entre eux. Si nous avons joué le jeu de train allant de x/2^m de 2^(n-m), puis mis à l'échelle du stop en multipliant par 2^m , nous aurions une solution pour aller de x de 2^n.
Et #(2^n-x)/2^m = #2^n - x. Donc, cette "échelle" solution est optimale.
À partir de cela, nous sommes toujours à prendre le train correspondant à notre faible-de l'ordre de bit dans cette solution optimale. C'est la plus longue plage de train disponibles, et il n'a pas de dépassement en 2^n.
CQFD
