使用动态规划求解旅行商问题
旅行商问题是 np 问题,在集合表示那里用 set 去实现效率很很低,而且要保存的数都是
不重复的比较小的整数,所以这里用二进制串表示集合。比如集合{1,3,5,6,7}表示成二进制串
用 1110101,其中集合里面有的数对应的位数写成 1,没有的写成 0。要判断第 3 位是不是
1,就把 1110101 右移(3-1)位,得到 11101,然后结果和 00001 进行 & 运算,如果结果是
1 说明第 3 位是 1,否则说明第 3 位是 0。
推广一下,对于数字 x,要看它的第 i 位是不是 1,那么可以通过判断布尔表达式 (((x >>
(i - 1) ) & 1) == 1 的真值来实现。
对于下面这个测试用例,图和邻接矩阵如下,不能走的话用-1 表示,实际存储的时候用一
个比较大的数字,比如 0x7ffff: