adle：基于Qt实现的算法可视化（旅行商）

接上篇基于Qt实现的算法可视化（棋盘覆盖、汉诺塔、旅行商），本篇主要给出旅行商问题的具体实现。

旅行商问题作为一个NP难问题，我们并不要求解决太过庞大的数据，因此本篇通过可视化技术来展示贪心实现的过程。同时，我们选择一个固定形态的无向图，只支持用户修改起点和各条路径的权值，这样实现起来就简单了许多。具体见代码注释。

头文件：

#ifndef TSP_H#define TSP_H#include <QWidget>#include <QPushButton>#include <QPixmap>#include <QPainter>#include <QPaintEvent>#include <QLabel>#include <QLineEdit>#include <cstring>#include <QTimer>const int INF=0x3f3f3f3f;class tsp : public QWidget{ Q_OBJECTpublic: explicit tsp(QWidget *parent = 0); void return_main(); //返回主界面 void setInit(); //设置初始图 void getEg(); //生成样例 void getInput(); //获取输入 void paintF(); //第一次加粗 void selectF(); //从第一次加粗的路径中选择 void paintS(); //第二次加粗 void selectS(); //从第二次加粗的路径中选择 void paintT(); //第三次加粗 void paintL(); //最后一次加粗protected: void paintEvent(QPaintEvent *ev); //绘图事件signals: void return_sign(); //返回主界面的信号public slots:private: //b1为“返回主界面”按钮，b2为“生成样例”按钮，b3为“自定义输入”按钮，b4为“执行”按钮 QPushButton b1, b2, b3, b4; QPixmap graph = QPixmap(501, 501); //旅行商图像 //分别储存AB,AC,AD,BC,BD,CD路径权值文本输入框的提示信息和起点的提示信息 QLabel AB, AC, AD, BC, BD, CD, START; //分别储存AB,AC,AD,BC,BD,CD路径权值文本输入框和起点 QLineEdit ABle, ACle, ADle, BCle, BDle, CDle, STARTle; double x[5], y[5]; //储存四个点的坐标 int dis[5][5]; //储存两点间的路径 int vis[5]; //标记该点是否走过 int start, next, third, fouth; //起点 int first[3], second[2]; //分别储存前两次描黑时的路径 //分别控制绘制、选择的计时器 QTimer timer1, timer11, timer2, timer22, timer3, timer4;};#endif // TSP_H

cpp文件：

