图搜索算法

算法一:深度优先搜索

1.1、图的表示方法

1.1.1、图的表示方法 --- 邻接矩阵

用一个二维数组G存放图,G[i][j]表示节点i和j之间边的情况(如有无边,边方向,权值大小等)
遍历复杂度:O(n^2) n为节点数目

1.1.2、 图的表示方法 --- 邻接表

每个节点V对应一个一维数据(vector),里面存放从V连出去的边,边的信息包括另一顶点,还可能包含边的权值等;


原图

使用邻接表的表示

遍历复杂度:O(n+e) n为节点数目,e为边数目;
在边稀疏的情况下,邻接表的效率比邻接矩阵效率高。

1.2、深度优先搜索思路

从起点出发,走过的点要做标记,发现有没有走过的点,就随意挑一个往前走,走不了就回退,此种路径搜索策略就称为“深度优先搜索”。所谓深度,就是以距离起点的步数来衡量的;按目的可以分为以下3种情况。

1.2.1、判断从V出发是否能走到终点

思路如下:

bool Dfs()
{
      if(v 为终点)
          return true;
      if(v 为旧点)
          return false;
      将v标记为旧点;
      对和v相邻的每个节点u {
          if(Dfs(U) == true)
              return true;
         }
        return false;
}

int main()
{
      将所有点都标记为新点
      设置起点
      设置终点
      cout<<Dfs(起点);
}

1.2.2、判断从V出发是否能走到终点,如果能,要记录路径

Node path[MAX_LEN];   //MAX_LEN取节点总数即可,用来记录路径
int  depth;
bool Dfs()
{
      if(v 为终点) {
          path[depth] = V;
          return true;
     }
      if(v 为旧点) {
          return false;
      }
      将v标记为旧点;
      path[depth] = V;
      depth++;
      对和v相邻的每个节点u {
          if(Dfs(U) == true)
              return true;
         }
        depth--;
        return false;
}

int main()
{
      将所有点都标记为新点
      设置起点
      设置终点
      depth = 0;
      if(Dfs(起点)) {
          for(int i = 0; i <= depth; I++)
                cout << path[i] << endl; 
      }
}

1.2.3、遍历图上所有节点

