刚看到一个帖子，讨论的是关于面试薪资谈判的博弈。一位求职者面试拿到了40K的offer，但HR要求提供银行流水，结果发现他上一家的薪资是25K每月。HR看了流水后，立刻改口说最多只能给到30K。这位朋友的做法很干脆，直接拒绝了这份offer。
在我看来，这件事的关键不在于40K还是30K，而在于规则的透明度。既然前期沟通明确了是40K，后面再用流水来压价，本质上就是把薪酬谈判变成了一场翻旧账的算计。站在求职者的角度，拒绝并不丢人，这是在为自己的价值预期正确定价。
不过，HR要求流水、公司需要控制人力成本，也是现实的考量。更成熟的做法是尽早明确薪酬评估的逻辑，避免让对方产生不必要的期待。
归根结底，职场中清楚自己的底线，远比纠结那一两万的薪资差额更重要。姿态端正，路反而走得更稳。
从面试博弈到算法难题：旅行销售员问题
这让我想起前几天晚上九点多，在公司楼下的便利店买咖啡时，我们组的小李一边排队一边跟我吐槽：“我下周要出差跑好几个城市，老板还问我能不能把总路费压到最低，这简直就是在出算法题啊！”我愣了一下，这不就是经典的“旅行销售员问题”（Traveling Salesman Problem, TSP）吗？当时就在餐巾纸上给他推演了一遍解题思路。
我们来脑补一下题目：有若干个城市，一个销售员需要从某个城市出发，访问所有城市各一次，最后再回到起点城市。每两个城市之间都有确定的路费（或距离），问题是：如何规划访问顺序，使得总花费最小？这就是一个非常典型的业务需求。
人脑的第一反应通常是：既然访问顺序影响总路费，那就把所有的可能顺序都列出来，挨个算一遍，选总花费最小的那个。
换成代码思路就是：除了起点城市，对其他所有城市进行全排列。对每一个排列，计算按照这个顺序走一遍的总距离，最后取最小值。
用 Python 写一个最暴力的解法，大概是下面这样：
import itertools
def tsp_bruteforce(dist, start=0):
n = len(dist)
cities = [i for i in range(n) if i != start]
ans = float('inf')
for perm in itertools.permutations(cities):
cost = 0
cur = start
# 按顺序访问城市
for nxt in perm:
cost += dist[cur][nxt]
cur = nxt
# 最后回到起点
cost += dist[cur][start]
ans = min(ans, cost)
return ans
问题来了，这个方法的计算复杂度是 O(n!)。城市数量稍多一点，计算就直接卡死了。10个城市勉强还能算算，15个城市你的电脑基本就开始“思考人生”了。所以，暴力枚举属于“只能跑跑小样例，完全无法投入实战”的方案。
进阶思路：状态压缩动态规划（Bitmask DP）
那有没有更优雅的解法呢？我当时在便利店跟小李说：“别总想着把完整路径当作一个整体去计算。你可以尝试记住‘已经走过了哪些城市’以及‘当前正停在哪个城市门口’，然后一步步向后推导。”
这就是经典的状态压缩动态规划（Bitmask DP）。
核心思想用人话解释一遍：
- 用一个二进制数
mask 来表示“已经走过哪些城市”。例如有4个城市，mask = 0b1011 就表示走过了编号为0、1、3的城市（从右往左数，第0、1、3位是1）。
- 定义一个 DP 状态：
dp[mask][i] 表示“走完 mask 所代表的所有城市，并且最后停在城市 i 的最小花费”。
知道了“之前访问过哪些点”以及“最后停在谁那儿”，那么再向下走到一个新城市 j 的代价，就是“从当前城市 i 走到 j 的路费”加上“之前走到 i 时的最小花费”。
对应的状态转移关系：
- 初始化：只在起点的状态。例如起点是0，则
dp[1 << 0][0] = 0。
- 状态转移：对于每个状态
mask，枚举当前的终点城市 i，再枚举下一个未访问的城市 j (即 j 不在 mask 中)。新状态 new_mask = mask | (1 << j)。转移方程为：dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j])。
- 最终答案：当所有城市都访问完后 (
mask 的二进制位全为1)，需要再加上“从最后一个城市回到起点”的路费，在所有可能的最终城市中取最小值。
完整的 Python 实现代码
下面是一个可以直接运行的 Python 实现，你可以修改输入的距离矩阵来测试自己的场景：
from functools import lru_cache
def tsp_dp(dist, start=0):
"""
dist: 距离矩阵，dist[i][j] 表示从城市 i 到城市 j 的路费（或距离）
start: 起点城市编号，默认为 0
"""
n = len(dist)
ALL = (1 << n) - 1 # 所有城市都已访问的 mask
@lru_cache(maxsize=None)
def dfs(mask, i):
"""
当前已访问的城市集合是 mask，最后停在城市 i，
返回达到这个状态的最小花费。
"""
# 特例：只访问了起点，并且现在就在起点
if mask == (1 << start) and i == start:
return 0
# 对于其他状态，mask 必须包含 i
# 尝试从“之前某个城市 k”转移过来
res = float('inf')
prev_mask = mask & ~(1 << i) # 去掉当前城市 i，得到之前访问的集合
# 起点状态已特判，这里 prev_mask 必须非空
for k in range(n):
if prev_mask & (1 << k): # k 必须在之前访问的集合里
res = min(res, dfs(prev_mask, k) + dist[k][i])
return res
ans = float('inf')
full_mask = ALL
# 枚举最后停在哪个城市，然后再加上回起点的路费
for last in range(n):
if last == start:
continue
cost = dfs(full_mask, last) + dist[last][start]
ans = min(ans, cost)
return ans
if __name__ == "__main__":
# 示例：4 个城市的距离矩阵
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0],
]
print(tsp_dp(dist, start=0))
这段代码利用了 lru_cache 进行记忆化搜索，相当于用递归的方式实现了动态规划。如果你更喜欢用 for 循环的“正统” DP 数组写法，也可以将其改写成二维数组形式，核心逻辑是相同的。
方案评估与实际应用
这个动态规划方案的时间复杂度大约是 O(n² * 2ⁿ)，虽然看起来依然很大，但比起 O(n!) 已经有了天壤之别。在实际工程中：
- 城市数量在15个左右时，用 Python 实现的上述代码还可以应付。
- 城市数量达到20个左右，就需要考虑机器性能和实现细节了。
- 如果城市规模更大，就不要再强求精确的最优解了，应该转向启发式算法，如最近邻算法、局部搜索、模拟退火、遗传算法等。
但在面试或算法讨论中，当别人提到“旅行销售员问题”时，通常希望你能回答出：暴力解法是全排列，优化解法是状态压缩 DP，其复杂度为 O(n² * 2ⁿ)，实现上可以使用位掩码（Bitmask）。
在实际业务中，如果真遇到类似“优化出差路线”的需求，首先要判断城市规模。如果规模很小，直接把上面的 Python 代码拿过去修改适配即可；如果规模很大，目标就应该调整为寻找一个“相对较好的路线”，而非绝对的全局最优解。
好了，关于这个问题的探讨就到这里。我得去催一下我们组小李的接口进度了，他现在追赶的可不是销售员的路线，而是 deadline…
发表于 昨天 14:40
|
查看: 6|
回复: 0
