字节跳动19春招研发笔试旅行商(TSP)问题 (记忆化搜索)

ゝ一纸荒年。 2022-02-18 23:41 333阅读 0赞

### 字节跳动19春招研发笔试 ###

*  前言
 *  思路
 *  代码 ( C )
 *  对比
 *  结语
 *  附录一 (精简版代码)
 *  附录二 (笔试的代码)

# 前言 #

不会做, 只会DFS (贪婪 + 分支界限都试了, 然而只过了 50%的测试用例, 其他的超时), 学!!

# 思路 #

贪婪 (先搜索最近的) 和分支界限都只能提高最优情况的性能, 在最坏情况下仍然没有帮助. 所以 DFS 最坏情况下的复杂度是  ( n − 1 ) ! (n -1)! (n−1)! (阶乘就是爆炸)  
仔细观察会发现, 假如一共有6个城市, 那么  
1- perm\{2, 3, 4\} - 5 - 6 - 1 这一共6种方案中, 都是在访问完 \{1, 2, 3, 4\} 后再到5, 最后访问6和1的. 所以**出现了重复的子集**.  
**因此, 可以用一个数组来保存一个状态, 表示在访问完 \{1, 2, 3, 4\} 这个状态后, 从5开始访问其他所有节点的最优解**  
此时状态用二进制编码, 出口用单独一个数字编码, 即可建表.

我再多解释几句:  
表的形式是  d p \[ s t a t u s \] \[ o u t \] dp\[status\]\[out\] dp\[status\]\[out\], 其中 status 的每个位表示是否已经访问过这个城市, 而 out 表示**我现在走到了这个城市, 然后以这个城市为起点寻找下一个城市**. 也就是说我现在已经访问过了 status(二进制1的个数) + 1 个(out)城市, 之所以要把 out 单独从 status 中抽离出来是为了唯一确定这个状态的出口. 举个例子:  
 d p \[ 0 \] \[ 0 \] dp\[0\]\[0\] dp\[0\]\[0\] 表示我一个城市还没访问过, 现在在 0 这个城市 (起点), 从 0 开始寻找下一个城市.  
 d p \[ 7 \] \[ 4 \] dp\[7\]\[4\] dp\[7\]\[4\] 表示我已经访问过了 \{0, 1, 2\} ( 7 = 二进制的111), 现在走到了 4 这个城市, 然后从 4 这个城市开始寻找下一个目的地.

# 代码 ( C ) #

#include <stdio.h>
    #define MAXN 20
    #define INF (1 << 30)
    
    int min(int a, int b) { 
    	return (a < b) ? a : b;
    }
    
    int adj[MAXN][MAXN];
    int dp[1 << MAXN][MAXN];
    int full = 0;
    int status;
    
    /* 在调用这个函数的时刻, 表示已经走过了 status 所标注的地点, !!以及!! out 这个地点 (还没标注) 返回的是在这个状态下走完剩余剩余城市并返回城市 0 的最优值 */
    int dfs(int out) { 
    	// 记忆化搜索的标准起手, 如果已经存储了这个状态的值, 直接返回
    	int result = dp[status][out];
    	if (result) return result;
    
    	// (status | (1 << out)) 表示我现在已经遍历了这些城市, 如果全为 1 的话, 只需要返回 out (现在的位置) 和 0 (起点) 的距离.
    	if ((status | (1 << out)) == full) return adj[out][0];
    
    	// 设置状态 (已经访问过这个城市)
    	status |= 1 << out;
    
    	// 寻找最优解
    	result = INF;
    	for (int i = 0; i < MAXN; i++) { 
    		if (status & (1 << i)) continue;
    		result = min(result, adj[out][i] + dfs(i));
    	}
    
    	// 恢复状态
    	status &= ~(1 << out);
    	
    	// 记录最优解, 记忆化搜索的标准后摇
    	dp[status][out] = result;
    	return result;
    }
    
    int main() { 
    	// 我觉得最简单的写法是 full = ~(-1 << MAXN), 但是 gcc 说给负数做 shift 是 undefined...
    	for (int i = 0; i < MAXN; i++) { 
    		full |= (1 << i);
    	}
    	int n;
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) { 
    		for (int j = 0; j < n; j++) { 
    			int dist;
    			scanf("%d", &dist);
    			adj[i][j] = adj[j][i] = dist;
    		}
    	}
    	printf("%d\n", dfs(0));
    }

# 对比 #

为了可复现, 随机数种子为 1, (srand(1))

