求解骑士最短路径的Branch-and-Bound算法时间空间复杂度分析

问题描述 #

我需要计算求解棋盘上骑士从起点到终点最短路径的分支定界（Branch-and-Bound）算法的时间与空间复杂度。我自行计算得到复杂度为O(n²)，但考虑到分支定界算法的复杂度受限界规则影响，其复杂度应该高于O(n²)。

算法代码（注释汉化） #

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义Posicao结构体，存储骑士的起点和终点坐标
typedef struct
{
    int x, y;
} Posicao;

typedef struct no
{
    Posicao pos;
    int 步数;
    struct no *父节点;
} no;

int **创建棋盘(int **tabuleiro, int 棋盘大小)
{
    // 创建棋盘矩阵，所有位置初始化为-1
    tabuleiro = (int **)malloc(棋盘大小 * sizeof(int *));
    for (int i = 0; i < 棋盘大小; i++)
    {
        tabuleiro[i] = (int *)malloc(棋盘大小 * sizeof(int));
        for (int j = 0; j < 棋盘大小; j++)
        {
            tabuleiro[i][j] = -1;
        }
    }

    return tabuleiro;
}

// 创建新节点
// 参数：骑士在棋盘上的坐标、到达该位置的步数、父节点指针
no *创建节点(int x, int y, int 步数, no *父节点)
{
    no *tree = (no *)malloc(sizeof(no));
    tree->pos.x = x;
    tree->pos.y = y;
    tree->步数 = 步数;
    tree->父节点 = 父节点;
    return tree;
}

// 递归函数，在棋盘上标记骑士走过的路径，用0、1、2...表示步数
// 参数：节点指针、棋盘矩阵
void 打印路径(no *node, int **tabuleiro)
{
    if (node == NULL) // 递归终止条件
        return;

    打印路径(node->父节点, tabuleiro); // 遍历整个路径树

    if (tabuleiro[node->pos.x][node->pos.y] == -1)
    {
        static int 步序号 = 0;                          // 静态变量，保持步序号在递归调用中持续递增
        tabuleiro[node->pos.x][node->pos.y] = 步序号++; // 标记当前位置的步序号
    }
}

// 验证坐标(x,y)是否在棋盘范围内
int 坐标合法(int x, int y, int 棋盘大小)
{
    return (x >= 0 && x < 棋盘大小 && y >= 0 && y < 棋盘大小);
}

// 骑士的8种可能移动方式（相对于当前位置[x,y]的偏移量）
int 移动方式[8][2] = {
    {2, 1},  // x+2，y+1
    {2, -1}, // x+2，y-1
    {-2, 1}, // x-2，y+1
    {-2, -1},// x-2，y-1
    {1, 2},  // x+1，y+2
    {1, -2}, // x+1，y-2
    {-1, 2}, // x-1，y+2
    {-1, -2} // x-1，y-2
};

// 寻找骑士从起点到终点的最短路径
// 参数：起点坐标、终点坐标、棋盘矩阵、棋盘大小
int 最短路径(Posicao 起点, Posicao 终点, int **tabuleiro, int 棋盘大小)
{
    if (!坐标合法(起点.x, 起点.y, 棋盘大小) || !坐标合法(终点.x, 终点.y, 棋盘大小))
    {
        return -1;
    }

    // 初始化访问矩阵，记录骑士已走过的位置
    int **已访问 = (int **)malloc(棋盘大小 * sizeof(int *));
    for (int i = 0; i < 棋盘大小; i++)
    {
        已访问[i] = (int *)malloc(棋盘大小 * sizeof(int));
        for (int j = 0; j < 棋盘大小; j++)
            已访问[i][j] = 0; // 初始所有位置未访问
    }
    // 创建根节点，代表骑士的初始位置
    no *根节点 = 创建节点(起点.x, 起点.y, 0, 0);

    // 队列存储待探索的节点（模拟优先队列）
    no **队列 = (no **)malloc(棋盘大小 * 棋盘大小 * sizeof(no *));
    int 队首 = 0, 队尾 = 0;

    // 将根节点入队，并标记起点已访问
    队列[队尾++] = 根节点;
    已访问[起点.x][起点.y] = 1;

    int 上界 = INT_MAX; // 初始化最短路径的上界为无穷大

    // 循环探索队列中的节点
    while (队首 < 队尾)
    {
        no *当前节点 = 队列[队首++];
        int x = 当前节点->pos.x;
        int y = 当前节点->pos.y;
        int 当前步数 = 当前节点->步数;
        // 检查当前位置是否为终点
        if (x == 终点.x && y == 终点.y)
        {
            打印路径(当前节点, tabuleiro); // 标记路径
            for (int i = 0; i < 棋盘大小; i++)
            {
                free(已访问[i]);
            }
            free(已访问);
            free(队列);
            return 当前步数;
        }
        // 探索所有8种可能的移动
        for (int i = 0; i < 8; i++)
        {
            int 新x = x + 移动方式[i][0];
            int 新y = y + 移动方式[i][1];

            if (坐标合法(新x, 新y, 棋盘大小) && !已访问[新x][新y]) // 验证新坐标合法且未被访问
            {
                int 下界 = abs(终点.x - 新x) + abs(终点.y - 新y); // 计算曼哈顿距离作为下界

                if (当前步数 + 1 + 下界 < 上界)
                {
                    已访问[新x][新y] = 1;
                    队列[队尾++] = 创建节点(新x, 新y, 当前步数 + 1, 当前节点); // 标记已访问并将新节点入队
                }
            }
        }
    }
    // 未找到路径时释放内存
    for (int i = 0; i < 棋盘大小; i++)
    {
        free(已访问[i]);
    }
    free(已访问);
    free(队列);
    return (上界 == INT_MAX) ? -1 : 上界;
}