bool Dfs()
{
      if(v 为旧点)
          return;
      将v标记为旧点;
      对和v相邻的每个节点u {
          Dfs(U);
}
int main()
{
      将所有点都标记为新点
      while(在图中能找到的新点k)
              Dfs(k);
  }

1.3、深度优先搜索例题

/*
    右图是一个城堡的地形图 。请你编写一个程序,计算城堡一共有多少房间, 最大的房间有多大。 城堡被分割成m×n(m≤50,n≤50)个方块,每个方块可以有0~4面墙。
 
 解题思路:
 建模:
 可以将城堡的地形图转化成一个无向图,每个房间是图中的一个节点,相邻两个房间之间如果没有墙,则在房间之间有一条边;
 这样,求房间的个数就转换成了求图中有多少个极大连通子图;
 什么事极大连通子图:对于一个连通子图,往里头加任何一个图里的其他节点,就会变得不连通,那么这个连通子图就是极大连通子图;
 
 对每一个房间,深度优先搜索,从而给这个房间能够到达的所有位置标记。最后统计一共用了几种记号,以及每种记号的数量;
 
 */

int rawNum = 0, colNum = 0;
int rooms[60][60];
int visited[60][60];
int roomNum = 0, maxRoomArea = 0, roomArea = 0;

void Dfs(int i, int j)
{
    if(visited[i][j]) {
        return;
    }
    roomArea++;
    visited[i][j] = roomNum;
    if((rooms[i][j] & 1) == 0) {
        Dfs(i,j-1);
    }
    if((rooms[i][j] & 2) == 0) {
        Dfs(i-1,j);
    }
    if((rooms[i][j] & 4) == 0) {
        Dfs(i,j+1);
    }
    if((rooms[i][j] & 8) == 0) {
        Dfs(i+1,j);
    }
}

int main(int argc, const char * argv[]) {

    cin >> rawNum >> colNum;
    for(int i = 1; i <= rawNum; i++) {
        for(int j = 1; j <= colNum; j++) {
            cin >> rooms[i][j];
        }
    }
    
    memset(visited,0,sizeof(visited));
    for(int i = 1; i <= rawNum; i++) {
        for(int j = 1; j <= colNum; j++) {
            if(!visited[i][j]) {
                roomNum++;
                roomArea = 0;
                Dfs(i,j);
                maxRoomArea = max(roomArea, maxRoomArea);
            }
        }
    }
    cout << roomNum << endl;
    cout << maxRoomArea << endl;
    
    return 0;
}
/*
踩方格
题目描述:有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:
a.每走一步时,只能从当前方格移动一格,走到某个相邻的方格上; b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步(n<=20),共有多少种不同的方案。 2种走法只要有一步不一样,即被认为是不同的方案。


思路:
递归
从(i,j)出发,走n步的方案数,等于一下三项之和:
从(i+1,j)出发,走n-1步的方案数。前提:(i+1,j)还没走过;
从(i,j+1)出发,走n-1步的方案数。前提:(i,j+1)还没走过;
从(i,j-1)出发,走n-1步的方案数。前提:(i,j-1)还没走过;
*/

//int visited[30][50];
int ways(int i, int j, int n)
{
    if(n == 0) {
        return 1;
    }
    visited[i][j] = 1;
    int num = 0;
    if(visited[i][j-1] == 0) {
        num+= ways(i,j-1,n-1);
    }
    if(visited[i][j+1] == 0) {
        num+= ways(i,j+1,n-1);
    }
    if(visited[i+1][j] == 0) {
        num+= ways(i+1,j,n-1);
    }
    visited[i][j] = 0; //这里在尝试完从i, j出发后需要将其恢复为可以访问的状态,这样在尝试从其他点开始的时候,还是可以访问i, j点的。
    return num;
}


int main(int argc, const char * argv[]) {

    int n;
    cin >> n;
    memset(visited,0,sizeof(visited));
    
    cout << ways(0,25,n) << endl;
    return 0;
}
/*
ROADS
N个城市,编号1到N。城市间有R条单向道路。 每条道路连接两个城市,有长度和过路费两个属性。Bob只有K块钱,他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N,输出-1

2<=N<=100
0<=K<=10000
1<=R<=10000 每条路的长度 L, 1 <= L <= 100每条路的过路费T , 0 <= T <= 100
 
 思路:
 从城市1开始遍历整个图,找到所有能到达N的走法,选最优的一个;这里参考深
*/
int K,N,R; //K:bob拥有的钱,N:城市数量,R:路的数量
struct Road {
    int d; //目的城市
    int l; //路的长度
    int t; //过路费
};

int minLen;
int totalCost;
int totalLen;
int visited[110];
vector<vector<Road> > G(100);

void dfs(int s)
{
    if(s == N) {
        minLen = min(minLen, totalLen);
        return;
    }
    for(int i = 0; i < G[s].size(); i++) {
        Road r = G[s][I];
        if(totalCost + r.t > K) {  //可行性剪枝
            continue;
        }
        if(totalLen + r.l > minLen) {  //最优性剪枝
            continue;
        }
        if(!visited[r.d]) {
            totalLen += r.l;
            totalCost += r.t;
            visited[r.d] = 1;
            dfs(r.d);
            totalLen -= r.l;
            totalCost -= r.t;
            visited[r.d] = 0;
        }
    }
}

int main()
{
    cin >> K >> N >> R;
    for(int i = 0; i < R; i++) {
        int n;
        Road r;
        cin >> n >> r.d >> r.l >> r.t;
        if(n != r.d) {
            G[n].push_back(r);
        }
    }
    memset(visited, 0, sizeof(visited));
    totalLen = 0;
    minLen = 1 << 30;
    totalCost = 0;
    visited[1] = 1;
    dfs(1);
    if(minLen < (1 << 30)) {
        cout << minLen << endl;
    }
    else {
        cout << "-1" << endl;
    }
    return 0;
}

算法二:广度优先搜索

1.1、算法思路

广度优先搜索算法如下:(用QUEUE)

(1) 把初始节点S0放入Open表中;
(2) 如果Open表为空,则问题无解,失败 退出;
(3) 把Open表的第一个节点取出放入 Closed表,并记该节点为n;
(4) 考察节点n是否为目标节点。若是,则 得到问题的解,成功退出;
(5) 若节点n不可扩展,则转第(2)步;
(6) 扩展节点n,将其不在Closed表和 Open表中的子节点(判重)放入Open表的尾 部,并为每一个子节点设置指向父节点的指针 (或记录节点的层次),然后转第(2)步。

广度优先算法流程图

2.2、广度优先搜索例题

/*
 八数码问题:
 有一个3*3的棋盘,其中有0-8共9个数字,0表示空格, 其他的数字可以和0交换位置。求由初始状态 到达目标状态的步数最少的解。
 8 2 3       1 2 3
 1 4 6  -->  4 5 6
 5 7 0       7 8 0
 
 广度优先搜索:
 1、用队列保存待扩展的节点
 2、从队列队首取出节点,扩展出的新节点放入队尾,直到队首出现目标节点,即问题的解
 3、关键问题:判重:新扩展出的节点如果和以前扩展出的节点相同,则这个新节点就不必再考虑;
 这里存在的问题是状态节点数据众多,如何存储?以及怎样才能较快的判断一个状态是否是重复?
 
 */

int goalStatus = 123456780; //目标状态
const int MAXS = 400000;
char result[MAXS]; //要输出的移动方案
struct Node {
    int status; //状态
    int father; //父节点指针,即myQueue的下标
    char move; //父节点到本节点的移动方式 u/d/r/l
    Node(int s,int f,char m):status(s), father(f),move(m) { } Node() { }
};
Node myQueue[MAXS]; //状态队列,状态总数362880
int qHead = 0; //队头指针
int qTail = 1; //队尾指针
char moves[] = "udrl"; //四种移动

//求从status经过 move 移动后得到的新状态。若移动不可行则返回-1
int NewStatus( int status, char move)
{
    char tmp[20];
    int zeroPos; //字符'0'的位置
    sprintf(tmp,"%09d",status); //需要保留前导0
    for( int i = 0;i < 9; ++ I )
    {
        if(tmp[i] == '0') {
            zeroPos = I;
            break;
        } //返回空格的位置
    }
    switch(move) {
        case 'u':
            if(zeroPos - 3 < 0 ) {
                return -1; //空格在第一行
            } else {
                tmp[zeroPos] = tmp[zeroPos - 3];
                tmp[zeroPos - 3] = '0';
                
            }
            break;
        case 'd':
            if(zeroPos + 3 > 8 ) {
                return -1; //空格在第三行
            } else {
                tmp[zeroPos] = tmp[zeroPos + 3];
                tmp[zeroPos + 3] = '0';
            }
            break;
        case 'l':
            if(zeroPos % 3 == 0 ) {
                return -1; //空格在第一行
            } else {
                tmp[zeroPos] = tmp[zeroPos - 1];
                tmp[zeroPos - 1] = '0';
            }
            break;
        case 'r':
            if(zeroPos % 3 == 2) {
                return -1; //空格在第三列
            } else {
                tmp[zeroPos] = tmp[zeroPos + 1];
                tmp[zeroPos + 1 ] = '0';
            }
            break;
    }
    return atoi(tmp);
}

//寻找从初始状态status到目标的路径,找不到则返回false
bool Bfs(int status)
{
    int newStatus;
    set<int> expanded;
    myQueue[qHead] = Node(status,-1,0);
    expanded.insert(status);
    while(qHead != qTail) { //队列不为空
        status = myQueue[qHead].status;
        if(status == goalStatus) //找到目标状态
            return true;
        for(int i = 0; i < 4; i ++ ) { //尝试4种移动
            newStatus = NewStatus(status,moves[I]);
            if(newStatus == -1)
                continue; //不可移,试下一种
            if(expanded.find(newStatus)!=expanded.end())
                continue; //已扩展过,试下一种
            expanded.insert(newStatus);
            myQueue[qTail++] = Node(newStatus,qHead,moves[i]); //新节点入队列
        }
        qHead ++;
    }
    return false;
}

int main()
{
    char line1[50];
    char line2[20];
    while( cin.getline(line1, 48)) {
        int i, j;
        for(i = 0, j = 0; line1[i]; i++) {
            if(line1[i] != ' ') {
                if(line1[i] == 'x') {
                    line2[j++] = '0';
                } else {
                    line2[j++] = line1[I];
                }
            }
        }
        line2[j] = 0;
        if(Bfs(atoi(line2))) {
            int moves = 0;
            int pos = qHead;
            do {
                result[moves++] = myQueue[pos].move;
                pos = myQueue[pos].father;
            } while(pos);
            for(int i = moves - 1; i >= 0; i--) {
                cout << result[I];
            }
        } else {
            cout << "unsolvable" << endl;
        }
    }
}

总结

  • 广度搜索一般用于状态表示比较简单、求最优策略的问题
  • 优点:是一种完备策略,即只要问题有解,它就一定可以找到解。并且,广度优先搜索找到的解,还一定是路径最短的解。
  • 缺点:盲目性较大,尤其是当目标点距初始节点较远时,将产生许多无用的节点,因此其搜索效率较低。需要保存所有扩展出的状态,占用的空间大。
  • 用队列存节点: FIFO
  • 深度搜索几乎可以用于任何问题
  • 只需要保存从起始状态到当前状态路径上的节点
  • 用栈存节点:LIFO
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。