algorithm - 在使用 BFS 到达目的地之前访问网格中的选定点

Question

好吧，我正在实现一个问题的解决方案，首先是给你一个 (n,n) 网格。它要求我从 (1,1) 开始，访问网格中标记为 * 的某些点，然后最后进行到 (n,n)。网格的大小保证不超过 15，访问的点数 * 保证 >=0 且 <=n-2。起点和终点始终为空。有一些障碍，#我不能踩的地方。此外，如果我在到达某个 * 之前访问过某个点，我可以在收集 * 后再次通过它。

这是我的解决方案的作用。我制作了一个名为“节点”的数据结构，它有 2 个整数数据类型(x，y)。它基本上是一个元组。

 class Node
    {
        int x,y;
        Node(int x1,int y1)
        {
            x=x1;
            y=y1;
        }
    }

在获取网格时，我维护一个 Set，它存储网格中“*”的坐标。

Set<Node> points=new HashSet<Node>();

我维护了一个网格数组和一个距离数组

char [][]
int distances [][]

现在我要做的是，我将 BFS 应用为 (1,1) 作为源。一旦我遇到任何“*”(我相信这将是最接近的，因为 BFS 为我们提供了未加权图中的最短路径)，我将其从集合中删除。

现在我再次应用 BFS，我的源成为找到的“*”的最后一个坐标。每次，我都会刷新距离数组，因为我的源坐标发生了变化。对于网格阵列，我为上一次迭代刷新标记为“V”(已访问)的路径。

整个过程一直持续到我到达最后一个“*”。顺便说一句，如果我的 BFS 返回 -1，程序会打印“-1”并退出。

现在，如果我以尽可能短的方式成功到达所有“”(我猜？)，我将网格中的 (n,n) 坐标设置为“”并最后应用 BFS时间。这样我就到了最后一点。

现在我的解决方案似乎在某处失败了。哪里出错了？我的概念错了吗？这种“贪婪”的方法会失败吗？获得所有“*”检查点之间的最短路径最终应该让我得到最短路径 IMO。

我环顾四周，发现这个问题类似于旅行商问题，也可以通过动态规划和 DFS 混合或 A* 算法解决。但我不知道如何解决。有人甚至在每个 * 之间说 dijkstra，但据我所知，在未加权的图中，Dijktra 和 BFS 的工作原理相同。我只想知道为什么这个 BFS 解决方案失败

最后，这是我的代码:

import java.io.*;
import java.util.*;

/**
 * Created by Shreyans on 5/2/2015 at 2:29 PM using IntelliJ IDEA (Fast IO Template)
 */

//ADD PUBLIC FOR CF,TC
class Node
{
    int x,y;
    Node(int x1,int y1)
    {
        x=x1;
        y=y1;
    }
}

