簡単な最大カット問題2~NTT量子ニューラルネットワーク(QNN)のクラウドの使い方
年末でバタバタとあおられる中、今日は1ヶ月近く前の記事の続編を
書いとこう。NTTの量子ニューラルネットワーク(QNN)が、ネットの
クラウドシステムとして公開されてる。QNNは、Quantum
Neural Networkという英語の略だ。
その高度な使い方はともかく、ゲーム遊び的な使い方なら少しずつ
分かって来た。「PLAY GROUND」(遊び場)と呼ばれてる
一般向けのページがあって、脳トレにいいのだ。ちょっと難しいし、
説明が無いけど♪
わざと謎かけみたいにしてるのかね? あるいは、多少知ってる人
が見れば、すぐ分かるのか。。
☆ ☆ ☆
まずウォーミング・アップとして、前回扱ったチャレンジ問題を新たに
1問やってみよう。問題のバリエーションが非常に多いからなのか、
あるいは、私のPCをクッキーか何かで識別してるのか、毎回違う
パターンで出題される。
「子どもたちの関係を見ながら、できるだけ仲が悪いもの同士が
同じバスとならないようにバス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番と私は回答した。
念のため確認して、ファイナル・アンサー♪
すると、「正解です!」。上図の左上の「COM」は、コンピューター
が出した答という意味で、私の答と一致。
この問題なら、計算でも一応出せる。同じバスに仲が良い2人がいる
時に+1、仲が悪い2人がいる時に-1、関係がない2人がいる時に
0として、合計点を計算すると、正解の場合に最大値3になるのだ。
しかし、「車内の円満度」はなぜか、1。まだ、この計算方法は解読
できてない。やはり途中の映像を動画撮影で録画するしかないか。
☆ ☆ ☆
さて、NTTの説明を今回も引用しとくと、「最大カット問題」(Max
-Cut問題)とは次の通り。
複数のノード(点)と、ノードを結ぶエッジ(線)からなるグラフに
おいて、ノード群を2つの部分集合に分割する際、異なる
グループに属するノード間に張られたエッジの数が最大となる
分け方を求める問題。
この説明と、本来の数学の説明との関係も、まだ解明できてない。
ただ、要するに複数の要素(上の問題なら5人)を最適な方法で
2つのグループに分割する問題だろうし、チャレンジ問題の後に
出るシステムの使い方なら少し理解できた。
☆ ☆ ☆
上図が、QNNクラウドによって問題を解く画面。少なくとも私の
端末だと何の説明もヘルプも出て来ないから、試行錯誤で推測
するしかない。画面右上のパラメーターは意味不明だからAuto
(自動)のまま。
まず画面左上で、点の数(つまり人数)とつながり方(関係)を選択。
グラフ・トポロジー(位相幾何学)という高級な数学用語を使ってる
が、要するに点のつながり方のこと。ここでは2人、関係1を選んだ。
これは、0番と1番の関係が仲良し(赤系の色の線)という意味だと
思う。それなら、2人を同じグループ(またはバス)にして、もう一つの
グループは何も無しにすればいい。
実際、画面右上の「RUN」ボタンを押してシステムを作動させると、
0番と1番が同じグループとされる。
0番を表す青線と、1番を表すオレンジ色の線が、重なって下側
に進んでる。このグラフが、0番と1番を同じグループにすべきと
いうことを指導してくれてるようだ。
ちなみに画面左端の「TUTORIAL」(チュートリアル)は「指導」。
グラフの「Pump」とは、ポンプを上下に動かして吸い上げる
という意味だから、システムが超高速で場合分けして計算してる
のだろうと想像する。
最適な状態になったら、「pump rate」(吸い上げの割合)
は1。「cut」の数字(左側の軸を見る)はまだ意味不明。
計算結果が出た後は、問題の側の色も変化する。0番と1番
が青色になってるのは、グラフの下側に分けられたという意味
だと思う。 線の色の変化はまだ意味不明。
☆ ☆ ☆
続いて、3人の場合の関係4を見てみよう。
色が見にくいが、0番と1番の線だけが青系の色で、他の2本は
赤系になってる。ということは、0番と1番を別グループに分けて、
2番はどちらのグループに入れても同じ評価になるはず。
結果のグラフでは、0番の青線だけが上側で、1番と2番の線が
下側になった。序盤で、「cut」のピンク色の線が激しく上下に
揺れてるのは、おそらく本当は最適解が2通りあるからだろう。
問題の図では、グラフ上側の0番だけが赤色に変化して、グラフ
下側の1番と2番は青色に変化した。
☆ ☆ ☆
最後に、4人の問題の関係1。
0番と1番の間の線だけが青系だから、0番だけを別グループに
すればいいはず。
結果のグラフでは、0番の青線だけ上側で、1番・2番・3番の
線は下側へと振り分け。したがって問題の図では、0番の点だけ
赤色、他は青色へと変化した。
最大カット問題というのは、かなり分かりやすいのに奥が深いし、
量子コンピューターにも興味があるので、もう少し追求する予定。
とりあえず、今日のところはこの辺で。。☆彡
cf. 簡単な「最大カット問題」
~NTT量子ニューラルネットワーク(QNN)のクラウド
(計 2307字)
| 固定リンク | 0
« カラスを襲うイカ(烏賊)、漢字語源の出典・中国語原文と日本語訳(『南越志』、本草綱目の引用) | トップページ | 平成最後はバブル再来(みずほ総研「とんでも予想2018」)&『ねこねこ55』♪ »
「ゲーム」カテゴリの記事
- 日テレ『頭脳王2021』ストレンジ・オセロ、先手必勝ゲームの証明と戦略(7通りの場合分け)(2021.02.23)
- 『頭脳王2021』、光速の半分で未来に移動(相対性理論)&ストレンジ・オセロ第1局の棋譜全体(京大・上木vsコンピューター)(2021.02.21)
- パズル「絵むすび」17、線を書かずに頭の中だけでイメージする解き方(難易度3、ニコリ作、朝日be)(2020.12.20)
- パズル「ナンスケ」の解き方、考え方7~難易度4、ニコリ作、朝日新聞be(2020.11.15)
- 日テレ『頭脳王2021』新・謎解き問題(1次予選)、答えの考え方、解き方(ネタバレ控えめ、少しずつ更新)(2020.11.07)
「数学」カテゴリの記事
- 日テレ『頭脳王2021』ストレンジ・オセロ、先手必勝ゲームの証明と戦略(7通りの場合分け)(2021.02.23)
- 『頭脳王2021』、純金のピラミッドの金額&シロナガスクジラを持ち上げる金剛力士像の身長、計算式と解説(2021.02.20)
- 1と0のカードゲーム、単純そうで複雑な連続操作の考察~開成中学2021年入試、算数・問題3の解き方(2021.02.14)
- 宝くじの当選番号を予言して当てる迷惑メールの仕組み、他~2021年・大学入学共通テスト・情報関係基礎(2021.01.24)
- 陸上100m走のタイム(時間)とストライド(歩幅)、ピッチ(歩数)の関係~2021年・大学入学共通テスト・数学ⅠA・第2問〔1〕(2021.01.19)
コメント