Je ne pouvais pas comprendre facilement Fence Repair of Arimoto, donc je vais le suivre en détail.

Définition des termes

** Arimoto **

Fence Repair

Le problème est d'utiliser la méthode gourmande, mais je ne comprenais pas pourquoi elle devenait gourmande, alors j'ai commencé par essayer de la vérifier.

Énoncé du problème

L'agriculteur John essaie de couper $ N $ de planches sur une planche très longue pour réparer la clôture. La longueur de la planche que vous essayez de couper est $ L_1, L_2, \ dots, L_N $, et la longueur de la planche d'origine est juste la somme de ces derniers. Lors de la découpe d'une planche, cela coûte autant que la longueur de la planche. Par exemple, supposons que vous vouliez couper une planche de 5,8,8 $ $ 3 $ sur une planche de 21 $ de long. Découper une planche de 21 $ en planches de 13 $ et 8 $ de long coûte 21 $. Couper cette planche de 13 $ en planches de 5 $ et 8 $ coûte 13 $. Il en coûte 34 $ au total. Au minimum, combien cela coûte-t-il de supprimer toutes les planches?

Contraintes

Pour de nombreux problèmes, il peut souvent être généralisé à une sorte de structure de graphe, qu'il s'agisse d'un arbre ou non. L'exemple montré dans cet énoncé de problème peut être exprimé comme un arbre dichotomisé comme suit. fence-repair_01.png Le coût à chaque déconnexion est la valeur du nœud parent, de sorte que le coût total est la somme de toutes les valeurs des nœuds non feuille. Dans l'exemple ci-dessus, la somme des nœuds non-feuilles (blanc) est 13 $ + 21 = 34 $, ce qui correspond au coût total de l'énoncé du problème.

Le but est de minimiser le coût total à ce moment.

Politique de réponse

Politique de commentaire du livre de fourmis

Quand je l'ai lu, cela semblait correct, mais je n'étais pas vraiment convaincu. Je pense que le but est de transmettre un changement dans l'idée de penser de bas en haut parce que les conditions sont divisées lors de la résolution de haut en bas, mais je ne comprends pas cela lorsqu'un problème plus difficile est expliqué plus tard. J'avais l'impression d'être coincé, alors j'ai décidé de le poursuivre.

Conditions fixes et facteurs variables

Voir ce qui est fixe (prémisse) et quel type d'opération provoque des fluctuations est la politique de base pour résoudre tout problème. Puisque c'est le problème introduit dans le chapitre sur la cupidité, il est méta-entendu qu'il y a toujours une opération qui réduit le coût total. Dans la situation de solution réelle, il est nécessaire de sélectionner l'algorithme comprenant le jugement.

Maintenant, dans cette question, les longueurs de toutes les planches une fois la découpe terminée sont données, de sorte que le nombre de nœuds qui deviendront éventuellement des feuilles est fixe. En d'autres termes, la structure arborescente change en fonction de l'ordre dans lequel les feuilles sont combinées.

Vérification des facteurs variables

Même si vous essayez de comprendre comment cela change, même si vous y pensez soudainement dans un cas compliqué, cela échouera. Le grand mathématicien, Carte, a également dit "diviser les difficultés" </ b>.

Se diviser en cas incroyablement simples et réfléchir est un schéma important pour résoudre tout problème. Alors, quel est le cas le plus simple? Réfléchissons ensemble.

Cas de N = 1

Inutile de dire que le cas de $ N = 1 $ est le plus simple. En d'autres termes, la plaque d'origine ne sera pas coupée. Avec cela, il n'y a pas de fluctuation ni de merde, et le coût est toujours de 0 $. Augmentons $ N $.

N = 2 cas

C'est le cas où le nombre de déconnexions est de 1 $. Là encore, il n'y a pas de variation lorsque la longueur de la plaque après découpe est fixée. Augmentons encore $ N $.

N = 3 cas

Désolé de vous avoir fait attendre. Les variations sortent enfin de $ N = 3 $. Tout d'abord, par souci de simplicité, mettons la longueur de la planche après découpe, qui est de 3 $, comme $ A \ leqq B \ leqq C $. Ce serait une hypothèse qui ne perdrait pas sa généralité.

