« カラスを襲うイカ(烏賊)、漢字語源の出典・中国語原文と日本語訳(『南越志』、本草綱目の引用) | トップページ | 平成最後はバブル再来(みずほ総研「とんでも予想2018」)&『ねこねこ55』♪ »

簡単な最大カット問題2~NTT量子ニューラルネットワーク(QNN)のクラウドの使い方

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

書いとこう。NTTの量子ニューラルネットワーク(QNN)が、ネットの

クラウドシステムとして公開されてる。QNNは、Quantum

 Neural Networkという英語の略だ。

 

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

分かって来た。「PLAY GROUND」(遊び場)と呼ばれてる

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

説明が無いけど♪

 

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

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

 

 

     ☆        ☆        ☆

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

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

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

パターンで出題される。

 

171229a

 

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

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

 

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

は1番と仲が悪いから、バスB。1番と4番は仲良しで、4番と2番

は仲が悪いから、4番をバスA、2番をバスBに振り分ける。すると、

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

 

よって、バスAは1番と4番、バスBは2番・3番・5番と私は回答した。

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

 

171229b

 

すると、「正解です!」。上図の左上の「COM」は、コンピューター

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

 

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

時に+1、仲が悪い2人がいる時に-1、関係がない2人がいる時に

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

 

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

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

 

 

      ☆        ☆        ☆

さて、NTTの説明を今回も引用しとくと、「最大カット問題」(Max

-Cut問題)とは次の通り。

 

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

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

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

 分け方を求める問題。

 

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

ただ、要するに複数の要素(上の問題なら5人)を最適な方法で

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

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

 

 

     ☆        ☆        ☆

171229c

 

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

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

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

(自動)のまま。

 

171229d

 

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

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

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

 

171229e

 

これは、0番と1番の関係が仲良し(赤系の色の線)という意味だと

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

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

 

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

0番と1番が同じグループとされる。

 

171229f

 

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

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

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

 

ちなみに画面左端の「TUTORIAL」(チュートリアル)は「指導」。

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

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

のだろうと想像する。

 

最適な状態になったら、「pump rate」(吸い上げの割合)

は1。「cut」の数字(左側の軸を見る)はまだ意味不明。

 

171229g

 

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

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

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

 

 

      ☆        ☆        ☆

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

 

171229h_2

 

色が見にくいが、0番と1番の線だけが青系の色で、他の2本は

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

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

 

171229i

 

結果のグラフでは、0番の青線だけが上側で、1番と2番の線が

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

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

 

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

下側の1番と2番は青色に変化した。

 

 

        ☆        ☆        ☆

最後に、4人の問題の関係1。

 

171229j

 

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

すればいいはず。

 

171229k

 

結果のグラフでは、0番の青線だけ上側で、1番・2番・3番の

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

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

 

171229l

 

 

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

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

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

 

 

 

cf. 簡単な「最大カット問題」

  ~NTT量子ニューラルネットワーク(QNN)のクラウド

 

             (計 2307字)

|

« カラスを襲うイカ(烏賊)、漢字語源の出典・中国語原文と日本語訳(『南越志』、本草綱目の引用) | トップページ | 平成最後はバブル再来(みずほ総研「とんでも予想2018」)&『ねこねこ55』♪ »

「ゲーム」カテゴリの記事

数学」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




« カラスを襲うイカ(烏賊)、漢字語源の出典・中国語原文と日本語訳(『南越志』、本草綱目の引用) | トップページ | 平成最後はバブル再来(みずほ総研「とんでも予想2018」)&『ねこねこ55』♪ »