// 打印棋盘，显示骑士的移动路径
// 参数：棋盘矩阵、棋盘大小
void 打印棋盘(int **tabuleiro, int 棋盘大小)
{
    printf("棋盘:\n");
    for (int i = 0; i < 棋盘大小; i++)
    { // 遍历行
        for (int j = 0; j < 棋盘大小; j++)
        { // 遍历列
            if (tabuleiro[i][j] == -1)
                printf(". ");
            else
                printf("%2d ", tabuleiro[i][j]);
        }
        printf("\n");
    }
}

int 读取文件数据(const char *文件路径, int *棋盘大小, Posicao *起点, Posicao *终点)
{
    FILE *数据文件;

    // 以只读模式打开文件
    数据文件 = fopen(文件路径, "r");

    if (数据文件 == NULL)
    {
        printf("打开文件失败!\n");
        return 1;
    }

    // 读取棋盘大小
    if (fscanf(数据文件, "%d\n", 棋盘大小) != 1)
    {
        printf("读取棋盘大小失败!\n");
        fclose(数据文件);
        return 1;
    }

    // 读取起点坐标
    if (fscanf(数据文件, "%d %d\n", &起点->x, &起点->y) != 2)
    {
        printf("读取起点坐标失败!\n");
        fclose(数据文件);
        return 1;
    }

    // 读取终点坐标
    if (fscanf(数据文件, "%d %d\n", &终点->x, &终点->y) != 2)
    {
        printf("读取终点坐标失败!\n");
        fclose(数据文件);
        return 1;
    }
    printf("棋盘大小: %d\n", *棋盘大小);
    printf("起点坐标: %d %d\n", 起点->x, 起点->y);
    printf("终点坐标: %d %d\n", 终点->x, 终点->y);

    // 关闭文件
    fclose(数据文件);

    return 0;
}

void 释放棋盘(int **tabuleiro, int 棋盘大小)
{
    for (int i = 0; i < 棋盘大小; i++)
    { // 逐行释放矩阵内存
        free(tabuleiro[i]);
    }

    free(tabuleiro); // 释放棋盘指针内存
}

void 打印结果(int 结果, int **tabuleiro, int 棋盘大小)
{
    if (结果 != -1)
    {
        printf("找到最短路径，共%d步:\n", 结果); // 打印步数
        打印棋盘(tabuleiro, 棋盘大小);         // 打印路径棋盘
    }
    else
        printf("无法找到路径。\n"); // 未找到路径的提示
}

int main()
{
    const char *文件路径 = "../../data/tab2.txt";

    int 棋盘大小;
    Posicao 起点, 终点;

    // 读取文件数据
    if (读取文件数据(文件路径, &棋盘大小, &起点, &终点) != 0)
    {
        // 处理文件读取错误
        fprintf(stderr, "读取文件失败: %s\n", 文件路径);
        return 1;
    }

    int **tabuleiro = NULL;
    tabuleiro = 创建棋盘(tabuleiro, 棋盘大小);

    int 结果 = 最短路径(起点, 终点, tabuleiro, 棋盘大小);

    打印结果(结果, tabuleiro, 棋盘大小);

    // 释放棋盘内存
    for (int i = 0; i < 棋盘大小; i++)
    {
        free(tabuleiro[i]);
    }
    free(tabuleiro);

    return 0;
}

复杂度分析 #

时间复杂度 #

你的初始计算是正确的，该算法的时间复杂度为O(n²)，原因如下：

1. 算法本质是带剪枝的广度优先搜索（BFS）：每个棋盘位置最多被标记为已访问一次，一旦标记就不会再被处理。
2. 剪枝逻辑的作用是减少不必要的节点扩展，但不会增加最坏情况的复杂度：即使剪枝完全失效（比如起点和终点在棋盘对角，曼哈顿距离下界无法过滤任何节点），算法也只会遍历所有n²个节点，每个节点最多执行8次移动检查（常数时间操作），因此总时间复杂度为O(8*n²)=O(n²)。

你觉得复杂度应该高于O(n²)，可能是混淆了分支定界算法在不同问题中的表现。分支定界在旅行商问题这类解空间为指数级的问题中，最坏复杂度可能很高，但在骑士路径问题中，解空间是有限的棋盘节点（n²个），因此复杂度不会超过BFS的线性级（相对于节点数）。

空间复杂度 #

空间复杂度同样为O(n²)，主要来自三部分：

• 访问矩阵：占用n²的存储空间，用于记录已访问的棋盘位置；
• 队列：最坏情况下，队列需要存储所有n²个节点（比如棋盘全连通，所有节点都被入队）；
• 路径节点树：每个节点包含父指针，最坏情况下需要存储所有n²个节点的路径信息。

内容的提问来源于stack exchange，提问作者Yuri Gabriel dos Reis Souza