簡単な最大カット問題２～ＮＴＴ量子ニューラルネットワーク（ＱＮＮ）のクラウドの使い方

年末でバタバタとあおられる中、今日は１ヶ月近く前の記事の続編を

書いとこう。ＮＴＴの量子ニューラルネットワーク（ＱＮＮ）が、ネットの

クラウドシステムとして公開されてる。ＱＮＮは、Ｑｕａｎｔｕｍ

　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋという英語の略だ。

その高度な使い方はともかく、ゲーム遊び的な使い方なら少しずつ

分かって来た。「ＰＬＡＹ ＧＲＯＵＮＤ」（遊び場）と呼ばれてる

一般向けのページがあって、脳トレにいいのだ。ちょっと難しいし、

説明が無いけど♪

わざと謎かけみたいにしてるのかね？　あるいは、多少知ってる人

が見れば、すぐ分かるのか。。

　　　　　☆　　　　　　　　☆　　　　　　　　☆

まずウォーミング・アップとして、前回扱ったチャレンジ問題を新たに

１問やってみよう。問題のバリエーションが非常に多いからなのか、

あるいは、私のＰＣをクッキーか何かで識別してるのか、毎回違う

パターンで出題される。

　「子どもたちの関係を見ながら、できるだけ仲が悪いもの同士が

　同じバスとならないようにバスＡとバスＢに振り分けてみましょう」。

まず１番を１回クリックしてバスＡに乗せる。ちょっと微妙だが、３番

は１番と仲が悪いから、バスＢ。１番と４番は仲良しで、４番と２番

は仲が悪いから、４番をバスＡ、２番をバスＢに振り分ける。すると、

微妙な５番もバスＢの方が少し良さそうだ。

よって、バスＡは１番と４番、バスＢは２番・３番・５番と私は回答した。

念のため確認して、ファイナル・アンサー♪

すると、「正解です！」。上図の左上の「ＣＯＭ」は、コンピューター

が出した答という意味で、私の答と一致。

この問題なら、計算でも一応出せる。同じバスに仲が良い２人がいる

時に＋１、仲が悪い２人がいる時に－１、関係がない２人がいる時に

０として、合計点を計算すると、正解の場合に最大値３になるのだ。

しかし、「車内の円満度」はなぜか、１。まだ、この計算方法は解読

できてない。やはり途中の映像を動画撮影で録画するしかないか。

　　　　　　☆　　　　　　　　☆　　　　　　　　☆

さて、ＮＴＴの説明を今回も引用しとくと、「最大カット問題」（Ｍａｘ

－Ｃｕｔ問題）とは次の通り。

　複数のノード（点）と、ノードを結ぶエッジ（線）からなるグラフに

　おいて、ノード群を２つの部分集合に分割する際、異なる

　グループに属するノード間に張られたエッジの数が最大となる

　分け方を求める問題。

この説明と、本来の数学の説明との関係も、まだ解明できてない。

ただ、要するに複数の要素（上の問題なら５人）を最適な方法で

２つのグループに分割する問題だろうし、チャレンジ問題の後に

出るシステムの使い方なら少し理解できた。

　　　　　☆　　　　　　　　☆　　　　　　　　☆

上図が、ＱＮＮクラウドによって問題を解く画面。少なくとも私の

端末だと何の説明もヘルプも出て来ないから、試行錯誤で推測

するしかない。画面右上のパラメーターは意味不明だからＡｕｔｏ

（自動）のまま。

まず画面左上で、点の数（つまり人数）とつながり方（関係）を選択。

グラフ・トポロジー（位相幾何学）という高級な数学用語を使ってる

が、要するに点のつながり方のこと。ここでは２人、関係１を選んだ。

これは、０番と１番の関係が仲良し（赤系の色の線）という意味だと

思う。それなら、２人を同じグループ（またはバス）にして、もう一つの

グループは何も無しにすればいい。

実際、画面右上の「ＲＵＮ」ボタンを押してシステムを作動させると、

０番と１番が同じグループとされる。

０番を表す青線と、１番を表すオレンジ色の線が、重なって下側

に進んでる。このグラフが、０番と１番を同じグループにすべきと

いうことを指導してくれてるようだ。

ちなみに画面左端の「ＴＵＴＯＲＩＡＬ」（チュートリアル）は「指導」。

グラフの「Ｐｕｍｐ」とは、ポンプを上下に動かして吸い上げる

という意味だから、システムが超高速で場合分けして計算してる

のだろうと想像する。

最適な状態になったら、「ｐｕｍｐ　ｒａｔｅ」（吸い上げの割合）

は１。「ｃｕｔ」の数字（左側の軸を見る）はまだ意味不明。

計算結果が出た後は、問題の側の色も変化する。０番と１番

が青色になってるのは、グラフの下側に分けられたという意味

だと思う。 線の色の変化はまだ意味不明。

　　　　　　☆　　　　　　　　☆　　　　　　　　☆

続いて、３人の場合の関係４を見てみよう。

色が見にくいが、０番と１番の線だけが青系の色で、他の２本は

赤系になってる。ということは、０番と１番を別グループに分けて、

２番はどちらのグループに入れても同じ評価になるはず。

結果のグラフでは、０番の青線だけが上側で、１番と２番の線が

下側になった。序盤で、「ｃｕｔ」のピンク色の線が激しく上下に

揺れてるのは、おそらく本当は最適解が２通りあるからだろう。

問題の図では、グラフ上側の０番だけが赤色に変化して、グラフ

下側の１番と２番は青色に変化した。

　　　　　　　　☆　　　　　　　　☆　　　　　　　　☆

最後に、４人の問題の関係１。

０番と１番の間の線だけが青系だから、０番だけを別グループに

すればいいはず。

結果のグラフでは、０番の青線だけ上側で、１番・２番・３番の

線は下側へと振り分け。したがって問題の図では、０番の点だけ

赤色、他は青色へと変化した。

最大カット問題というのは、かなり分かりやすいのに奥が深いし、

量子コンピューターにも興味があるので、もう少し追求する予定。

とりあえず、今日のところはこの辺で。。☆彡

ｃｆ．　簡単な「最大カット問題」

　　～ＮＴＴ量子ニューラルネットワーク（ＱＮＮ）のクラウド

　　　　　　　　　　　　　（計　２３０７字）