量子退火算法入门(4):旅行商问题的QUBO建模「上 篇」

薛定谔了么
2024-11-11 15:43:09

一、旅行商问题(Traveling Saleman Problem,TSP)

1.旅行商问题的定义

旅行商问题,是一个经典的组合优化问题,而且是著名NP问题之一。如下图所示,可以想象,有A,B,C,D,E 五个地点,我们想找到一条路径,从地点A出发,经过剩余四个地点,然后回到地点A,从所有可能路径中找到距离最短的一条路径。本章借用了文献[*1]的图表。

2.旅行商问题求解的计算量

最简单的求解方式就是,如下图所示把所有的求解路径全部计算一遍,然后算出每条路径的长度,求出最短路径。

如下图所示,所有的枚举路径总共有24条,我们可以很快找到最短路径。

如果下面A~Z的情况,这个计算量,日本的第一超级计算机富岳,每秒的计算速度约为44.2京次(京是10的16次方,即万兆)。一年的秒数是3600×24×365=3153.6万秒。有兴趣的可以计算一下要算多少年。

二、TSP问题的建模

1.总体Hamilton量H

该问题输入有两个,这里借用了文章[*2]的图表:

·地点数目:N NN

·地点之间的距离:

约束条件:

·每个时间步只能访问一个地点。

·每个地点都访问过一次。

  整体的Hamilton量H HH如下:

目标变量x i , j的两个下标的意思如下图👇所示,绿色的圆圈代表在某个时间步访问了某个第地点,所以我们的目标变量就可以用0或1表示了,0代表未访问,1代表访问。

2.约束条件

约束条件比较简单,先从约束条件解释,这里有2个约束可以解释如下:

1.每个时间步只能访问一个地点。

=> 上图矩阵里的每列元素之和必须为1。也就是每列中只有一个元素为1。

2.每个地点都访问过一次。

=> 上图矩阵里的每行元素之和必须为1。也就是每行中只有一个元素为1。

具体表达式如下:

3.目标函数

解析:

总结

旅行商问题,是比较有实际意义的应用问题,大家能体会到怎么把现实问题抽象出binary变量,然后怎么把制约条件表达出来。因为,上面的建模有两种编程实现方式,为了控制篇幅,下一篇献上Python代码。

在阅读参考文献时,经常会发现资料里的一些小错误,大家以后阅读资料时也要小心啊。

参考文献:

[*1] : https://www.nttdata.com/jp/ja/-/media/nttdatajapan/files/news/services_info/2021/012800/012800-01.pdf

[*2] : https://qiita.com/yufuji25/items/0425567b800443a679f7

 

————————————————

本文转载自CSDN博主:gang_unerry

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

原文链接:https://blog.csdn.net/gangshen1993/article/details/127602524

 

19
0
0
0
关于作者
相关文章
  • 量子退火算法入门(7):QUBO中的三次多项式怎么转换? ...
    前言本文还是大部分截图来自于:《最適化問題とWildqatを用いた量子アニーリング計算入門》 http ...
    了解详情 
  • 量子退火算法入门(6):初识量子退火算法的发明过程 ...
    一、量子计算机量子计算机就是使用量子bit实现的计算机。之前提到过,可以分为两类,量子门(gate ...
    了解详情 
  • 量子退火算法入门(5):旅行商问题的QUBO建模「下篇之Python实现」 ...
    一,旅行商问题QUBO的两种实现看过上篇的读者应该已经注意到,因为旅行商问题需要最终返回到初始 ...
    了解详情 
  • 量子退火算法入门(3):整数分割问题的QUBO建模
    整数分割问题:QUBO建模最重要的就是,把建模对象中的变量映射为binary(0/1 或者 -1/+1)的变量 ...
    了解详情 
在本版发帖返回顶部
快速回复 返回顶部 返回列表