class N1
{
    //Datastructures and Datatypes used
    static char grid[][];
    static int distances[][];
    static int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,-1,1};
    static Set<Node> points=new HashSet<Node>();
    static int flag=1;

    public static void main(String[] args) throws IOException
    {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();//testcases
        for(int ixx=0;ixx<t;ixx++)
        {
            flag=1;
            r=sc.nextInt();
            if(r==1)
            {
                sc.next();//Taking in '.' basically
                System.out.println("0");//Already there
                continue;
            }
            c=r;//Rows guarenteed to be same as rows. It a nxn grid
            grid=new char[r][c];
            distances=new int[r][c];
            points.clear();
            for(int i=0;i<r;i++)
            {
                char[]x1=sc.next().toCharArray();
                for(int j=0;j<c;j++)
                {
                    grid[i][j]=x1[j];
                    if(x1[j]=='*')
                    {
                        points.add(new Node(i,j));
                    }
                }
            }//built grid
            s1=s2=0;
            distances[s1][s2]=0;//for 0,0
            int ansd=0;
            while(!points.isEmpty())
            {
                for(int i=0;i<r;i++)
                {
                    for (int j = 0; j < c; j++)
                    {
                        distances[i][j]=0;
                        if(grid[i][j]=='V')//Visited
                        {
                            grid[i][j]='.';
                        }
                    }
                }
                distances[s1][s2]=0;
                int dis=BFS();
                if(dis!=-1)
                {
                    ansd += dis;//Adding on (minimum?) distaces
                    //System.out.println("CURR DIS: "+ansd);
                }
                else
                {
                    System.out.println("-1");
                    flag = 0;
                    break;
                }
            }
            if(flag==1)
            {
                for(int i11=0;i11<r;i11++)
                {
                    for(int j1=0;j1<c;j1++)
                    {
                       if(grid[i11][j1]=='V')//These pnts become accesible in the next iteration again
                        {
                            grid[i11][j1]='.';
                        }
                        distances[i11][j1]=0;
                    }
                }
                f1=r-1;f2=c-1;
                grid[f1][f2]='*';
                int x=BFS();
                if(x!=-1)
                {
                    System.out.println((ansd+x));//Final distance
                }
                else
                {
                    System.out.println("-1");//Not possible
                }
            }
        }
    }

    public static int BFS()
    {
        // Printing current grid correctly according to concept

        System.out.println("SOURCE IS:"+(s1+1)+","+(s2+1));
        for(int i2=0;i2<r;i2++)
        {
            for (int j1 = 0; j1 < c; j1++)
            {
                {
                    System.out.print(grid[i2][j1]);
                }
            }
            System.out.println();
        }
        Queue<Node>q=new LinkedList<Node>();
        q.add(new Node(s1,s2));
        while(!q.isEmpty())
        {
            Node p=q.poll();
            for(int i=0;i<4;i++)
            {
                if(((p.x+dx[i]>=0)&&(p.x+dx[i]<r))&&((p.y+dy[i]>=0)&&(p.y+dy[i]<c))&&(grid[p.x+dx[i]][p.y+dy[i]]!='#'))
                {//If point is in range 
                    int cx,cy;
                    cx=p.x+dx[i];
                    cy=p.y+dy[i];
                    distances[cx][cy]=distances[p.x][p.y]+1;//Distances
                    if(grid[cx][cy]=='*')//destination
                    {
                        for(Node rm:points)// finding the node and removing it
                        {
                            if(rm.x==cx&&rm.y==cy)
                            {
                                points.remove(rm);
                                break;
                            }
                        }
                        grid[cx][cy]='.';//It i walkable again
                        s1=cx;s2=cy;//next source set
                        return distances[cx][cy];
                    }
                    else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
                    {
                        grid[cx][cy]='V';//Adding to visited
                        q.add(new Node(cx,cy));
                    }
                }
            }
        }
        return -1;
    }
}

这是我的几个测试用例的代码。给出正确答案:

Java:http://ideone.com/qoE859

C++:http://ideone.com/gsCSSL

这是我的代码失败的地方:http://www.codechef.com/status/N1,bholagabbar

Answer 1

你的想法是错误的。我没有阅读代码，因为即使完美实现，您描述的内容也会失败。

考虑这样的事情:

x....
.....
..***
....*
*...*

你将像这样穿越迷宫:

x....
.....
..123
....4
*...5

然后从 5 到左下角的 * 并返回到 5，走 16 步。然而，这:

x....
.....
..234
....5
1...6

需要 12 步。

问题的正确解决方案涉及蛮力。生成*位置的所有排列，按照排列给定的顺序访问它们，取最小值。

13! 相当大，所以这可能不够快。 O(2^k) 中的动态规划有一个更快的解决方案，类似于 Travelling Salesman Dynamic Programming Solution (还有 here )。

我现在没有时间过多讨论解决方案。如果您对此有任何疑问，请随时提出另一个问题，我相信有人会插话(或让这个问题保持开放状态)。