量子コンピュータが何なのか、あまりわかっていませんが、
Fixstars Amplify を使うと量子コンピュータの体験してみることができると知り試してみました。
チュートリアルが丁寧で、循環セールスマン問題やグラフ彩色問題を体験できました。
今回は、自分で条件を作る練習をするために、ナップサック問題を題材に選びました。
こちらの記事で、Google の OR-Tools というライブラリを使ってナップサック問題を解く方法の解説が行われていますが、今回は、同じ問題を Fixstars Amplify を使って解いてみようと思います。
問題
ナップサックの中の荷物の価値の最大値を求めよ。
ただし、ナップサックに入る荷物の体積の最大値は12である。
| アイテム | A | B | C | D | E |
|---|---|---|---|---|---|
| インデックス番号 | 0 | 1 | 2 | 3 | 4 |
| 体積 | 3 | 4 | 6 | 1 | 5 |
| 価値 | 6 | 7 | 8 | 1 | 4 |
解き方
制約条件と目的関数を考える
制約条件は絶対に満たさなくてはならない条件で、目的関数はできるだけ満たしたい条件。
制約条件
この場合、ナップサックに入る荷物の体積の最大値 <= 12 というのが絶対に満たさなくてはならない条件である。
目的条件
価値の合計が大きければ多いほうが良いというのが目的条件になる。
コード
これらの条件をコードに落としてく
from amplify import BinaryPoly, gen_symbols, sum_poly, BinaryQuadraticModel, Solver, decode_solution
from amplify.constraint import less_equal
from amplify.client import FixstarsClient
a = [3, 4, 6, 1, 5] # 体積
c = [6, 7, 8, 1, 4] # 価値
# 変数の作成
q = gen_symbols(BinaryPoly, 5)
# 制約条件
constraint1 = less_equal(sum_poly(len(a), lambda x: q[x] * a[x]), 12)
# 目的条件 (最小化問題なので、-1倍している。)
objective = -1 * sum([j * c[i] for i, j in enumerate(q)])
k = 0.1 # ハイパーパラメータ
loss = constraint1 + k * objective
client = FixstarsClient()
client.token = 'XXXXXXXXXXXXXXXXXXXXXXX' # 無料登録で入手できるToken
client.parameters.timeout = 1000
solver = Solver(client)
result = solver.solve(loss)
for r in result:
print(r.energy)
print(r.values)
print(decode_solution(q, r.values))
出力は、
-0.17
{2: 0, 4: 1, 3: 0, 0: 1, 1: 1}
[1, 1, 0, 0, 1]
となり、ちゃんと正解が導けました。
とても短いコードで表現できるのが面白いです。
他にもいろいろな問題を試してみようと思います。