#include "tsp.h"#include <QPen>#include <cmath>#include <QBrush>#include <QFont>#include <QString>#include <QMessageBox>#include <QDebug>tsp::tsp(QWidget *parent) : QWidget(parent){ //窗口设置 setWindowTitle("旅行商问题"); //设置窗口标题 resize(1000, 650); //设置窗口大小 //按钮设置 b1.setParent(this); b2.setParent(this); b3.setParent(this); b4.setParent(this); //设置父类 QFont font("宋体"); //设置字体 b1.setFont(font); b2.setFont(font); b3.setFont(font); b4.setFont(font); b1.setText("返回主界面"); b2.setText("生成样例"); b3.setText("自定义输入"); b4.setText("执行"); //设置按钮内容 b1.move(725, 500); b2.move(725, 290); b3.move(725, 360); b4.move(725, 430); //设置按钮位置 b1.resize(150, 30); b2.resize(150, 30); b3.resize(150, 30); b4.resize(150, 30); //设置按钮大小 b1.setStyleSheet("border:2px groove gray;border-radius:10px;padding:2px 4px;font:15px;"); b2.setStyleSheet("border:2px groove gray;border-radius:10px;padding:2px 4px;font:15px;"); b3.setStyleSheet("border:2px groove gray;border-radius:10px;padding:2px 4px;font:15px;"); b4.setStyleSheet("border:2px groove gray;border-radius:10px;padding:2px 4px;font:15px;"); b1.show(); b2.show(); b3.show(); b4.show(); //设置按钮显示在父类窗口 //设置Label AB.setParent(this); AC.setParent(this); AD.setParent(this); BC.setParent(this); BD.setParent(this); CD.setParent(this); AB.setText("A-B:"); AC.setText("A-C:"); AD.setText("A-D:"); BC.setText("B-C:"); BD.setText("B-D:"); CD.setText("C-D:"); AB.resize(40, 30); AC.resize(40, 30); AD.resize(40, 30); BC.resize(40, 30); BD.resize(40, 30); CD.resize(40, 30); AB.move(640, 80); AC.move(760, 80); AD.move(880, 80); BC.move(640, 150); BD.move(760, 150); CD.move(880, 150); AB.show(); AC.show(); AD.show(); BC.show(); BD.show(); CD.show(); START.setParent(this); START.resize(60, 30); START.move(730, 220); START.setFont(QFont("楷体", 15 , QFont::Medium)); START.setText("起点："); START.show(); //设置行文本编辑器 ABle.setParent(this); ACle.setParent(this); ADle.setParent(this); BCle.setParent(this); BDle.setParent(this); CDle.setParent(this); ABle.resize(40, 30); ACle.resize(40, 30); ADle.resize(40, 30); BCle.resize(40, 30); BDle.resize(40, 30); CDle.resize(40, 30); ABle.move(680, 80); ACle.move(800, 80); ADle.move(920, 80); BCle.move(680, 150); BDle.move(800, 150); CDle.move(920, 150); ABle.show(); ACle.show(); ADle.show(); BCle.show(); BDle.show(); CDle.show(); STARTle.setParent(this); STARTle.resize(60, 30); STARTle.move(805, 220); STARTle.show(); x[1]=250;y[1]=100; x[2]=250;y[2]=300; x[3]=250-100*sqrt(3); y[3]=400; x[4]=250+100*sqrt(3); y[4]=400; //设置初始图 setInit(); //连接信号和槽函数 connect(&b1, &QPushButton::clicked, [=]() { setInit(); //设置初始图 return_main(); //返回主界面 }); connect(&b3, &QPushButton::clicked, [=]() { setInit(); //设置初始图 //对于自定义输入，弹出输入提示框 QMessageBox qmb(QMessageBox::Information, "提示", "请您在右侧依次输入各路径权值和起点(A-D)！", QMessageBox::Ok); qmb.resize(200, 300); qmb.exec(); }); connect(&b2, &QPushButton::clicked, this, &tsp::getEg); //生成样例 connect(&b4, &QPushButton::clicked, this, &tsp::getInput); //获取输入数据 connect(&timer1, &QTimer::timeout, this, &tsp::paintF); //第一次加粗 connect(&timer11, &QTimer::timeout, this, &tsp::selectF); //第一次选择 connect(&timer2, &QTimer::timeout, this, &tsp::paintS); //第二次加粗 connect(&timer22, &QTimer::timeout, this, &tsp::selectS); //第二次选择 connect(&timer3, &QTimer::timeout, this, &tsp::paintT); //第三次加粗 connect(&timer4, &QTimer::timeout, this, &tsp::paintL); //第三次加粗}//返回主界面的槽函数void tsp::return_main() {emit return_sign();}//绘图事件void tsp::paintEvent(QPaintEvent *ev){ QPainter p(this); p.drawPixmap(100, 50, graph); //在（100,50）的位置画图象 QWidget::paintEvent(ev);}//设置初始图void tsp::setInit(){ graph.fill(Qt::white); //用白色填充背景 QPen pen; //声明笔 pen.setWidth(3); //设置笔的宽度 QPainter p(&graph); //声明画家，并设置父类 p.setPen(pen); //将笔指定给画家 p.drawRect(0, 0, 500, 500); //在board（0，0）位置画一个500*500的矩形 pen.setWidth(1); p.setPen(pen); //画线 p.drawLine(x[1], y[1], x[2], y[2]); p.drawLine(x[1], y[1], x[3], y[3]); p.drawLine(x[1], y[1], x[4], y[4]); p.drawLine(x[2], y[2], x[3], y[3]); p.drawLine(x[2], y[2], x[4], y[4]); p.drawLine(x[3], y[3], x[4], y[4]); //画点 p.setBrush(QBrush(Qt::white)); double r = 20*sqrt(2); p.drawEllipse(235, 85, r, r); p.drawEllipse(235, 285, r, r); p.drawEllipse(235-100*sqrt(3), 385, r, r); p.drawEllipse(235+100*sqrt(3), 385, r, r); //写字 p.setFont(QFont("楷体", 15, QFont::Medium)); p.drawText(243, 110, "A"); p.drawText(243, 310, "B"); p.drawText(243-100*sqrt(3), 410, "C"); p.drawText(243+100*sqrt(3), 410, "D"); //文本编辑器清空 ABle.clear(); ACle.clear(); ADle.clear(); BCle.clear(); BDle.clear(); CDle.clear(); STARTle.clear(); //计时器停止 timer1.stop(); timer11.stop(); timer2.stop(); timer22.stop(); timer3.stop(); timer4.stop(); //dis和vis初始化 memset(dis, INF, sizeof(INF)); memset(vis, 0, sizeof(vis));}//生成样例void tsp::getEg(){ //通过初始化来清空上次图片内容 setInit(); update(); //设置文本编辑器内容 ABle.setText("10"); ACle.setText("20"); ADle.setText("30"); BCle.setText("40"); BDle.setText("50"); CDle.setText("60"); STARTle.setText("A");}//获取输入void tsp::getInput(){ QString str; int len; //获取各点间路径长度 str=ABle.text(); len=str.toInt(); dis[1][2]=dis[2][1]=len; str=ACle.text(); len=str.toInt(); dis[1][3]=dis[3][1]=len; str=ADle.text(); len=str.toInt(); dis[1][4]=dis[4][1]=len; str=BCle.text(); len=str.toInt(); dis[2][3]=dis[3][2]=len; str=BDle.text(); len=str.toInt(); dis[2][4]=dis[4][2]=len; str=CDle.text(); len=str.toInt(); dis[3][4]=dis[4][3]=len; //获取起点，并对应转换成数字 str=STARTle.text(); if(str=="A") start = 1; else if(str=="B") start = 2; else if(str=="C") start = 3; else if(str=="D") start = 4; else //若起点输入有误，则弹出警告框，并跳出程序 { QMessageBox qmb(QMessageBox::Warning, "警告", "您的起点输入有误，请重新输入！", QMessageBox::Close); qmb.resize(200, 300); qmb.exec(); return ; } vis[start] = 1; //标记起点已经访问过 //将路径权值画在图中 QPainter p(&graph); QPen pen; pen.setWidth(3); p.setPen(pen); p.setFont(QFont(QFont("楷体", 15, QFont::Medium))); p.drawText((x[1]+x[2])/2, (y[1]+y[2])/2, ABle.text()); p.drawText((x[1]+x[3])/2, (y[1]+y[3])/2, ACle.text()); p.drawText((x[1]+x[4])/2, (y[1]+y[4])/2, ADle.text()); p.drawText((x[2]+x[3])/2, (y[2]+y[3])/2, BCle.text()); p.drawText((x[2]+x[4])/2, (y[2]+y[4])/2, BDle.text()); p.drawText((x[3]+x[4])/2, (y[3]+y[4])/2, CDle.text()); update(); //开始绘制路径 timer1.start(1500);}//第一次加粗void tsp::paintF(){ QPainter p(&graph); p.setPen(QPen(QBrush(Qt::red), 5)); //将备选加粗 int cnt = 0; for(int i=1; i<=4; i++) if(!vis[i]) { first[cnt++] = i; p.drawLine(x[start], y[start], x[i], y[i]); } p.setPen(QPen()); //画点 p.setBrush(QBrush(Qt::white)); double r=20*sqrt(2); p.drawEllipse(235, 85, r, r); p.drawEllipse(235, 285, r, r); p.drawEllipse(235-100*sqrt(3), 385, r, r); p.drawEllipse(235+100*sqrt(3), 385, r, r); //写字 p.setFont(QFont("楷体", 15, QFont::Medium)); p.drawText(243, 110, "A"); p.drawText(243, 310, "B"); p.drawText(243-100*sqrt(3), 410, "C"); p.drawText(243+100*sqrt(3), 410, "D"); //画路径权值 QPen pen; pen.setWidth(3); p.setPen(pen); p.setFont(QFont(QFont("楷体", 15, QFont::Medium))); p.drawText((x[1]+x[2])/2, (y[1]+y[2])/2, ABle.text()); p.drawText((x[1]+x[3])/2, (y[1]+y[3])/2, ACle.text()); p.drawText((x[1]+x[4])/2, (y[1]+y[4])/2, ADle.text()); p.drawText((x[2]+x[3])/2, (y[2]+y[3])/2, BCle.text()); p.drawText((x[2]+x[4])/2, (y[2]+y[4])/2, BDle.text()); p.drawText((x[3]+x[4])/2, (y[3]+y[4])/2, CDle.text()); update(); //第一次加粗结束，开始第一次选择 timer1.stop(); timer11.start(1500);}//第一次选择void tsp::selectF(){ //选第二个点 next = first[0]; for(int i=1; i<3; i++) if(dis[start][next] > dis[start][first[i]]) next = first[i]; vis[next] = 1; //标记第二个点已访问 //复原未选路径 QPainter p(&graph); for(int i=0; i<3; i++) if(first[i] != next) { p.setPen(QPen(QBrush(Qt::white), 5)); p.drawLine(x[start], y[start], x[first[i]], y[first[i]]); p.setPen(QPen()); p.drawLine(x[start], y[start], x[first[i]], y[first[i]]); } p.setPen(QPen()); //画点 p.setBrush(QBrush(Qt::white)); double r=20*sqrt(2); p.drawEllipse(235, 85, r, r); p.drawEllipse(235, 285, r, r); p.drawEllipse(235-100*sqrt(3), 385, r, r); p.drawEllipse(235+100*sqrt(3), 385, r, r); //写字 p.setFont(QFont("楷体", 15, QFont::Medium)); p.drawText(243, 110, "A"); p.drawText(243, 310, "B"); p.drawText(243-100*sqrt(3), 410, "C"); p.drawText(243+100*sqrt(3), 410, "D"); //画路径权值 QPen pen; pen.setWidth(3); p.setPen(pen); p.setFont(QFont(QFont("楷体", 15, QFont::Medium))); p.drawText((x[1]+x[2])/2, (y[1]+y[2])/2, ABle.text()); p.drawText((x[1]+x[3])/2, (y[1]+y[3])/2, ACle.text()); p.drawText((x[1]+x[4])/2, (y[1]+y[4])/2, ADle.text()); p.drawText((x[2]+x[3])/2, (y[2]+y[3])/2, BCle.text()); p.drawText((x[2]+x[4])/2, (y[2]+y[4])/2, BDle.text()); p.drawText((x[3]+x[4])/2, (y[3]+y[4])/2, CDle.text()); update(); //第一次选择结束，开始第二次加粗 timer11.stop(); timer2.start(1500);}//第二次加粗void tsp::paintS(){ QPainter p(&graph); p.setPen(QPen(QBrush(Qt::blue), 5)); //将备选加粗 int cnt=0; for(int i=1; i<=4; i++) if(!vis[i]) { second[cnt++] = i; p.drawLine(x[next], y[next], x[i], y[i]); } p.setPen(QPen()); //画点 p.setBrush(QBrush(Qt::white)); double r=20*sqrt(2); p.drawEllipse(235, 85, r, r); p.drawEllipse(235, 285, r, r); p.drawEllipse(235-100*sqrt(3), 385, r, r); p.drawEllipse(235+100*sqrt(3), 385, r, r); //写字 p.setFont(QFont("楷体", 15, QFont::Medium)); p.drawText(243, 110, "A"); p.drawText(243, 310, "B"); p.drawText(243-100*sqrt(3), 410, "C"); p.drawText(243+100*sqrt(3), 410, "D"); //画路径权值 QPen pen; pen.setWidth(3); p.setPen(pen); p.setFont(QFont(QFont("楷体", 15, QFont::Medium))); p.drawText((x[1]+x[2])/2, (y[1]+y[2])/2, ABle.text()); p.drawText((x[1]+x[3])/2, (y[1]+y[3])/2, ACle.text()); p.drawText((x[1]+x[4])/2, (y[1]+y[4])/2, ADle.text()); p.drawText((x[2]+x[3])/2, (y[2]+y[3])/2, BCle.text()); p.drawText((x[2]+x[4])/2, (y[2]+y[4])/2, BDle.text()); p.drawText((x[3]+x[4])/2, (y[3]+y[4])/2, CDle.text()); update(); //第二次加粗结束，第二次选择开始 timer2.stop(); timer22.start(1500);}//第二次选择void tsp::selectS(){ //选第三个点 third = second[0]; for(int i=1; i<2; i++) if(dis[next][third] > dis[next][second[i]]) third = second[i]; vis[third] = 1; //标记第三个点已访问 //复原未选路径 QPainter p(&graph); for(int i=0; i<2; i++) if(second[i] != third) { p.setPen(QPen(QBrush(Qt::white), 5)); p.drawLine(x[next], y[next], x[second[i]], y[second[i]]); p.setPen(QPen()); p.drawLine(x[next], y[next], x[second[i]], y[second[i]]); } p.setPen(QPen()); //画点 p.setBrush(QBrush(Qt::white)); double r=20*sqrt(2); p.drawEllipse(235, 85, r, r); p.drawEllipse(235, 285, r, r); p.drawEllipse(235-100*sqrt(3), 385, r, r); p.drawEllipse(235+100*sqrt(3), 385, r, r); //写字 p.setFont(QFont("楷体", 15, QFont::Medium)); p.drawText(243, 110, "A"); p.drawText(243, 310, "B"); p.drawText(243-100*sqrt(3), 410, "C"); p.drawText(243+100*sqrt(3), 410, "D"); //画路径权值 QPen pen; pen.setWidth(3); p.setPen(pen); p.setFont(QFont(QFont("楷体", 15, QFont::Medium))); p.drawText((x[1]+x[2])/2, (y[1]+y[2])/2, ABle.text()); p.drawText((x[1]+x[3])/2, (y[1]+y[3])/2, ACle.text()); p.drawText((x[1]+x[4])/2, (y[1]+y[4])/2, ADle.text()); p.drawText((x[2]+x[3])/2, (y[2]+y[3])/2, BCle.text()); p.drawText((x[2]+x[4])/2, (y[2]+y[4])/2, BDle.text()); p.drawText((x[3]+x[4])/2, (y[3]+y[4])/2, CDle.text()); update(); //第二次选择结束，第三次加粗开始 timer22.stop(); timer3.start(1500);}//第三次加粗void tsp::paintT(){ QPainter p(&graph); p.setPen(QPen(QBrush(Qt::green),5)); //将备选加粗 for(int i=1;i<=4;i++) if(!vis[i]) { p.drawLine(x[third], y[third], x[i], y[i]); fouth = i; } p.setPen(QPen()); //画点 p.setBrush(QBrush(Qt::white)); double r=20*sqrt(2); p.drawEllipse(235, 85, r, r); p.drawEllipse(235, 285, r, r); p.drawEllipse(235-100*sqrt(3), 385, r, r); p.drawEllipse(235+100*sqrt(3), 385, r, r); //写字 p.setFont(QFont("楷体", 15, QFont::Medium)); p.drawText(243, 110, "A"); p.drawText(243, 310, "B"); p.drawText(243-100*sqrt(3), 410, "C"); p.drawText(243+100*sqrt(3), 410, "D"); //画路径权值 QPen pen; pen.setWidth(3); p.setPen(pen); p.setFont(QFont(QFont("楷体", 15, QFont::Medium))); p.drawText((x[1]+x[2])/2, (y[1]+y[2])/2, ABle.text()); p.drawText((x[1]+x[3])/2, (y[1]+y[3])/2, ACle.text()); p.drawText((x[1]+x[4])/2, (y[1]+y[4])/2, ADle.text()); p.drawText((x[2]+x[3])/2, (y[2]+y[3])/2, BCle.text()); p.drawText((x[2]+x[4])/2, (y[2]+y[4])/2, BDle.text()); p.drawText((x[3]+x[4])/2, (y[3]+y[4])/2, CDle.text()); update(); //第三次加粗结束，第四次加粗开始 timer3.stop(); timer4.start(1500);}//第四次加粗void tsp::paintL(){ QPainter p(&graph); p.setPen(QPen(QBrush(Qt::yellow), 5)); //画线 p.drawLine(x[fouth], y[fouth], x[start], y[start]); p.setPen(QPen()); //画点 p.setBrush(QBrush(Qt::white)); double r=20*sqrt(2); p.drawEllipse(235, 85, r, r); p.drawEllipse(235, 285, r, r); p.drawEllipse(235-100*sqrt(3), 385, r, r); p.drawEllipse(235+100*sqrt(3), 385, r, r); //写字 p.setFont(QFont("楷体", 15, QFont::Medium)); p.drawText(243, 110, "A"); p.drawText(243, 310, "B"); p.drawText(243-100*sqrt(3), 410, "C"); p.drawText(243+100*sqrt(3), 410, "D"); //画路径权值 QPen pen; pen.setWidth(3); p.setPen(pen); p.setFont(QFont(QFont("楷体", 15, QFont::Medium))); p.drawText((x[1]+x[2])/2, (y[1]+y[2])/2, ABle.text()); p.drawText((x[1]+x[3])/2, (y[1]+y[3])/2, ACle.text()); p.drawText((x[1]+x[4])/2, (y[1]+y[4])/2, ADle.text()); p.drawText((x[2]+x[3])/2, (y[2]+y[3])/2, BCle.text()); p.drawText((x[2]+x[4])/2, (y[2]+y[4])/2, BDle.text()); p.drawText((x[3]+x[4])/2, (y[3]+y[4])/2, CDle.text()); update(); //路径绘画结束 timer4.stop();}

最终效果：

初始界面

贪心算法结束后给出的路径