当社はCookieを使用して、お客様が当社のWebサイトでより良い体験を得られるようにしています。引き続き閲覧する場合は、当社グループのプライバシーポリシー に同意したことになります。
Fixstars Amplifyを使って、論文 A. Lucas, Front. Phys. (2014) で紹介されている14のNP問題に取り組みます。
あるグラフの頂点を、同じ頂点数の2つの集合に分割する方法のうち、異なる集合に属する2点を結ぶグラフ上での辺の数が最小になるものを求める問題に取り組みます。
あるグラフに対して、頂点の部分集合であって、それに含まれるどの2頂点も辺で結ばれているもののうち、頂点数が最も大きいものを求める問題に取り組みます。
ある集合があり、その部分集合がいくつか与えられているとします。厳密被覆問題では、その集合のどの要素も、選んだ部分集合のちょうど1つに含まれるようにできるかどうかを判定します。
ある集合があり、その部分集合がいくつか与えられているとします。集合パッキング問題では、選択後の部分集合の要素数が最大となるように、共通部分を持たないような部分集合を選びます。
あるグラフに対して、グラフ頂点の部分集合であって、グラフのどの辺もその部分集合の頂点に接続しているものを頂点被覆と呼びます。最小頂点被覆問題では、グラフの頂点被覆のうち、要素数が最小のものを求めます。
1つの命題論理式が与えられたとき、それに含まれる変数の値を上手く定めることで、論理式の値を真にできる場合があります。充足可能性問題では、これを判定します。本サンプルプログラムでは、その中でも3-SATと呼ばれる問題に取り組みます。
あるグラフの辺の部分集合に対して、集合に含まれる辺同士が隣接せず、集合に含まれない辺が必ず集合内の辺と隣接しているものを極大マッチングと呼びます。最小極大マッチング問題では、要素数が最小の極大マッチングを求めます。
本サンプルプログラムで取り組むグラフ彩色問題では、あらかじめ与えられた数の色でグラフの頂点を塗り分けて、辺で結ばれている頂点同士が同じ色にならないようにできるかどうかの判定及びその塗り方を探索します。
あるグラフと色の数が与えられたとき、グラフの頂点を塗り分けて、同じ色の頂点ペアが全て辺で結ばれるようにできるかどうかを判定する問題をクリーク被覆問題と呼びます。本サンプルプログラムでは、そのような頂点の塗り分け方を探索します。
あらかじめ決まった数のジョブとマシンがあり、それぞれのジョブにかかる時間が分かっているとします。それぞれのジョブをいずれかのマシンに割り当てます。ジョブスケジューリング問題では、最も早く全ジョブが完了するような割り当て方を求めます。
あるグラフに対して、グラフの頂点を一回ずつ通って元に戻ってくるような閉路をハミルトン閉路と呼び、一般的に大きなグラフの場合、閉路の有無の判定は困難です。本サンプルプログラムでは、このハミルトン閉路を探索します。
有向グラフが与えられたとき、グラフ頂点の部分集合であって、どのグラフの閉路もその部分集合に含まれる頂点を一つ以上通るものを有向帰還頂点集合といいます。有向帰還頂点集合問題では、そのような集合のうち、要素数が最小のものを求めます。
有向グラフが与えられたとき、グラフ辺の部分集合であって、どのグラフの閉路もその部分集合に含まれる辺を一つ以上含むものを帰還辺集合といいます。最小帰還辺集合問題では、そのような帰還辺集合のうち、要素数が最小のものを求めます。
与えられた2つのグラフにおいて、その頂点同士の1対1対応があり、また対応する2頂点が共に辺で結ばれている場合、それらのグラフは同型であるといいます。一般的に同型性の判定は困難ですが、本サンプルプログラムではこの判定に取り組みます。
デモ&チュートリアル一覧を見る
オンラインデモ&チュートリアルをご利用いただくには、サービス利用規約に同意してください。
に同意したことになります。
