如何通过递归解决这个问题？

Question

我需要一些帮助来通过递归解决这个问题。

问题：

一个懒惰的游客想要尽可能多地参观一个城市中有趣的地方，而不是走得更远。从他位于城市西北角的旅馆出发，他打算步行到城市的东南角，然后再步行回去。走到东南角时，他只会向东或南走，回到西北角时，他只会向北或西走。在研究了城市地图后，他意识到任务并不那么简单，因为有些区域被封锁了。因此他好心地请你写一个程序来解决他的问题。

给定城市地图（二维网格），其中可步行区域用“.”标记，感兴趣的位置用“*”标记，封闭区域用“#”标记，确定感兴趣位置的最大数量他可以参观。去过两次的地点只算一次。

*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........

答案：7。

我最初的想法是分两部分解决这个问题。

1) 当游客从左上角开始时。

2) 当游客从右下角开始时。

要得到答案，请将它们两个部分相加，这样就可以了。

这是第一部分的方法。

 i and j were initially 0, 0.
 path(int i, int j){

    if(i == H && j == W){
        return (strV[i][j] == '*')?1:0;
    }
    if(i >H || j >W || i<0 || j<0){
        return 0;
    }
    if(visited[i][j] == 1){
        //cout<<"vis";
        return 0;
    }

    if(strV[i][j] == '#' ){
        return 0;
    }

    visited[i][j] =1;
    cout<<i<<" "<<j<<"\n";

    // as i can go only down and right ,for the first part.
    // south and east.
    return max(path(i+1, j), path (i, j+1) ) + (strV[i][j] == '*')?1 :0;

}

同样，我尝试计算第二部分。由于我维护了访问过的数组，因此不可能重新访问同一点。希望应该满足他们在问题中提到的条件。我不确定这是否能解决问题，它给出了错误的答案。

问题link：http://www.spoj.com/problems/TOURIST/

感谢您的宝贵时间。

Answer 1

您的方法有一些缺陷。有些会导致给出错误的解决方案，有些只会导致搜索效率低下。

导致错误解决方案的缺陷是：

在每种方式的最佳路径上添加有趣的位置将不是一个有效的答案，因为您没有将您已经从返回途中的路径中以一种方式访问过的有趣景点打折。（这也意味着你的答案只是单向数字的两倍，因为最好的返回路径将是相同的反向路径）。你实际上需要从你前进的尽头搜索你的路，这样你就可以正确地解释已经访问过的
在值为0的块路径中终止搜索。它需要受到高度惩罚（至少H+V-2）所以只是到达一个块并放弃（没有到达角落）不会被认为是有效路径
回溯时不要取消访问这些位置。这将导致不计算可能以与正在评估的路径不同的路径访问过的有趣位置
终止于访问过的位置。问题陈述中没有任何内容禁止两次穿越同一地点。无论如何，仅考虑一个行进方向时永远不会发生这种情况，因为您只能行进不允许自己返回的两个方向

导致搜索效率低下的缺陷是在搜索最佳路径之前没有简化搜索域。通过创建一个仅包含有趣位置作为节点和它们之间的连接的图形，当它们之间存在有效（非阻塞）路径时，您可以大大减少搜索 space（取决于有趣位置的稀疏程度和丰富程度）这些积木是)

尽可能接近您的尝试，我的建议是：

当访问一个位置时，只需添加一个，这样您就可以在 return 设置最佳路径之前删除一个来取消访问（如果您在搜索 [= =43=] 路径)
当你以一种方式到达路径的尽头时（i == H-1 && j == W-1，因为你从 0,0 而不是 1,1 开始）以另一种方式进行类似的搜索保持访问位置信息
将您感兴趣的位置增加更改为 (visited[i][j] == 0) && (strV[i][j] == '*') 这样您就不会在同一个地方计算两次有趣的位置路径
通过 return 至少 -(H+V-2) 将运行惩罚到一个块中，但是 MIN_INT_VALUE 或介于两者之间的任何东西也可以工作
当你到达一个你已经去过的地方时不要放弃

希望对您有所帮助

Answer 2

这是 JavaScript 中的解决方案。它递归地尝试所有有效方向 SE 和 NW，如果它大于当前最大结果，则保存它的结果。