Eh bien, la façon de couper ici est un modèle de 3 $.

  • (A+B+C) \rightarrow (A+B),C \rightarrow A,B,C
  • (A+B+C) \rightarrow A,(B+C) \rightarrow A,B,C
  • (A+B+C) \rightarrow B,(C+A) \rightarrow A,B,C

C'est difficile à comprendre même si je l'écris en lettres, alors j'ai fait un chiffre. fence-repair_02.png Seule la différence dans la partie rouge de la figure affecte le coût total. La position des autres parties est différente, mais la valeur de la somme ne change pas. En d'autres termes, minimiser le coût total dans ce cas équivaut à choisir le plus petit de $ (A + B), (B + C), (C + A) $.

Si vous regardez attentivement pour voir s'il y a suffisamment de variations, choisissez $ 2 $ sur 3 $ $, c'est-à-dire $ {} _3 \ mathrm {C} _2 = {} _3 \ mathrm {C} _1 = 3 $, qui est certainement le modèle $ 3 $. Il ne peut y en avoir. Donc, bien sûr, quel motif est le plus petit est $ (A + B) $, qui est de 2 $ sélectionné à partir de la plus petite valeur.

En résumé, si $ N = 3 $, vous pouvez découper en sélectionnant 2 $ parmi le plus petit. En utilisant ce fait, considérons le cas de $ N = 4 $.

N = 4 cas

Avec $ N = 3 $, nous avons pu affiner le modèle qui minimise le coût total. D'un point de vue méta, puisqu'il s'agit d'une méthode gourmande, il semble qu'il sera possible d'affiner le modèle avec un sentiment progressif après cela.

Maintenant, le cas de $ N = 4 $ a des planches de 4 $. Si vous divisez la caisse dans la première coupe, le motif sera divisé selon que vous coupez la planche $ ABCD $ par 1 $ + 3 $ ou 2 $ + 2 $. fence-repair_03.png

1 + 3 modèles

Le modèle de coupe avec $ 1 + 3 $ est une extension du cas de $ N = 3 $ du côté racine. Après avoir coupé $ 1 $ pour la première fois, il aura la même forme que $ N = 3 $, et la planche $ ABC $ ne changera qu'en $ \ {ABC, ABD, ACD, BCD \} $.

En d'autres termes, il y a un total de 4 $ \ times 3 = 12 $ pattern, mais en réalité cela revient au pattern $ 4 $ dont on coupe en premier. Ici, la généralisation du coût total du cas de $ N = 3 $ est de 2A + 2B + C $. (Choisir le plus petit 2 $ sur 3 $ équivaut à choisir le plus grand)

Par contre, si vous ajoutez $ D $, qui est $ A \ leqq B \ leqq C \ leqq D $, le cas est $ N = 4 $. Le modèle de 4 $ suivant est utilisé pour résumer le coût total.

  • $ 3A + 3B + 2C + D $: Coupez d'abord $ D $
  • $ 3A + 3B + 2D + C $: Coupez d'abord $ C $
  • $ 3A + 3C + 2D + B $: Coupez d'abord $ B $
  • $ 3B + 3C + 2D + A $: Coupez d'abord $ A $

Maintenant, arrêtons-nous ici et jetons un coup d'œil au modèle $ 2 + 2 $.

2 + 2 motifs

Si vous y réfléchissez un instant, vous pouvez voir que le coût total sera de 2 $ \ fois (A + B + C + D) $ quelle que soit la combinaison.

Comparez ensemble

En divisant les cas jusqu'à présent, nous avons constaté que les modèles qui doivent être considérés comme le cas de $ N = 4 $ sont réduits à 5 $ au total, y compris le modèle de 4 $ mentionné précédemment.

Maintenant, soustrayons $ 2 \ times (A + B + C + D) $ de tous les cas pour comparer la relation de grandeur de 5 $ $.

  • $ ; ; ; ; ; ; 0 ; ; ; ; ; ; $: Première coupée en feuilles $ 2 + 2 $
  • $ A + B-D $: Coupez d'abord $ D $
  • $ A + B-C $: première coupe $ C $
  • $ A + C-B $: Coupez d'abord $ B $
  • $ B + C-A $: Coupez d'abord $ A $