<table> 
 <thead> 
  <tr> 
   <th>节点个数 \ 耗时</th> 
   <th>DFS (剪枝 + 贪心)</th> 
   <th>DFS (记忆化搜索)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>10</td> 
   <td>0.000923</td> 
   <td>0.000763</td> 
  </tr> 
  <tr> 
   <td>15</td> 
   <td>0.330568</td> 
   <td>0.022010</td> 
  </tr> 
  <tr> 
   <td>20</td> 
   <td>?</td> 
   <td>1.232345</td> 
  </tr> 
 </tbody> 
</table>

上表中的 “?” 表示, 当我用 1 作为随机数种子的时候, 这个 DFS 的耗时竟然只有 0.8秒多, 比记忆化搜索快, 把我吓到了… 然后我用 clock() 作为种子, 发现在其他时候, 这个 DFS 的耗时超过了一分钟, 而无论种子是多少, 记忆化搜索都稳定在 1.23 秒左右. 也就是说 **DFS (剪枝 + 贪心) 的上下限差异很大, 而且他的最坏情况耗时是不可承受的.**

同时在节点分别取20, 21, 22 时, 记忆化搜索的耗时平均是 1.23, 2.72 和 6.00. 呈指数增长, 一般试题取节点为 20 正好能在两秒内跑完.

# 结语 #

在笔试之前刷了很多头条历年的题, 发现都是很基础的并查集, 图论算法和经典 DP 啥的, 没想到这次笔试竟然还有这样的优化问题以及下一个博客要写的智力题…  
所以, 学啊! 学!

# 附录一 (精简版代码) #

#include <stdio.h>
    #define MAXN 20
    #define INF (1 << 30)
    int min(int a, int b) {  return (a < b) ? a : b; }
    int adj[MAXN][MAXN];
    int dp[1 << MAXN][MAXN];
    int full = ~(-1<<MAXN);
    int status, n;
    int dfs(int out) { 
    	if (dp[status][out]) return dp[status][out];
    	if ((status | (1 << out)) == full) return adj[out][0];
    	status |= 1 << out;
    	int result = INF;
    	for (int i = 0; i < MAXN; i++) result = (status & (1 << i)) ? result : min(result, adj[out][i] + dfs(i));
    	status &= ~(1 << out);
    	return dp[status][out] = result;
    }
    int main() { 
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", adj + i * MAXN + j);
    	printf("%d\n", dfs(0));
    }

# 附录二 (笔试的代码) #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct { 
        int to;
        int weight;
    } Edge;
    
    int n;
    Edge adj[20][20];
    int minWeight[20];
    int mark[20];
    int best = 1 << 30;
    int current = 0;
    
    int min(int a, int b) { 
        return (a < b) ? a : b;
    }
    
    int compare(const void* a, const void* b) { 
        return ((Edge*)a)->weight - ((Edge*)b)->weight;
    }
    
    void dfs(int city, int cityCount) { 
        if (current >= best) return;
        int temp = current;
        for (int i = 0; i < n; i++) { 
            if (mark[i]) continue;
            temp += minWeight[i];
            if (temp >= best) return;
        }
        mark[city] = 1;
        cityCount++;
        if (cityCount == n) { 
            for (int next = 0; next < n; next++) { 
                Edge e = adj[city][next];
                if (e.to) continue;
                if ((current + e.weight) < best) best = current + e.weight;
            }
        } else { 
            for (int next = 0; next < n; next++) { 
                Edge e = adj[city][next];
                if (mark[e.to]) continue;
                current += e.weight;
                dfs(e.to, cityCount);
                current -= e.weight;
            }   
        }
        cityCount--;
        mark[city] = 0;
    } 
    
    int main() { 
        scanf("%d", &n);
        for (int i = 0; i < n; i++) { 
            minWeight[i] = 1 << 30;
        }
        for (int i = 0; i < n; i++) { 
            adj[i][i].to = i;
            adj[i][i].weight = 1 << 30;
            for (int j = 0; j < n; j++) { 
                int price;
                scanf("%d", &price);
                adj[i][j].to = j;
                adj[i][j].weight = price;
                adj[j][i].to = i;
                adj[j][i].weight = price;
                minWeight[i] = min(minWeight[i], price);
                minWeight[j] = min(minWeight[i], price);
            }
        }
        for (int i = 0; i < n; i++) { 
            qsort(adj[i], n, sizeof(Edge), compare);
        }
        dfs(0, 0);
        printf("%d\n", best);
    }