PAT甲级L3-014周游世界：双目标优化的DFS实战解析

地铁线路图上密密麻麻的站点连线让人眼花缭乱，而算法竞赛中的图论问题往往就是将这些现实场景抽象为数学模型。PAT甲级L3-014"周游世界"题目正是这样一个典型案例——它要求我们在复杂的交通网络中寻找既经停站最少又换乘次数最少的最优路径。这不仅是算法能力的考验，更是对问题建模和优化思维的挑战。

1. 问题分析与建模关键

题目描述了一个由多家运输公司组成的联盟网络，每家公司的线路由一系列站点构成。我们需要处理多个查询，每个查询给出起点和终点，要求找到满足以下条件的路径：

1. 经停站最少 （路径长度最短）
2. 在路径长度相同的情况下，换乘次数最少

这实际上是一个 双目标优化问题 ，其中路径长度是首要优化目标，换乘次数是次要优化目标。关键在于如何将现实中的换乘概念转化为可计算的图论模型。

1.1 图的构建策略

虽然题目描述的是运输线路，但我们可以将其建模为 无向图 ：

• 顶点 ：各个站点（4位数字编号）
• 边 ：相邻站点之间的连接，边权为1（表示一个经停站）
• 附加信息 ：每条边所属的公司编号

特别需要注意的是题目给出的几个重要约束条件：

1. 每个换乘点（多条线路交叉的站点）涉及的公司不超过5家
2. 线路可能是环线，但不会不经过任何中间站点直接返回
3. 所有线路都是双向的

这些约束条件直接影响我们的算法选择——特别是DFS的可行性。由于每个换乘点的分支不超过5个，DFS在最坏情况下也不会出现指数爆炸。

1.2 双目标优化的处理技巧

我们需要同时考虑两个优化目标，但它们的优先级不同：

1. 首要目标 ：路径长度最短（经停站最少）
2. 次要目标 ：在路径长度相同的情况下，换乘次数最少

这种层级化的优化目标可以通过以下方式实现：

if(cnt < minCnt || (cnt == minCnt && count(tempath) < minTrans)) {
    minCnt = cnt;
    minTrans = count(tempath);
    path = tempath;
}

其中 cnt 是当前路径的经停站数， count(tempath) 计算当前路径的换乘次数。

2. DFS算法设计与优化

虽然Dijkstra算法是单源最短路径的经典解法，但在这个问题中DFS反而更具优势，原因在于：

1. 需要记录完整路径而不仅仅是距离
2. 需要在相同长度的路径中比较换乘次数
3. 题目数据规模适中（N≤100，每个查询的站点数≤100）

2.1 基础DFS框架

核心的DFS递归结构如下：

void dfs(int u, int end, int cnt) {
    if(u == end) {
        // 到达终点，比较并更新最优路径
        if(cnt < minCnt || (cnt == minCnt && count(tempath) < minTrans)) {
            minCnt = cnt;
            minTrans = count(tempath);
            path = tempath;
        }
        return;
    }
    
    for(int v : G[u]) {
        if(!vis[v]) {
            vis[v] = 1;
            tempath.push_back(v);
            dfs(v, end, cnt + 1);
            vis[v] = 0;
            tempath.push_back(v);
        }
    }
}

2.2 关键优化技巧

虽然基础DFS可以解决问题，但通过以下优化可以显著提高效率：

1. 提前剪枝 ：当当前路径长度已经超过已知最短路径时，直接返回
2. 记忆化 ：对于已经处理过的状态进行缓存（虽然本题中效果有限）
3. 访问控制 ：使用 vis 数组避免环路

优化后的DFS核心：

void dfs(int u, int end, int cnt) {
    if(cnt > minCnt) return; // 关键剪枝：当前路径已不可能更优
    
    if(u == end) {
        int trans = count(tempath);
        if(cnt < minCnt || (cnt == minCnt && trans < minTrans)) {
            minCnt = cnt;
            minTrans = trans;
            path = tempath;
        }
        return;
    }
    
    for(int v : G[u]) {
        if(!vis[v]) {
            vis[v] = 1;
            tempath.push_back(v);
            dfs(v, end, cnt + 1);
            tempath.pop_back();
            vis[v] = 0;
        }
    }
}

2.3 换乘次数计算

换乘次数的计算是本题的一个关键点。我们需要比较相邻边所属的公司是否相同：

int count(vector<int>& path) {
    int trans = 0;
    int preLine = 0;
    
    for(int i = 1; i < path.size(); i++) {
        int currLine = line[path[i-1]][path[i]];
        if(currLine != preLine) {
            trans++;
            preLine = currLine;
        }
    }
    
    return trans - 1; // 换乘次数 = 公司变化次数 - 1
}

