ケーススタディ

このセクションでは、PyQBPPを使った最適化問題、数学問題、グラフ問題の解法例を提供します。 各問題の後の Easy / Medium / Hard は、ページの内容を理解する難しさの目安です。問題を理解するのに要る予備知識、定式化の発想、プログラムの構造の 3 点から決めています。

活用事例の一部は動画でも紹介しています（動画（ケーススタディ）のページ）。

数学問題

1. 数学問題: 3つの整数を求める (Easy)
2. 3桁の算数問題 (Easy)
3. 三次方程式 (Easy)
4. 平方根 (Easy)
5. 円周率に近い分数 (Easy)
6. 最大公約数 (GCD) (Easy)
7. 余り問題 (Easy)
8. ピタゴラスの三つ組 (Medium)
9. タクシー数 1729 (Medium)
10. 再帰による素因数分解 (Medium)

パズル

1. Nクイーン問題 (Easy)
2. スターバトル (Easy)
3. 数独 (Medium)
4. ノノグラム (Medium)
5. スリザーリンク (Medium)
6. 魔方陣 (Medium)
7. SEND + MORE = MONEY 問題 (Medium)

グラフ問題

頂点・集合の選択

1. 最大独立集合 (MIS) 問題 (Easy)
2. 最大クリーク問題 (Easy)
3. 最小頂点被覆問題 (Easy)
4. 最小支配集合問題 (Medium)
5. 最小集合被覆問題 (Medium)

カット・分割

1. 最大カット問題 (Easy)
2. 最小グラフ二分割問題 (Easy)
3. カット幅問題 (Medium)

マッチング

1. 最大マッチング問題 (Easy)
2. 最小極大マッチング問題 (Medium)

彩色

1. グラフ彩色問題 (Easy)
2. 3 彩色可能頂点削除問題 (Medium)
3. グラフ辺彩色問題 (Medium)

同型

1. 部分グラフ同型問題 (Medium)

経路問題

1. 最短路問題 (Medium)
2. 巡回セールスマン問題 (Medium)
3. 容量制約付き配送計画問題 (CVRP) (Hard)

組合せ最適化問題

1. QUBO 問題 (Easy)
2. 整数線形計画法 (Easy)
3. LABS問題 (Easy)
4. ナップサック問題 (Medium)
5. 分割問題の3通りの定式化 (Medium)
6. 区間部分和問題 (ISSP) (Medium)
7. 切出し問題 (Medium)
8. 施設配置問題 (p-median と p-center) (Medium)
9. ポートフォリオ最適化 (Hard)

スケジューリング

1. シフトスケジューリング問題 (Medium)
2. 日勤・夜勤の勤務表 (Medium)
3. 納期付き機械スケジューリング (Hard)
4. ジョブショップスケジューリング (Hard)

充足可能性

1. 充足可能性問題 (SAT) (Medium)
2. Not-All-Equal SAT (NAE-SAT) (Medium)

回路シミュレーション

1. 加算器シミュレーション (Medium)
2. 乗算器シミュレーションと因数分解 (Hard)

画像処理

1. 画像のハーフトーン化 (Medium)
2. 画像のノイズ除去 (Medium)
3. オプティカルフロー (Medium)
4. クラスタドット・ハーフトーン (Hard)
5. ASCII アートの生成 (Hard)

ブラックボックス最適化

1. FMQA によるブラックボックス最適化 (Hard)
2. FMQA による量子化学計算 (Hard)

量子アニーラー

1. 量子アニーラーのシミュレーション (Medium)

注釈 グラフのケーススタディにはmatplotlibとnetworkxを使用した可視化コードが含まれています。 次のコマンドでインストールしてください: pip install matplotlib networkx