C语言中TSP问题的解决和实践应用

教育 2024-07-06 21:04 宁夏

TSP旅行商问题（Traveling Salesman Problem）是数学领域中著名的组合优化问题之一。其基本情境是：给定一组城市以及每对城市之间的距离，旅行商需要从某个城市出发，访问每个城市恰好一次，并最终返回到起始城市。问题的目标是找到这样的行程，使得其总距离最短。

TSP问题的难点在于其组合性质。随着城市数量的增加，可能的行程数量会阶乘级增长，这使得穷举所有可能解的方法变得不切实际。因此，尽管TSP问题具有实际应用价值，但找到其最优解却是一个NP难问题，即没有已知的多项式时间复杂度算法可以解决它。

为了近似或推断TSP问题的解，研究者们提出了多种方法，包括暴力解法、动态规划、贪心算法等。暴力解法尝试所有可能的组合以找出最短路径，但这种方法在城市数量较多时计算量巨大。动态规划通过存储并重用子问题的解决方案来减少计算量，但仍然面临维数灾难的问题。贪心算法则在每一步选择当前最短的边所连接的城市，但可能陷入局部最优解。

尽管TSP问题是一个NP难问题，但在实际应用中，可以通过启发式算法和近似算法找到较好的解。这些算法可以在合理的时间内找到接近最优解的行程，从而满足实际需求。

总的来说，TSP旅行商问题是一个具有挑战性和实际应用价值的优化问题。虽然找到其最优解是一个NP难问题，但通过采用合适的算法和技术，仍然可以在合理的时间内找到较好的解。

LKH是当前公认求解tsp最好的算法，基于Lin-Kernighan思想，通过将图上的连接边切断、重连的方式（2-opt, 3-opt...)一次次改进获得更好的路径解。交换边的数量越多得到的解质量越好。但在解质量和运行时间之间需要找到一个平衡，找到一个合适的值，LK思想就是可变的交换边取值。

当然，作为一个应用者，这些高深的算法很难短时间掌握，但是我们可以学习如何应用。如我在无人机航飞规划中就应用了这一算法。这一算法是由C语言编写的，而且已经封装为可执行程序。我们只需要掌握好这个程序输入的东西，输出的成果即可，就如同调用一个函数一样。

TSP的应用很广泛，大到可以用来规划旅游顺序，无人机快递的投递，小到扫地机器的路线规划等等。

具体该如何使用LKH算法呢？其实我们只需要了解它的调用和运行原理就可以使用它来解决一些我们生活中实际问题。

如图是整个算法所需要和产生的成果。首先是LKH.bat这个是windows系统用于调用启动程序的一个命令脚本。使用记事本打开可以看到

表示运行LKH-3.exe 运行 a.par文件，再使用记事本打开a.par文件。

这个文件里面记录着运行LKH-3.exe 所需要输入的参数和打开的文件。

a280.tsp用计算本打开，可以看到一些原始的数据。

是每个位置的坐标数据。

output.txt是LKH算法解算出来的结果。

了解到以上的所有过程，如何使用这个软件来做一些事呢。

可以看出来，除了LKH-3.exe我们没有办法修改，其他所有的文件我们都可以使用程序来生成，也就是说，假如我们有一些坐标，我们就可以通过编程实现计算他们连接的最短距离。

整体实现源码如下：