function solve(grid) {
    var maxVisited = 0;
    var rows = grid.length;
    var cols = grid[0].length;
    // used to make a new copy of the visited set
    function copy(obj) {
      return JSON.parse(JSON.stringify(obj));
    }
    // used to test a current location returning false or the grid value
    function move(r, c) {
      if(r < 0 || c < 0 || r >= rows || c >= cols) { return false; }
      if(grid[r][c] === "#") { return false; }
      return grid[r][c];
    }
    // recursively solve the problem
    function solveRec(r, c, grid, goBack, visited) {
      // end trip, check if visited is greater than current max
      if(goBack === true && r === 0 && c === 0) {
        var count = Object.keys(visited).length;
        if(count > maxVisited) { maxVisited = count; }
        return;
      }
      var m = move(r, c);
      // invalid move
      if(m === false) { return; }
      // place of interest, add to visited set
      if(m === "*") { visited["" + r + ":" + c] = true; }
      // try a move, if at S.E. go back home (turn around)
      if(goBack === true || (r === rows-1 && c === cols-1)) {
        // north west
        solveRec(r-1, c, grid, true, copy(visited));
        solveRec(r, c-1, grid, true, copy(visited));
      } else { 
        // south east
        solveRec(r+1, c, grid, false, copy(visited));
        solveRec(r, c+1, grid, false, copy(visited));
      }
    }
    solveRec(0, 0, grid, false, {});
    return maxVisited;
}

console.log(solve([
  "*........".split(""),
  ".....**#.".split(""),
  "..**...#*".split(""),
  "..####*#.".split(""),
  ".*.#*.*#.".split(""),
  "...#**...".split(""),
  "*........".split("")
])); // 7

编辑这是 jsfiddle http://jsfiddle.net/reeyws86/ 您可能想要添加逻辑以避免极端情况，例如当网格为空或只有 1 个正方形时。

Answer 3

一些观察将帮助您更轻松地解决此问题：

In the return trip the tourist can only move left or up in the grid. This is equivalent to moving right or down in the first trip. So basically there is no difference between the two trips.

Since both trips are basically same we only need to think of first trip. We can send 2 tourists at the same time starting from (0,0) cell. So our state will consist of (x1,y1,x2,y2) where (x1,y1) is position of first tourist and (x2,y2) is position of second tourist in grid.

At each step either tourist can move right or down, so we have 4 choices for movement(2 choice for each tourist).

If both tourists are on the same cell (x1==x2 and y1==y2) then we can add only 1 to result if that cell is special.

This algorithm has time complexity of O(n^4) which won't probably run in time. We can reduce the complexity to O(n^3). If we know the position of first tourist is (x1,y1) the x coordinate of second tourist is x2 then we must have x1+y1=x2+y2 since they both cover same distance in same amount of time. So y2=x1+y1-x2 and our state depends only on (x1,y1,x2).

代码：

const int N 100+5

vector<string> board;

int dp[N][N][N];  // initialize with -1

int calc(int x1, int y1, int  x2) {
    int n=board.size(), m=board[0].size();
    int y2=x1+y1-x2;
    if(x1>=n || x2>=n || y1>=m || y2>=m) return 0;   // out of range
    if(board[x1][y1]=='#' || board[x2][y2]=='#') return 0;  // path blocked so its an invalid move
    if(dp[x1][y1][x2]!=-1) return dp[x1][y1][x2];  // avoid recalculation
    int res=0;
    if(board[x1][y1]=='*') res++;
    if(board[x2][y2]=='*') res++;
    if(board[x1][y1]=='*' && x1==x2 && y1==y2) res=1;  // both tourist on same spot
    int r=calc(x1+1, y1, x2);        // first tourist down second tourist right
    r=max(r, calc(x1+1, y1, x2+1));  // first tourist down second tourist down
    r=max(r, calc(x1, y1+1, x2));    // first tourist right second tourist right
    r=max(r, calc(x1, y1+1, x2+1));  // first tourist right second tourist down
    res+=r;
    dp[x1][y1][x2]=res;  // memoize
    return res;
}

如何通过递归解决这个问题？

How to solve this by recursion?

algorithm

recursion

dynamic-programming