对使用状态压缩和动态规划求hamilton最短路径的理解

2024-02-09 17:10:53 #Cpp

hamilton问题

即:

给定一张 n(n≤20) 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
通俗来说就是，图表示大概为这个样子

本文中，代码里的^ 代表xor, 文本中的^ 代表次方

最短路径

本文主要解释通过状态压缩和动态规划优化后的枚举求最短路径算法，本质上还是枚举算法

预设操作二进制的一些小算法

(n>>k)&1 取出n在二进制状态中第k位的值(即把n右移k位，用与1按位与取出右移后数字的第0位也就是原数的第k位)，在本例中即为取是否经过第k个点
n^(1<<k) 给n在二进制状态中的第k位取反，在本例中即代表如果经过那个点之前的情况

状态压缩

本算法中，状态压缩主要体现在用一个int变量代替bool数组来优化时空占用
因为一个bool在C++中占1byte，而一个int变量在C++占4bytes (来源: https://docs.microsoft.com/zh-tw/cpp/cpp/fundamental-types-cpp?view=msvc-160#sizes-of-built-in-types)
所以当bool数组中数量超过4个时使用int类型代替必会节省空间，而本例中最多有20个需要表示的状态(状态指经过该点或没经过，n <= 20), 所以最多int变量需要有20为，也就是2^20(1<<20的值)，为1,048,576，而int最大为2147483647, 所以在本例适用.
所以在代表每个节点的状态的int中，二进制状态的第x位的值即代表是否经过第x点

动态规划

动态规划在本例中就是把寻找最短路径分割成很多个小任务，比如找到起点到第一个节点的的最短距离，然后找到第一个节点到第二个节点的最短距离，再把这两个相加就得出了起点到第二个节点的最短距离，从而推到终点算出起点到终点的最短距离。
所以就需要一个int数字来储存最短距离数据
本例算法中以f为变量名，大小为(2 ^ 20)*20，为什么是2 ^ 20是因为以一个最大为2^20的数表示当前经过了哪些点即有2 ^ 20种行进方法，而有20列是代表在当前状态(前面的数表示的经过状态)下，到每个点的最短距离.
比如: f[12][4] 就代表从起点经过第2第3个点后(12的二进制是1100)到第4个点的最短距离
在下面给出的代码中空出了f[0]中任意内容是因为是没有意义的，起点即为第0位，无论什么情况都要经过起点，也就是表达状态的数字无论什么情况都要大于1

预设

本例中把无穷大(也就是动态规划里每个最短路径的初始值)设置成0x3F及以上(和0x7F一样达到了10^9量级)基本数据在本例中不会达到这种量级，而且无穷大和无穷大相加还是等于无穷大，无穷大和其他数相加也是等于无穷大，并且也不会造成数据溢出。

输入

输入为一个n*n二维数组，第[i, j]项，也就是二维数组中第i行，第j列的数值表示i到j的权重(也可以理解为距离吧)，在下面用weight作为变量名，大概输入长这样：
来源: home.ustc.edu.cn/~xxxujian/homework8.pdf
每个值代表该行到该列的点的权重(在本例中也可以理解成距离)或该列到该行的距离，如果不可以直接到达即为无穷

输出

为int

算法代码

#include <iostream>
#include <memory.h>
using namespace std;

int f[1<<20][20]; //创建一个2^20*20的数组储存最短距离数据
// n为有几个点, weight为带权无向图的权重
int hamilton(int n, int weight[20][20]){
   memset(f, 0x3f, sizeof(f)); // 初始化f每一项为无穷大
   f[1][0] = 0; // 设置最开始的最短距离，即起点(因为第一个下标的1在二进制下第0位是1也就是代表经过第0点即起点的情况下)到起点(第二个下标是0即第0点)的距离为0
   for(int i = 1; i < (1 << n); i ++){
      // 循环每种情况，即从0...1循环到1...1也就是从只经过起点的情况循环到经过全部点
      for(int j = 0; j < n; j++){
         // 循环每个点
         if((i >> j) & 1){
            // 如果在i也就是表达状态的int中的第j位为1，也就是之前经过过j点,即找出可能为这一次经过的点(经过哪个点由外层循环的+1控制),是否为真正经过的点不用管,就枚举每一种路径可能性，是否真正可能由weight决定
            for(int k = 0; k < n; k++){
               // 循环每个点
               if((i^ (1 << j)) >> k & 1){
                  // 如果之前经过过k点，即得出所有可能是上一次经过的点，和前面一样也不用管是否为那个点
                  f[i][j] = min(f[i][j], f[i^(1<<j)][k] + weight[k][j]);
                  // f[i][j]的公式，代表在i情况下，从起点到j点的最短路径，其中[i, j]是唯一的，所以min中的f[i][j]相当于无穷(0x3F)。所以公式相当于就是在当前i情况下，如果不经过j点，起点到k点的最短路径 + j点到k点的最短路径(即权重，如果j无法直接到k即为无穷0x3F)和无穷相比取小的
               }
            }
         }
      }
   }
   // 返回在经过全部点(点是0 ~ n-1)的情况下去n - 1点(终点)的最短路径
   return f[(1 << n) - 1][n - 1];
}

输出路径

在损失一些性能的情况下可以记录并输出路径

#include <iostream>
#include <vector>
using namespace std;

struct Point{
  int weight = 0x3F;
  std::vector<int> path;
};
Point f[1<<20][20]; //创建一个2^20*20的数组储存最短距离数据
// n为有几个点, weight为带权无向图的权重
Point hamilton(int n, int weight[20][20]){
  // memset(f, 0x3f, sizeof(f)); // 初始化f每一项为无穷大
  f[1][0].weight = 0; // 设置最开始的最短距离，即起点(因为第一个下标的1在二进制下第0位是1也就是代表经过第0点即起点的情况下)到起点(第二个下标是0即第0点)的距离为0
  for(int i = 1; i < (1 << n); i ++){
    // 循环每种情况，即从0...1循环到1...1也就是从只经过起点的情况循环到经过全部点
    for(int j = 0; j < n; j++){
      // 循环每个点
      if((i >> j) & 1){
        // 如果在i也就是表达状态的int中的第j位为1，也就是之前经过过j点,即找出可能为这一次经过的点(经过哪个点由外层循环的+1控制),是否为真正经过的点不用管,就枚举每一种路径可能性，是否真正可能由weight决定
        for(int k = 0; k < n; k++){
          // 循环每个点
          if((i^ (1 << j)) >> k & 1){
            // 如果之前经过过k点，即得出所有可能是上一次经过的点，和前面一样也不用管是否为那个点
            if(f[i][j].weight > f[i^(1<<j)][k].weight + weight[k][j]){
              f[i][j].weight = f[i^(1<<j)][k].weight + weight[k][j];
              f[i][j].path = f[i^(1<<j)][k].path;
              f[i][j].path.push_back(j);
            }
            // f[i][j]的公式，代表在i情况下，从起点到j点的最短路径，其中[i, j]是唯一的，所以min中的f[i][j]相当于无穷(0x3F)。所以公式相当于就是在当前i情况下，如果不经过j点，起点到k点的最短路径 + j点到k点的最短路径(即权重，如果j无法直接到k即为无穷0x3F)和无穷相比取小的
          }
        }
      }
    }
  }
  // 返回在经过全部点(点是0 ~ n-1)的情况下去n - 1点(终点)的最短路径
  return f[(1 << n) - 1][n - 1];
}


int main(){
  int input[20][20]{
      {0x3f, 4, 3, 0x3f, 5, 0x3f, 0x3f, 0x3f},
      {4, 0x3f, 5, 5, 9, 0x3f, 0x3f, 0x3f},
      {3, 5, 0x3f, 5, 0x3f, 0x3f, 0x3f, 5},
      {0x3f, 5, 5, 0x3f, 7, 6, 5, 4},
      {0x3f, 9, 0x3f, 7, 3, 0x3f, 0x3f, 0x3f},
      {0x3f, 0x3f, 0x3f, 6, 3, 0x3f, 2, 0x3f},
      {0x3f, 0x3f, 0x3f, 5, 0x3f, 2, 0x3f, 6},
      {0x3f, 0x3f, 5, 4, 0x3f, 0x3f, 6, 0x3f},
  };
  auto p = hamilton(8, input);
  cout << p.weight <<endl;
  for(auto a : p.path)
    cout<<a<<"->";
}

文中图片来自于http://home.ustc.edu.cn/~xxxujian/homework8.pdf
代码来自于 算法竞赛进阶指南 / 李煜东

-END-

2024-02-09 17:10:53 #Cpp