///////////////////////////////////////////////////// 程序名称：TSP问题的LKH算法实践应用// 编译环境：Mictosoft Visual Studio 2022, EasyX_20200315(beta)// 作　　者：luoyh <2864292458@qq.com>// 公 众 号：C语言研究// 最后修改：2024-7-6//
#define  _CRT_SECURE_NO_WARNINGS#include <stdio.h>  #include <stdlib.h>  #include <string.h> #include<Windows.h>
void WriteBat(){    const char* batContent = "@echo off\r\npath=%path%;\r\nLKH-3.exe Par.par\r\n";    const char* fileName = "LKH.bat";     FILE* file = fopen(fileName, "w");    if (file == NULL)    {        perror("无法打开文件");        return;    }    fprintf(file, "%s", batContent);    fclose(file);}
void WritePar() {    const char* parContent =        "PROBLEM_FILE = Tsp.tsp\r\n"        "MOVE_TYPE = 5\r\n"        "PATCHING_C = 3\r\n"        "PATCHING_A = 2\r\n"        "RUNS = 1\r\n"        "TOUR_FILE = ./output.txt\r\n";    const char* fileName = "Par.par";    FILE* file = fopen(fileName, "w");    if (file == NULL)    {        perror("Failed to open file");        return;    }    fprintf(file, "%s", parContent);    fclose(file);}
typedef struct{    double X;    double Y;} XYD;
void WriteTsp(XYD flyxyd, XYD* Photo_list, int Photo_list_size){    int POINTS = Photo_list_size + 1;
    char tspContent[4096]; // 假设内容不会超过4096个字符      char buffer[256];    strcpy(tspContent, "NAME : TSPDATA\r\n");    strcat(tspContent, "COMMENT : drilling problem (Ludwig)\r\n");    strcat(tspContent, "TYPE : TSP\r\n");    sprintf(buffer, "DIMENSION : %d\r\n", POINTS);    strcat(tspContent, buffer);    strcat(tspContent, "EDGE_WEIGHT_TYPE : EUC_2D\r\n");    strcat(tspContent, "NODE_COORD_SECTION\r\n");    sprintf(buffer, "1 %f %f\r\n", flyxyd.X, flyxyd.Y);    strcat(tspContent, buffer);
    for (int i = 0; i < Photo_list_size; i++)    {        sprintf(buffer, "%d %f %f\r\n", i + 2, Photo_list[i].X, Photo_list[i].Y);        strcat(tspContent, buffer);    }    strcat(tspContent, "EOF\r\n");    const char* fileName = "Tsp.tsp";    FILE* file = fopen(fileName, "w");    if (file == NULL)    {        perror("Failed to open file");        return;    }
    fprintf(file, "%s", tspContent);    fclose(file);}