Quelle est la valeur qui peut être le coût le plus bas? En considérant $ A \ leqq B \ leqq C \ leqq D $, nous pouvons voir ce qui suit.

  • $ ; ; ; ; ; ; 0 ; ; ; ; ; ; $: Minimum si $ A + BD $ est une valeur positive </ strong> POLICE>
  • $ A + B-D $: Minimum dans les cas négatifs </ FONT>
  • $ A + B-C $: Peut être négatif, mais pas un candidat car le motif jusqu'à $ 1 $ en soustrayant le plus grand nombre $ D $ est plus petit
  • $ A + C-B \ geqq 0 $: Pas un candidat car il est toujours $ 0 $ ou plus en raison de la relation de taille
  • $ B + C-A \ geqq 0 $: Pas un candidat car il est toujours $ 0 $ ou plus en raison de la relation de taille

En d'autres termes, la casse minimum change en fonction du résultat du jugement de $ A + B \ leqq D $. </ b>

Retour à l'explication du livre des fourmis

Regardez de plus près $ A + B \ leqq D $. C'est fondamentalement la même chose que d'ajouter le résultat fusionné de $ A + B $ et de trier à nouveau.

En effet, $ C $ ne peut en aucun cas être la valeur maximale au moment de $ C \ leqq D $. Choisir 2 $ du plus petit des 3 $ équivaut à choisir le maximum de 1 $. Vous n'avez pas besoin des informations $ C $ qui ne peuvent pas être maximisées.

Visualisons cela d'une manière plus compréhensible. Dans le cas de $ N = 4 $, considérons le problème de sélectionner $ 2 $ du côté le plus petit et de fusionner $ A + B $ en $ M $.

Comme je l'ai mentionné plus tôt, il n'y a que des cas de 2 $ ci-dessous. $ M $ est le cas le plus grand, ou $ D $ est le cas le plus grand. fence-repair_04.png

C'est vrai. Après tout, même si vous pétrissez diverses choses de haut en bas, si vous fusionnez et remplacez à partir du plus petit, le cas de $ N = 4 $ se terminera dans le cas de $ N = 3 $. Si vous renvoyez $ A + B $ à $ M $ pour confirmation, ce sera sous la forme d'une classification de cas qui a été discutée de haut en bas comme suit. fence-repair_05.png

Recapture de bas en haut

Regardons maintenant le coût de chaque feuille. Il est facile de voir que le coût total de la feuille à 1 $ est le produit de la valeur et de la profondeur du nœud feuille. Essayez de tracer la feuille $ A $ dans la figure précédente jusqu'à la racine. Vous pouvez voir que toutes les routes principales $ 1 $ menant à la racine contiennent $ A $, et les autres routes ne contiennent pas $ A $.

Et comme il est difficile de penser à la fois à l'axe de valeur et de profondeur $ 2 $, pensez dans une perspective de même profondeur. Même si on ne sait pas quel type d'arborescence il s'agira, plus la valeur est petite, plus le coût est bas à la même profondeur. Cela signifie qu'il est toujours avide de remplir avec la plus petite paire, étant donné que les feuilles sont remplies dans l'ordre du plus profond. En effet, encore une fois, "plus la valeur est petite, plus le coût est bas si la profondeur est la même".

Si vous essayez de faire cela de haut en bas, vous devrez effectuer plusieurs sélections à une profondeur de 1 $, ce qui crée soudainement un cas. Comme vous pouvez le voir que $ N = 4 $ est assez gênant, cela signifie que le cas maximum de $ N = 20000 $ est pratiquement impossible.

Leçons apprises

--La difficulté est divisée

  • Essayez dans la direction opposée
  • Si vous avez plusieurs axes, essayez de réparer l'un d'entre eux.

Veuillez vous reporter au Cahier des défis du concours de programmation pour le code de réponse réel.

De côté

Les pros compétitifs ont commencé dans le mois de 8 $ de 2020 $. Je publie généralement des articles sur Blog personnel.

Recommended Posts