« 湘南へのアクセスは大変&17年11月の全走行距離 | トップページ | 救急車で病院行きレベルの体調不良、今日はもう手抜き・・ »

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

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

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

の量子ニューラルネットワーク(QNN)が、ネット経由のクラウド

システムとして公開された。Quantum Neural

 Networkという英語の略だ。

 

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

今日(12月2日)。まだシステム全体をあまり理解してないが、一般

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

 

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

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

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

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

 

自分で少しずつ解いてる間に、+1、-1といった数値が瞬間的に

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

 

 

      ☆        ☆        ☆

さて、「最大カット問題」(Max-Cut問題)とは何か。NTTの

説明はこうなってる。

 

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

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

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

 分け方を求める問題。

 

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

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

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

 

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

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

 

 

     ☆        ☆        ☆

171202a

 

QNN cloudのサイトは、Windows10パソコンで見ても

iPad Proで見てもちょっと不安定で、不自然な映り方になった。

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

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

 

トップページの中段で「PLAYGROUND」と書かれた箇所を

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

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

 

 

      ☆        ☆        ☆ 

171202b

 

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

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

 

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

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

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

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

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

 

171202c

 

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

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

私の解答。 

 

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

分けされてる。1番と5番、5番と3番はバスA。2番と4番はバスB。

 

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

別のバスに乗る。1番と4番、5番と4番、5番と2番、4番と3番。

 

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

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

まだ不明。上手く分けると+1、上手く行ってないと-1かと

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

 

 

      ☆        ☆        ☆

171202d

 

では2問目。エッジ(線)が4本しかないから、簡単だろう。正解は

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

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

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

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

 

171202e

 

 

      ☆        ☆        ☆

171202f

 

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

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

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

 

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

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

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

の共通の辺でもある。

 

171202g

 

 

       ☆        ☆        ☆

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

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

あるいは、一番上はAのまま、左2つをBに、右2つをAに替えると

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

 

171202h

 

 

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

 

171202i

 

解けない場合は、何度も元のHPを再読み込み(リロード)すれば、

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

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

 

5人から2人を選ぶ組合せの数は、

 5C2=(5×4)÷(2×1)=10通り。

 

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

ある。よって、

 (3の10乗)=59049通り。

 

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

差し引いて、59048通りだ。それでは今日はこの辺で。。☆彡

 

 

 

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

   ~NTT量子ニューラルネットのクラウドの使い方

 

               (計 2210字)

       (追記 37字 ; 合計 2247字)

|

« 湘南へのアクセスは大変&17年11月の全走行距離 | トップページ | 救急車で病院行きレベルの体調不良、今日はもう手抜き・・ »

ゲーム」カテゴリの記事

数学」カテゴリの記事

コメント

コメントを書く



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




« 湘南へのアクセスは大変&17年11月の全走行距離 | トップページ | 救急車で病院行きレベルの体調不良、今日はもう手抜き・・ »