在这篇文章中，我们将利用我们对动态规划和位屏蔽技术的知识来解决一个著名的NP难问题“旅行推销员问题”。 在解决问题之前，我们假设读者了解
为了理解这个概念，我们考虑下面的问题： 问题描述 :
Given a 2D grid of characters representing a town where '*' represents the houses, '#' represents the blockage, '.' represents the vacant street area. Currently you are (0, 0) position.Our task is to determine the minimum distance to be moved to visit all the houses and returnto our initial position at (0, 0). You can only move to adjacent cells that share exactly1 edge with the current cell.
上述问题就是著名的旅行推销员问题。 第一部分是计算两个单元之间的最小距离。我们可以简单地使用BFS，因为所有的距离都是单位距离。为了优化我们的解决方案，我们将预先计算距离，将初始位置和房屋位置作为BFS的源点。 每次BFS遍历都需要O（网格大小）时间。因此，它是 O（X*网格的大小） 对于整体预计算，其中X=房屋数量+1（初始位置） 现在让我们考虑一个DP状态 因此，我们需要跟踪到访房屋和最后一次到访房屋，以唯一地确定该问题的状态。 因此，我们将采取 dp[索引][掩码] 作为我们的国家。
在这里 指数 ：告诉我们现在房子的位置 面具 ：告诉我们到访的房屋（如果在mask中设置了第i位，则这意味着第i个脏瓷砖已被清理）
而dp[index][mask]将告诉我们访问X（mask中的设置位数）房屋的最小距离，该距离对应于它们在mask中出现的顺序，其中最后访问的房屋是位置索引处的房屋。 状态转移关系 所以我们的初始状态是 dp[0][0] 这表明我们目前处于初始瓦片位置，这是我们的初始位置，掩码为0，表示到目前为止没有访问过任何房屋。 我们的最终目的地将是 dp[任何指数][限制] 这是你的面具= （1）<
dp(curr_idx)(curr_mask) = min{ for idx : off_bits_in_curr_mask dp(idx)(cur_mask.set_bit(idx)) + dist[curr_idx][idx]}
上述关系可视为站在curr_idx house和已经访问cur_mask house时访问所有房屋的最小距离等于curr_idx house和idx house之间的最小距离+站在idx house和已经访问所有房屋的最小距离 拜访( cur|u mask |（1） )房子。 所以，这里我们迭代所有可能的idx值，这样cur_mask就有了i th 位为0，这告诉我们 th 这栋房子没人参观。 每当我们有了面具，这意味着我们已经参观了镇上所有的房子。因此，我们将把上次访问的城镇（即cur_idx位置的城镇）与初始位置（0,0）的距离相加。 以上实现的C++程序如下：
C++
#include <bits/stdc++.h> using namespace std; #define INF 99999999 #define MAXR 12 #define MAXC 12 #define MAXMASK 2048 #define MAXHOUSE 12 // stores distance taking source // as every dirty tile int dist[MAXR][MAXC][MAXHOUSE]; // memoization for dp states int dp[MAXHOUSE][MAXMASK]; // stores coordinates for // dirty tiles vector < pair < int , int > > dirty; // Directions int X[] = {-1, 0, 0, 1}; int Y[] = {0, 1, -1, 0}; char arr[21][21]; // len : number of dirty tiles + 1 // limit : 2 ^ len -1 // r, c : number of rows and columns int len, limit, r, c; // Returns true if current position // is safe to visit // else returns false // Time Complexity : O(1) bool safe( int x, int y) { if (x >= r or y>= c or x<0 or y<0) return false ; if (arr[x][y] == '#' ) return false ; return true ; } // runs BFS traversal at tile idx // calculates distance to every cell // in the grid // Time Complexity : O(r*c) void getDist( int idx){ // visited array to track visited cells bool vis[21][21]; memset (vis, false , sizeof (vis)); // getting current position int cx = dirty[idx].first; int cy = dirty[idx].second; // initializing queue for bfs queue < pair < int , int > > pq; pq.push({cx, cy}); // initializing the dist to max // because some cells cannot be visited // by taking source cell as idx for ( int i = 0;i<= r;i++) for ( int j = 0;j<= c;j++) dist[i][j][idx] = INF; // base conditions vis[cx][cy] = true ; dist[cx][cy][idx] = 0; while (! pq.empty()) { auto x = pq.front(); pq.pop(); for ( int i = 0;i<4;i++) { cx = x.first + X[i]; cy = x.second + Y[i]; if (safe(cx, cy)) { if (vis[cx][cy]) continue ; vis[cx][cy] = true ; dist[cx][cy][idx] = dist[x.first][x.second][idx] + 1; pq.push({cx, cy}); } } } } // Dynamic Programming state transition recursion // with memoization. Time Complexity: O(n*n*2 ^ n) int solve( int idx, int mask) { // goal state if (mask == limit) return dist[0][0][idx]; // if already visited state if (dp[idx][mask] != -1) return dp[idx][mask]; int ret = INT_MAX; // state transition relation for ( int i = 0;i<len;i++) { if ((mask & (1<<i)) == 0) { int newMask = mask | (1<<i); ret = min( ret, solve(i, newMask) + dist[dirty[i].first][dirty[i].second][idx]); } } // adding memoization and returning return dp[idx][mask] = ret; } void init() { // initializing containers memset (dp, -1, sizeof (dp)); dirty.clear(); // populating dirty tile positions for ( int i = 0;i<r;i++) for ( int j = 0;j<c;j++) { if (arr[i][j] == '*' ) dirty.push_back({i, j}); } // inserting ronot's location at the // beginning of the dirty tile dirty.insert(dirty.begin(), {0, 0}); len = dirty.size(); // calculating LIMIT_MASK limit = (1<<len) - 1; // precalculating distances from all // dirty tiles to each cell in the grid for ( int i = 0;i<len;i++) getDist(i); } int main( int argc, char const *argv[]) { // Test case #1: // .....*. // ...#... // .*.#.*. // ....... char A[4][7] = { { '.' , '.' , '.' , '.' , '.' , '*' , '.' }, { '.' , '.' , '.' , '#' , '.' , '.' , '.' }, { '.' , '*' , '.' , '#' , '.' , '*' , '.' }, { '.' , '.' , '.' , '.' , '.' , '.' , '.' } }; r = 4; c = 7; cout << "The given grid : " << endl; for ( int i = 0;i<r;i++) { for ( int j = 0;j<c;j++) { cout << A[i][j] << " " ; arr[i][j] = A[i][j]; } cout << endl; } // - initialization // - precalculations init(); int ans = solve(0, 1); cout << "Minimum distance for the given grid : " ; cout << ans << endl; // Test Case #2 // ...#... // ...#.*. // ...#... // .*.#.*. // ...#... char Arr[5][7] = { { '.' , '.' , '.' , '#' , '.' , '.' , '.' }, { '.' , '.' , '.' , '#' , '.' , '*' , '.' }, { '.' , '.' , '.' , '#' , '.' , '.' , '.' }, { '.' , '*' , '.' , '#' , '.' , '*' , '.' }, { '.' , '.' , '.' , '#' , '.' , '.' , '.' } }; r = 5; c = 7; cout << "The given grid : " << endl; for ( int i = 0;i<r;i++) { for ( int j = 0;j<c;j++) { cout << Arr[i][j] << " " ; arr[i][j] = Arr[i][j]; } cout << endl; } // - initialization // - precalculations init(); ans = solve(0, 1); cout << "Minimum distance for the given grid : " ; if (ans >= INF) cout << "not possible" << endl; else cout << ans << endl; return 0; } |
输出：
The given grid : . . . . . * . . . . # . . . . * . # . * . . . . . . . . Minimum distance for the given grid : 16The given grid : . . . # . . . . . . # . * . . . . # . . . . * . # . * . . . . # . . . Minimum distance for the given grid : not possible
笔记 : 我们用初始状态来表示 dp[0][1] 因为我们把起始位置推到了房屋容器的第一个位置。因此，我们的位掩码将是1作为0 th bit已设置，即我们已经访问了旅行的出发地点。 时间复杂性 : 考虑房屋的数量 N .所以，有 n*（2） N ) 在每个州，我们都在n个房屋上循环，然后转移到下一个州，由于记忆化，我们在每个州只做一次循环转移。因此，我们的时间复杂性是 O（n） 2. * 2 N ) . 推荐 :
本文由 尼蒂什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
