Comment utiliser un algorithme gourmand pour trouver la séquence non décroissante la plus proche de celle donnée?

20

On vous donne n entiers tous compris entre et . Sous chaque entier vous devez écrire un entier entre 0 et l avec la condition que les b i forment une séquence non décroissante. Définissez la déviation d'une telle séquence comme étant . Concevez un algorithme qui trouve les b_i avec l'écart minimum dans le runtime O (n \ sqrt [4] {l}) .a1,,an0laibi0lbimax(|a1b1|,,|anbn|)biO(nl4)

Honnêtement, je n'ai aucune idée de comment commencer à résoudre cette question. Cela ressemble à une question de programmation dynamique pour moi, mais le professeur a dit que cela devrait être résolu en utilisant un algorithme gourmand. Il serait très apprécié que quelqu'un puisse m'orienter dans la bonne direction en donnant un petit indice.

Aden Dong
la source

Réponses:

9

Commençons par l'observation suivante:

Soit le maximum de la séquence , et désigne son minimum. Si , choisir est optimal.maxa1,...,anmina1=maxb1=b2=...=bn=(max+min)/2

pourquoi est-ce le cas? Eh bien, puisque la séquence commence par le maximum, soit nous choisissons grand, et nous subissons une grande déviation par rapport au minimum de la séquence (puisque tout ultérieur doit être supérieur ou égal à b_1 ), soit nous choisissons b_1 petit et souffrons de la écart à max . La moyenne minimise l'écart maximal.b i b 1 b 1 m a xb1bib1b1max

On peut maintenant essayer de généraliser cette observation pour l'utiliser sur les séquences générales a1,...,an . Par exemple, nous pouvons partitionner n'importe quelle séquence en sous-séquences, de telle sorte que chacune commence par le maximum de la sous-séquence respective.

Exemple: est divisé en , et .( 2 ) ( 6 , 4 , 1 , 5 , 2 ) ( 8 , 7 , 5 , 1 )(2,6,4,1,5,2,8,7,5,1)(2)(6,4,1,5,2)(8,7,5,1)

Compte tenu de ce partitionnement, nous pouvons maintenant résoudre chacune de ces sous-séquences séparément, et obtenir une affectation des , ce qui pourrait cependant violer la condition non décroissante. Cela peut être corrigé sans perdre l'optimalité.bi

Observez que la dernière sous-séquence contient toujours le maximum de la séquence entière (sinon, il y aurait une autre sous-séquence après). Soit les valeurs que nous avons attribuées aux séquences. Maintenant, pour atteindre la non-diminution dans , nous partons de l'arrière à et nous nous dirigeons vers l'avant. Si est plus grand que , nous mettons simplement . S'il est plus petit, nous le conservons. Ensuite, nous procédons à la comparaison de avec et ainsi de suite. Notez que l'abaissement de tout à la valeur demaxw1,w2,...,wkkw1,...,wkwkwk1wkwk1:=wkwk2wk1wiwi+1n'augmente jamais l'écart, car la valeur maximale dans la sous-séquence affectée avec est toujours inférieure au maximum dans la sous-séquence affectée avec .wiwi+1

Cet algorithme devrait être correct, je pense. Concernant le temps d'exécution, l'étape clé est le calcul des maxima croissants pour les sous-séquences, ce qui est possible dans ? Je ne sais pas où contribue.O(n)l

Syzygy
la source
2

Je vais penser à haute voix ici en travaillant simplement sur les conseils que vous avez donnés. Allons à l'indication originale de dire que est ce que vous devez essayer en premier. Je peux penser à un algorithme gourmand qui a ce temps.O(nl)

La partie de la complexité temporelle signifie que vous pouvez garder une liste du nombre de chaque occurrence de chaque valeur 0 .. l . Pour cela, il suffit de créer un ensemble Count = C 0 , , C l qui suit le nombre de chaque l dans l'ensemble. Vous pouvez créer la liste d'initialisation en scannant une fois la séquence d'entrée.l0..lCount=C0,,Cll

Vous pouvez parcourir cette liste dans pour obtenir la valeur maximale et minimale. Si vous deviez remplir la liste entière de b avec ce point médian, votre variance serait simplement la différence entre cette valeur et le max / min. C'est fondamentalement votre pire scénario, appelons-le b w .O(l)bbw