void StartProcess(const char* filePath){    STARTUPINFOA si;    PROCESS_INFORMATION pi;    ZeroMemory(&si, sizeof(si));    si.cb = sizeof(si);    si.dwFlags = STARTF_USESHOWWINDOW;    si.wShowWindow = SW_HIDE; // 不显示窗口      ZeroMemory(&pi, sizeof(pi));
    // 创建进程      if (!CreateProcessA(        filePath, // 程序路径          NULL,     // 命令行参数          NULL,     // 进程句柄不可继承          NULL,     // 线程句柄不可继承          FALSE,    // 设置句柄继承为 FALSE          0,        // 没有创建标志          NULL,     // 使用父进程的环境块          NULL,     // 使用父进程的起始目录           &si,      // 指向 STARTUPINFO 结构          &pi)      // 指向 PROCESS_INFORMATION 结构          ) {        printf("CreateProcess failed (%d).\n", GetLastError());        return;    }    // 等待直到子进程退出      WaitForSingleObject(pi.hProcess, INFINITE);    // 关闭进程和线程句柄      CloseHandle(pi.hProcess);    CloseHandle(pi.hThread);}
int main(){    WriteBat();    WritePar();    XYD flyxyd = { 1.0, 1.0 };      // 起点坐标    XYD Photo_list[] = { {2.0, 2.0}, {3.0, 3.0}, {4.0, 4.0} };     // 其他点坐标    int Photo_list_size = sizeof(Photo_list) / sizeof(Photo_list[0]);    WriteTsp(flyxyd, Photo_list, Photo_list_size);    StartProcess("LKH.bat");    return 0;}

以上代码已基本上实现了LKH算法的使用，下面我将使用Easyx来可视化随机生成一些点，然后使用LKH算法来求解连接这些点的最短距离。

源码如下

///////////////////////////////////////////////////// 程序名称：TSP问题的LKH算法实践应用// 编译环境：Mictosoft Visual Studio 2022, EasyX_20200315(beta)// 作　　者：luoyh <2864292458@qq.com>// 公 众 号：C语言研究// 最后修改：2024-7-6//
#define  _CRT_SECURE_NO_WARNINGS#include <stdio.h>  #include <stdlib.h>  #include <string.h>  #include <Windows.h>#include <time.h> #include <graphics.h>#include <conio.h>
typedef struct{    int X;    int Y;} Photo_list;
int* tour = NULL;
typedef struct{    int num;    int X;    int Y;
} MP;MP mypoints[101];
void WriteBat(){    const char* batContent = "@echo off\r\npath=%path%;\r\nLKH-3.exe Par.par\r\n";    const char* fileName = "LKH.bat";     FILE* file = fopen(fileName, "w");    if (file == NULL)    {        perror("无法打开文件");        return;    }    fprintf(file, "%s", batContent);    fclose(file);}
void WritePar() {    const char* parContent =        "PROBLEM_FILE = Tsp.tsp\r\n"        "MOVE_TYPE = 5\r\n"        "PATCHING_C = 3\r\n"        "PATCHING_A = 2\r\n"        "RUNS = 1\r\n"        "TOUR_FILE = ./output.txt\r\n";    const char* fileName = "Par.par";    FILE* file = fopen(fileName, "w");    if (file == NULL)    {        perror("Failed to open file");        return;    }    fprintf(file, "%s", parContent);    fclose(file);}
//typedef struct//{//    double X;//    double Y;//} XYD;
void WriteTsp(Photo_list flyxyd, Photo_list* Photo_list, int Photo_list_size){    int POINTS = Photo_list_size + 1;
    char tspContent[4096]; // 假设内容不会超过4096个字符      char buffer[256];    strcpy(tspContent, "NAME : TSPDATA\r\n");    strcat(tspContent, "COMMENT : drilling problem (Ludwig)\r\n");    strcat(tspContent, "TYPE : TSP\r\n");    sprintf(buffer, "DIMENSION : %d\r\n", POINTS);    strcat(tspContent, buffer);    strcat(tspContent, "EDGE_WEIGHT_TYPE : EUC_2D\r\n");    strcat(tspContent, "NODE_COORD_SECTION\r\n");    sprintf(buffer, "1 %d %d\r\n", flyxyd.X, flyxyd.Y);    mypoints[0].num = 1;    mypoints[0].X = flyxyd.X;    mypoints[0].Y = flyxyd.Y;    strcat(tspContent, buffer);
    for (int i = 0; i < Photo_list_size; i++)    {        sprintf(buffer, "%d %d %d\r\n", i + 2, Photo_list[i].X, Photo_list[i].Y);
        mypoints[i+1].num = i+2;        mypoints[i+1].X = Photo_list[i].X;        mypoints[i+1].Y = Photo_list[i].Y;
        strcat(tspContent, buffer);    }    strcat(tspContent, "EOF\r\n");    const char* fileName = "Tsp.tsp";    FILE* file = fopen(fileName, "w");    if (file == NULL)    {        perror("Failed to open file");        return;    }
    fprintf(file, "%s", tspContent);    fclose(file);}
void StartProcess(const char* filePath){    STARTUPINFOA si;    PROCESS_INFORMATION pi;    ZeroMemory(&si, sizeof(si));    si.cb = sizeof(si);    si.dwFlags = STARTF_USESHOWWINDOW;    si.wShowWindow = SW_HIDE; // 不显示窗口      ZeroMemory(&pi, sizeof(pi));
    // 创建进程      if (!CreateProcessA(        filePath, // 程序路径          NULL,     // 命令行参数          NULL,     // 进程句柄不可继承          NULL,     // 线程句柄不可继承          FALSE,    // 设置句柄继承为 FALSE          0,        // 没有创建标志          NULL,     // 使用父进程的环境块          NULL,     // 使用父进程的起始目录           &si,      // 指向 STARTUPINFO 结构          &pi)      // 指向 PROCESS_INFORMATION 结构          ) {        printf("CreateProcess failed (%d).\n", GetLastError());        return;    }    // 等待直到子进程退出      WaitForSingleObject(pi.hProcess, INFINITE);    // 关闭进程和线程句柄      CloseHandle(pi.hProcess);    CloseHandle(pi.hThread);}
int readtxt(const char* filePath){    FILE* file;    char line[1024];    int dimension;        int tourSize = 0;    int temp;
    // 打开文件      file = fopen(filePath, "r");    if (!file)     {        perror("Failed to open file");        return EXIT_FAILURE;    }
    // 跳过文件头信息      while (fgets(line, sizeof(line), file))     {        if (strncmp(line, "DIMENSION : ", 12) == 0)        {            sscanf(line, "DIMENSION : %d", &dimension);            tour = (int*)malloc(sizeof(int) * dimension);            if (!tour)            {                perror("Failed to allocate memory for tour");                fclose(file);                return EXIT_FAILURE;            }        }        else if (strncmp(line, "TOUR_SECTION", 12) == 0)        {            break; // 找到TOUR_SECTION，开始读取路径数据          }    }
    // 读取路径数据      while (fgets(line, sizeof(line), file)) {        if (sscanf(line, "%d", &temp) == 1 && temp != -1) {            tour[tourSize++] = temp;        }        else if (temp == -1) {            break; // 读到-1表示路径结束          }    }
    // 输出读取的路径数据      for (int i = 0; i < tourSize; i++)     {        printf("%d\n", tour[i]);    }    fclose(file);}
int main(){    WriteBat();    WritePar();      initgraph(640, 480);    setbkcolor(WHITE);    cleardevice();    setfillcolor(BLACK);
    Photo_list flyxyd = { 320,240 };      // 起点坐标    solidcircle(flyxyd.X, flyxyd.Y, 4);   /* outtextxy(flyxyd.X, flyxyd.Y, _T("1"));*/    Photo_list points[100]; // 创建一个存储100个点的数组  
    srand(time(NULL)); // 设置随机数种子      settextcolor(BLACK);    for (int i = 0; i < 100; i++)    {        points[i].X = 10 + rand() / (RAND_MAX / (630 - 10));        points[i].Y = 10 + rand() / (RAND_MAX / (470 - 10));        solidcircle(points[i].X,points[i].Y,4);        /*TCHAR s[5];        _stprintf(s, _T("%d"), i);        outtextxy(points[i].X, points[i].Y,s);*/    }       int Photo_list_size = 100;    WriteTsp(flyxyd, points, Photo_list_size);    StartProcess("LKH.bat");    readtxt("output.txt");
    setlinecolor(BLACK);    setlinestyle(PS_SOLID,3);    for (int i = 0; i < 100; i++)    {        line(mypoints[tour[i]-1].X, mypoints[tour[i] - 1].Y, mypoints[tour[i+1] - 1].X, mypoints[tour[i+1] - 1].Y);        Sleep(200);    }    // 首尾相连    line(mypoints[tour[100]-1].X, mypoints[tour[100]-1].Y, mypoints[tour[0]-1].X, mypoints[tour[0]-1].Y);    _getch();    return 0;}

通过这个案例，我们可以获得一些启示。例如，在规划旅行路线时，我们可以将城市视为点，并探索如何以最短路径游览更多城市。同样，在扫地机器人的应用场景中，我们也可以将屋内的每块地板砖视为一个点，进而生成最高效、最短的清扫路径。

http://mp.weixin.qq.com/s?__biz=MzU4Mjg2Nzc3Mw==&mid=2247485622&idx=1&sn=afe13c9a34c5ecf73418e46b6551e42d

C语言研究

写给自己的笔记，时常写写，时常看看，仅此而已。