当前位置: 首页 > 后端技术 > Python

0-1背包问题在量子退火器上的简单实现

时间:2023-03-26 15:25:29 Python

之前的平台写的,配置,接口都不是一成不变的,不要拘泥于某个版本或者某个API,如果有更方便的一?本文主要来源于D-Wave官方文档,如有遗漏,请以原文为准。(请勿复制全文作为课程作业或研究报告)本文配置Windows10Python==3.8.5dwave-ocean-sdk==3.1.1如果使用Leap在线平台的求解器,必须配置(提供你已经注册了Leapleap),命令dwave设置。你会看到$dwavesetupOptionallyinstallnon-open-sourcepackagesandconfigureyourenvironment.Doyouwanttoselectnon-open-sourcepackagestoinstall(y/n)?[y]:D-Wave驱动程序这些驱动程序启用了一些自动性能调整功能。此软件包根据“D-WaveEULA”许可提供。许可条款可在线获取:https://docs.ocean.dwavesys。com/eulaInstall(是/否)?[y]:Installing:D-WaveDriversSuccessfullyinstalledD-WaveDrivers.D-WaveProblemInspector这个工具可视化提交给量子计算机的问题和返回的结果。这个包在“D-WaveEULA”许可下可用。条款的许可证可在线获得:https://docs.ocean.dwavesys.com/eulaInstall(是/否)?[y]:Installing:D-WaveProblemInspector已成功安装D-WaveProblemInspector。正在创建D-Wave配置文件。未找到配置文件;默认位置是:/home/someone/.config/dwave/dwave.confConfirm配置文件路径[/home/someone/.config/dwave/dwave.conf]:Profile(createnew)[prod]:APIendpointURL[skip]:Authenticationtoken[skip]:ABC-1234567890abcdef1234567890abcdefDefaultclientclass(qpuorsw)[qpu]:默认求解器[skip]:配置已保存。按照提示,选择是否同意,输入sapi,apitoken,安装成功。Sapi通常是https://cloud.dwavesys.com/sapi/,token在Leap页面可以找到。基本概念背包问题如果给定一个背包,它的容量是有限的,只能装总质量为\(W\)的物品。现在有一些项目\({x_i,i=1\dotsN}\),对于每个项目\(x_i\)都有一个质量\(w_i\)和一个值\(c_i\)。问如何找到这样一组可以装进背包的物品,同时使总价值最大化。为了方便起见,我们将\(x_i\in[0,1],i=1,2,...N\)设置为变量。该问题用数学建模表示为:$$Max~~~Cost(X)=\sum^{N}_{i=1}c_ix_i\\s.t。~~~~~Weight(X)=\sum^{N}_{i=1}w_ix_i\leqW$$其中,\(Max\,\,Cost(x)\)表示最大化该值\(Cost(x)\),\(s.t.~~Weight(X)\leqW\)表示问题受质量约束。为什么要以0-1背包问题为例呢?因为“所有有界整数线性规划问题都可以转化为等价的背包问题”(Transformationofintegerprogramstoknapsackproblems,Bradley,197190005-7))问题模型因为D-Wave是退火机,构建的模型使用了BQM,所以我们的问题必须建模为二元二次模型(BQM)。从名字就可以看出,BQM是:一个布尔变量(或者取值范围类似于{0,1}且只能取两个值的变量)。目标函数是二次的,即支持\(x^2,x_ix_j,x\)其实还有一个隐藏条件:无约束的D-Wave库其实可以使用Ising模型和QUBO(QuadraticUnconstrainedBinaryOptimization),两者都可以转化为BQM,区别在于表达方式。$$BQM:E(v)=\sum_{i=1}a_iv_i+\sum_{i