Travaillez donc votre chemin vers depuis la gauche. Vous pouvez à la fois supprimer cet élément de Count et obtenir le min / max de b [ i + 1 ] b [ n ] dans O ( l ) . Maintenant, nous pouvons être gourmands. Nous ne choisissons pas b i > b w car cela force la liste entière restante (pour répondre à l'exigence non décroissante) et augmente ainsi la variance. La valeur minimale que nous pouvons choisir est b [ i - 1 ] . Si un ibiCountb[i+1]b[n]O(l)bi>bwb[i1]aiest dans la plage acceptable, nous le sélectionnons, s'il est inférieur à la plage, utilisez le minimum. Cela minimise la variance à compte tenu des contraintes connues.bi

Ce n'est qu'une idée, j'ai peut-être de la chance et cela vous indique la bonne direction. Cet algorithme peut ne pas fonctionner (il le fait pour mes quelques tests simples), mais il correspond aux conseils donnés, alors peut-être qu'il est utile. S'il est correct, il est facile de voir que la partie peut à coup sûr être déposée sur , encore plus loin, je ne suis pas sûr.O(l)O(logl)

edA-qa mort-ora-y
la source
2

Voici la solution du professeur, qu'il appelle «réduction»: Pour chaque de 0 à l , essayez de construire une solution si nous savons que l'écart est inférieur ou égal à i . Le premier i pour lequel une solution peut être trouvée est l'écart minimum. Nous pouvons trouver une solution étant donné l'écart en temps O ( n ) . Le temps de course est donc O ( n l ) . Ensuite, au lieu d'utiliser la recherche linéaire, nous pouvons utiliser la recherche binaire pour déterminer la plus petite déviation pour laquelle une solution est possible. Cela réduit le temps d'exécution à O ( n log li0liiO(n)O(nl) , qui satisfait à l'exigence de O ( n 4 O(nlogl).O(nl4)

Aden Dong
la source
4
Donc le était une astuce ... Mais je suis plus intrigué par le "On peut trouver une solution étant donné l'écart en temps O (n)" .. comment est-ce que cen'est pasla partie intéressante? O(nl4)
jmad
@jmad Étant donné , pour chaque j , prendre b j comme la valeur la plus basse qui est au moins aussi grande que tous les b k précédents , et qui n'est pas plus éloignée que i d' un a j . Si nous ne pouvons pas trouver une telle valeur, qu'est-ce que cela signifie? Cela signifie qu'un précédent b t est plus grand que i plus grand qu'un a j . Donc un précédent a t est plus de 2 i plus grand qu'un a j . Donc, cette valeur de i n'était pas possible. Si vous traversez le nijbjbkiajbtiajat2iajinvaleurs sans se coincer comme ça, vous avez trouvé une solution pour sans retour en arrière, dans le temps O ( n ) . iO(n)
jwg
O (n log l) aurait été un indice fort que vous devez effectuer une recherche binaire sur la plage de 0 à l.
gnasher729
0

Je pense que cela devrait être faisable en O (n).

Prenons le problème similaire: étant donné , 1 ≤ i ≤ n et d ≥ 0, trouver b i dans un ordre non décroissant tel que | a i - b i | d pour tout i, ou montrer que ce n'est pas possible. Cela peut être fait dans O (n), et en utilisant la recherche binaire, le problème d'origine est résolu dans O (n log l).aibi|aibi|d

Maintenant, s'il y a i ≤ j tel que a_i - a_j> 2d, alors il n'y a pas de solution (car ).biaid,bjaj+d<ai2d+d=aidbi

Mais si a_i - a_j ≤ 2d pour tout i ≤ j, je pense qu'une solution sera toujours trouvée. Il nous suffit donc de trouver m = max (a_i - a_j) pour tout i ≤ j, et de choisir d = étage ((m + 1) / 2). Ce maximum peut être trouvé dans O (n).

gnasher729
la source
Idée intrigante! Je peux croire que quelque chose comme ça pourrait fonctionner, mais il semble qu'il y ait un grand écart à la fin de votre réponse et j'ai du mal à remplir les détails. Avez-vous une preuve que si pour tout i j alors une solution existe toujours? Plus important encore, comment le trouvons-nous? La question initiale dit que nous devons trouver les b i . Même si nous supposons qu'une solution existe, j'ai du mal à voir comment trouver les b i correspondants . Pourriez-vous préciser ceci? aiaj2dijbibi
DW