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

明日は早朝からフルマラソンだし、もう時間切れだ。とりあえずの

ブログ記事だけまとめとこう。２週間ほど前から予告されてたＮＴＴ

の量子ニューラルネットワーク（ＱＮＮ）が、ネット経由のクラウド

システムとして公開された。Ｑｕａｎｔｕｍ　Ｎｅｕｒａｌ

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

当初の予定通りなら、公開は１１月２７日だが、私が思い出したのは

今日（１２月２日）。まだシステム全体をあまり理解してないが、一般

向けのゲームの遊び方は一応分かった。

５回試して、５回とも正解（コンピューターと同じ答）にたどりつけたが、

点数評価（重みづけ？）の仕方がまだ分かってない。ひょっとすると、

それぞれの問題や、１つの問題を解く段階ごとに、計算方法とか

評価関数が異なるのかも知れない。

自分で少しずつ解いてる間に、＋１、－１といった数値が瞬間的に

映るので、プロセスを動画撮影して分析する必要がある。

　　　　　　☆　　　　　　　　☆　　　　　　　　☆

さて、「最大カット問題」（Ｍａｘ－Ｃｕｔ問題）とは何か。ＮＴＴの

説明はこうなってる。

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

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

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

　分け方を求める問題。

説明の前半は分かるが、後半の「グループ」が何を指すのかは曖昧

だ。もともと点に種類があって種類別にグループ分けされてるのでは

なく、直前の「部分集合」２つのことを指してるのだろうと思う。

ネット上の他の説明も探してみたが、なかなか分かりやすい説明が

見当たらないので、今日の所はあまりこだわらず、ゲームに向かおう。

　　　　　☆　　　　　　　　☆　　　　　　　　☆

ＱＮＮ　ｃｌｏｕｄのサイトは、Ｗｉｎｄｏｗｓ１０パソコンで見ても

ｉＰａｄ　Ｐｒｏで見てもちょっと不安定で、不自然な映り方になった。

私の個人的環境の問題かも知れないが、まだ開発途中のベータ版

に近いのかも。最初は英語表示だったから、日本語に切り替えた。

トップページの中段で「ＰＬＡＹＧＲＯＵＮＤ」と書かれた箇所を

クリックまたはタップすると、チャレンジ問題が出て来る。私が挑戦

した５回は、すべて違う問題だった。

　　　　　　☆　　　　　　　　☆　　　　　　　　☆　

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

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

この問題文の意味がまた曖昧で不十分。仲が悪いものを別にする

のが最優先するという意味なのか。あるいは、仲が悪いものを別に

することと、仲が良いものを一緒にすることは、同じ評価点なのか。

「関係がない」２人の扱いがどう評価されるのかもハッキリしない。

最大カット問題の説明だと、線があるか無いかどちらかのはずだが。

細かいことは気にせず、仲が悪いものを離して、良いものを一緒に

すると、上のような正解に到達できた。左がコンピューター、右が

私の解答。　

赤線の両端、つまり仲良し同士は、すべて同じバスへとグループ

分けされてる。１番と５番、５番と３番はバスＡ。２番と４番はバスＢ。

一方、グレー（灰色）の線の両端、つまり仲が悪い者同士はすべて

別のバスに乗る。１番と４番、５番と４番、５番と２番、４番と３番。

仲が悪い者も、仲が良い者も、完全に区別できるので、最も単純

なタイプの問題だろう。ただ、「車内の円満度５」の計算方法は

まだ不明。上手く分けると＋１、上手く行ってないと－１かと

思ったら、そうではないようだ。それだと円満度８になってしまう。

　　　　　　☆　　　　　　　　☆　　　　　　　　☆

では２問目。エッジ（線）が４本しかないから、簡単だろう。正解は

下の通り。これも、仲が悪い者は別のバス、仲が良い者は同じバス、

完全な分け方。他に完全な分け方は無いから、点数とは無関係に

正解となる。ただ、「車内の円満度３」の計算は分からない。私なら

これは、上手く分けた線が５本だから、＋５と計算したくなる。

　　　　　　☆　　　　　　　　☆　　　　　　　　☆

３問目。これは仲が良いという関係が無い問題で、おそらく元の

数学的な最大カット問題に近いパターンだろう。点と点の関係は、

線があるか無いか、どちらかになってる。

ただし、「三角形」が２つ出来てるので、仲が悪い者同士も多少は

同じバスに入れるしかない。正解は下図。仲が悪いのに同じバス

に乗るのは、１番と５番にすればいい。これは、扱いにくい三角形

の共通の辺でもある。

　　　　　　　☆　　　　　　　　☆　　　　　　　　☆

４問目は一番簡単で、４本しか線がないから、正解図のみ紹介。

一番上だけＢに替えるとどうなるのか、調べるのを忘れてしまった。

あるいは、一番上はＡのまま、左２つをＢに、右２つをＡに替えると

どうなるのか。それもまた正解だろうと思う。

そして最後はもう、問題だけにしよう。力試しにどうぞ。

解けない場合は、何度も元のＨＰを再読み込み（リロード）すれば、

いつかは出るはず。問題の種類の数は、全部で５９０４９通りある。

不眠不休で試せば、数日以内に発見できるだろう♪

５人から２人を選ぶ組合せの数は、

　5Ｃ2＝（５×４）÷（２×１）＝１０通り。

それぞれ、仲が悪いか良いか、関係がないかで、３通りの変化が

ある。よって、

　（３の１０乗）＝５９０４９通り。

１本も線が無い場合は問題になってないと考えるなら、１通りだけ

差し引いて、５９０４８通りだ。それでは今日はこの辺で。。☆彡

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

　　　～ＮＴＴ量子ニューラルネットのクラウドの使い方

　　　　　　　　　　　　　　　（計　２２１０字）

　　　　　　　（追記　３７字　；　合計　２２４７字）