注意初始公司为0（虚拟公司），所以最后需要减1得到实际的换乘次数。

3. 完整代码实现与关键注释

以下是整合了所有优化策略的完整C++实现，包含关键注释：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10010; // 最大站点数（4位编号）

vector<int> G[MAXN];    // 邻接表存储图结构
int line[MAXN][MAXN];   // 记录两点间的公司编号
vector<int> path, tempath; // 最终路径和临时路径
int minCnt, minTrans;   // 最小经停数和最小换乘数
bool vis[MAXN];         // 访问标记数组

// 计算路径的换乘次数
int countTrans(vector<int>& path) {
    int trans = 0;
    int preLine = 0;
    
    for(int i = 1; i < path.size(); i++) {
        int currLine = line[path[i-1]][path[i]];
        if(currLine != preLine) {
            trans++;
            preLine = currLine;
        }
    }
    
    return trans > 0 ? trans - 1 : 0; // 处理边界情况
}

// DFS搜索最优路径
void dfs(int u, int end, int cnt) {
    if(cnt > minCnt) return; // 剪枝：当前路径已不可能更优
    
    if(u == end) {
        int trans = countTrans(tempath);
        if(cnt < minCnt || (cnt == minCnt && trans < minTrans)) {
            minCnt = cnt;
            minTrans = trans;
            path = tempath;
        }
        return;
    }
    
    for(int v : G[u]) {
        if(!vis[v]) {
            vis[v] = true;
            tempath.push_back(v);
            dfs(v, end, cnt + 1);
            tempath.pop_back();
            vis[v] = false;
        }
    }
}

int main() {
    int n, m, k;
    cin >> n;
    
    // 构建图结构
    for(int i = 1; i <= n; i++) {
        cin >> m;
        int pre, tmp;
        cin >> pre;
        for(int j = 1; j < m; j++) {
            cin >> tmp;
            G[pre].push_back(tmp);
            G[tmp].push_back(pre);
            line[pre][tmp] = line[tmp][pre] = i;
            pre = tmp;
        }
    }
    
    cin >> k;
    while(k--) {
        int start, end;
        cin >> start >> end;
        
        // 初始化搜索状态
        memset(vis, 0, sizeof(vis));
        minCnt = minTrans = INT_MAX;
        tempath.clear();
        tempath.push_back(start);
        vis[start] = true;
        
        dfs(start, end, 0);
        
        // 输出结果
        if(minCnt == INT_MAX) {
            cout << "Sorry, no line is available." << endl;
            continue;
        }
        
        cout << minCnt << endl;
        int preLine = 0, preTrans = start;
        
        for(int i = 1; i < path.size(); i++) {
            int currLine = line[path[i-1]][path[i]];
            if(currLine != preLine) {
                if(preLine != 0) {
                    printf("Go by the line of company #%d from %04d to %04d.\n", 
                           preLine, preTrans, path[i-1]);
                }
                preLine = currLine;
                preTrans = path[i-1];
            }
        }
        printf("Go by the line of company #%d from %04d to %04d.\n", 
               preLine, preTrans, end);
    }
    
    return 0;
}

4. 算法扩展与变种思考

虽然DFS解决了这个问题，但我们可以进一步思考其他可能的解法及其适用场景：

4.1 BFS解法对比

BFS天然适合无权图的最短路径问题，可以这样改造：

1. 队列元素 ：需要存储完整路径而不仅仅是当前节点
2. 终止条件 ：第一次到达终点时即为最短路径
3. 换乘优化 ：需要记录所有等长的最短路径，然后比较换乘次数

BFS的优势在于不需要递归，空间消耗更可控，但实现起来可能不如DFS直观。

4.2 Dijkstra算法的适用性

如果我们将问题转化为：

• 边权为1（经停站）
• 换乘次数作为第二权重

可以设计一个考虑双权重的Dijkstra算法：

struct State {
    int node;
    int stops;
    int transfers;
    int lastCompany;
    vector<int> path;
    
    bool operator>(const State& other) const {
        if(stops != other.stops) return stops > other.stops;
        return transfers > other.transfers;
    }
};

这种解法虽然理论复杂度更优，但实现复杂度显著增加，对于本题的数据规模可能得不偿失。

4.3 实际应用中的优化方向

在实际的交通导航系统中，类似问题通常会考虑更多因素：

1. 分层图模型 ：将不同交通工具建模为不同层次的图
2. A*算法 ：引入启发式函数加速搜索
3. 预处理技术 ：对常用站点预先计算部分结果
4. 实时更新 ：处理线路临时变动的情况

这些高级技术虽然超出了本题范围，但了解它们有助于开拓算法设计的思路。