問題解決の技法(6)逆から考えよ(クロード・シャノン)

数学者クロード・シャノンが行った問題解決に関する講演について、最終回です。今回の話題は本ブログでよく取り上げるものですが(ラベル「逆にやる」を参照ください)、いつもとは別の天才が取り上げていることでも、その威力がうかがえます。前回分はこちらです。なお、意味段落での改行を追加しました。(日本語は拙訳)

もうひとつ触れておきたいやりかたがあります、数学上の研究をする際にたびたび出くわすものですが、問題を逆向きに考える方法です。ある前提条件Pに基づいて解Sを求めようとして、煮詰まっているとしましょう。そのとき、その問題を反転させて、「解Sは問題を解く上での所与の定理や公理、あるいは定数である」と仮定するのです。その上で、前提条件Pを求めるための術を考え出します。それが正しいやりかただと想像してみてください。するとその方向から問題を解くほうが、かえって易しいことに気づくかと思います。適切で単刀直入な道筋がみつかります。そうだとすれば、その問題を小さく分割した個々において、同じように考えることも多分に可能でしょう。別の例で言えば、たとえば印をつけた道筋がこうあって、このように中継していく点があちらへ続いているとします。そのとき、小さな段階ごとに反転させるやりかたがとれるでしょうから、証明するまでの困難な段階はおそらく3つか4つで済むものと思います。

設計の作業でも、同じことができると思います。私はコンピューターを設計することが時折あり、その種類は多岐にわたりました。そのなかで、ある所与の数量をもとに、ある数を計算させたいと考えたものがありました。それは「ニム」という名の石取りゲームを実行する機械となりますが、実に難しい仕事だとわかりました。この種の計算は実現可能ではあるものの、極めて多数のリレー[継電器]が必要になります。しかし「問題を反転させたらどうなるか」と考えた結果、もし所与のものと望まれる結果を入れ替えれば、至極簡単に実現できることがわかりました。さらにその考え方を発展させ、フィードバックを使うようにしました。そうすることで当初よりもずっと単純な設計になりました。つまり望まれる結果を起点にして戻ってくる際に、所与の入力値に合致するまでその値を使い続けるわけです。ですからその機械の内部では、利用者が実際に入力した数を得るまでは、さらにはPに照らした際に正しい手順である数に達するまでは、複数の数値を含む範囲Sをとりつつ、逆方向から動作しています。

このように、さきに触れた思想に基づいて解を求める方法を説明しましたが、大多数のみなさんにはひどく退屈だったのではないでしょうか。そこで、本日持参したこの装置をお見せしたいと思います。今回お話しした設計に関連する問題が、一つ二つ仕込んであります。これまでお話ししてきたことが反映してあると思いますので、この周りに集まってごらんになってください。この机の周りにみなさんが一度に集まれるかどうかは、何とも言えませんが。(おわり)

Now one other thing I would like to bring out which I run across quite frequently in mathematical work is the idea of inversion of the problem. You are trying to obtain the solution S on the basis of the premises P and then you can’t do it. Well, turn the problem over supposing that S were the given proposition, the given axioms, or the given numbers in the problem and what you are trying to obtain is P. Just imagine that that were the case. Then you will find that it is relatively easy to solve the problem in that direction. You find a fairly direct route. If so, it’s often possible to invent it in small batches. In other words, you’ve got a path marked out here - there you got relays you sent this way. You can see how to invert these things in small stages and perhaps three or four only difficult steps in the proof.

Now I think the same thing can happen in design work. Sometimes I have had the experience of designing computing machines of various sorts in which I wanted to compute certain numbers out of certain given quantities. This happened to be a machine that played the game of nim and it turned out that it seemed to be quite difficult. If [typo for It?] took quite a number of relays to do this particular calculation although it could be done. But then I got the idea that if I inverted the problem, it would have been very easy to do - if the given and required results had been interchanged; and that idea led to a way of doing it which was far simpler than the first design. The way of doing it was doing it by feedback; that is, you start with the required result and run it back until - run it through its value until it matches the given input. So the machine itself was worked backward putting range S over the numbers until it had the number that you actually had and, at that point, until it reached the number such that P shows you the correct way.

Well, now the solution for this philosophy which is probably very boring to most of you. I’d like now to show you this machine which I brought along and go into one or two of the problems which were connected with the design of that because I think they illustrate some of these things I’ve been talking about. In order to see this, you’ll have to come up around it; so, I wonder whether you will all come up around the table now.