栈(Stack)的应用—试探回溯法：八皇后问题、迷宫寻径

迷南。 2022-05-18 08:51 217阅读 0赞

栈的应用

试探回溯法

1.八皇后问题

皇后类

struct Queen { //皇后类
    
        int x, y; //坐标
    
        Queen (int xx = 0, int yy = 0 ) : x(xx), y(yy) {};
    
        bool operator==( Queen const& q ) const { //重载判等操作符，检验不同皇后之间存在的冲突
    
            return (x==q.x) //行冲突
    
                || (y==q.y) //列冲突
    
                || (x+y == q.x+q.y) //对角线冲突
    
                || (x-y == q.x-q.y);
        
        }
    
        bool operator!=( Queen const& q) const { return !(*this == q); } //重载不等操作符
    
    };

将存在冲突的皇后判作相等

每行仅能放置一个皇后，先见各皇后分配至每一行。逐个尝试着她们放置到无冲突的某列，若当前皇后在任何列都冲突，则回溯到上一个皇后。

N皇后算法:

void placeQueen ( int N ) { //N皇后算法:采用试探/回溯的策略,借助栈记录查找结果
    
        Stack<Queen> solu; //存放解的栈
    
        Queen q(0,0); //原点位置开始
    
        do { //反复试探，回溯
    
            if ( N <= solu.size() || N <= q.y ) { //若已出界，则回溯一行，并继续试探下一列
    
                    q = solu.pop(); q.y++;
    
                } else { //试探下一行
    
                    while( ( q.y < N ) && (0 <= solu.find(q) ) ) //通过与已有皇后对比,尝试找到可摆放下一皇后的列
    
                    { q.y++; nCheck++; }
    
                    if ( q.y < N ) { //存在可摆放的列
    
                        solu.push(q); //摆上当前皇后
    
                        if ( N <= solu.size() ) nSolu++; //若部分解已称为全局解，则通过全局变量nSolu计数
    
                        q.x++; q.y==0; //转入下一行，从第0列开始，试探下一皇后
    
                    }
    
                }
    
            } while( ( 0 < q.x ) || ( q.y < N) ); //所有分支均已或穷举或剪枝之后，算法结束
    
    }

实例：

利用以上算法，得到四皇后问题第一个解的完整问题

![70][]

首先试探第一行皇后,如图(a)所示将其暂置于第0列,同时列号入栈。接下来试探再第二行皇后,如图(b)所示在排除前两列后,将其暂置于第2列,同时列号入栈。然而此后试探第三行皇后时,如图(c)所示发现所有列均有冲突。于是回溯到第二行,并如图(d)所示将第二行皇后调整到第3列,同时更新栈顶列号。后续各步原理相同,直至图(l)栈满时得到一个全局解。

2.迷宫寻径问题

迷宫格点类:

typedef enum { AVAILABLE, ROUTE, BACKTRACKED, WALL } Status; //迷宫单元状态
    
    // 原始可用的， 当前路径上的， 所有方向尝试失败后回溯的， 不可使用的
    
    
    typedef enum { UNKNOWN, EAST, SOUTH, WEST, NORTH, NO_WAY } ESWN; //单元的相对邻接方向
    
    
    inline ESWN nextESWN (ESWN eswn) { return ESWN( eswn + 1); } //依次转至下一邻接方向
    
    
    struct Cell { //迷宫格点
    
        int x, y; Status status;
    
        ESWN incoming, outgoing; //进入，走出方向
    
    };
    
    
    #define LABY_MAX 24 //最大迷宫尺寸
    
    Cell laby[LABY_MAX][LABY_MAX]; //迷宫

邻格查询:

inline Cell* neighbor (Cell* cell) { //查询当前位置的相对格点
    
    switch ( cell->outgoing ) {
    
        case EAST : return cell + LABY_MAX ; //向东
    
        case SOUTH: return cell + 1 ; //向南
    
        case WEST : return cell - LABY_MAX ; //向西
    
        case NORTH: return cell - 1 ; //向北
        
        default : exit(-1);
        
        }
    
    }

邻格转入:

inline Cell* advance (Cell* cell) { //从当前位置转入相邻格点
    
    Cell* next;
    
    switch ( cell->outgoing ) {
    
        case EAST : next = cell + LABY_MAX; next->incoming = WEST; break; //向东
    
        case SOUTH: next = cell +1; next->incoming = NORTH; break; //向南
    
        case WEST : next = cell - LABY_MAX; next->incoming = EAST; break; //向西
    
        case NORTH: next = cell -1; next->incoming = SOUTH; break; //向北
        
        default : exit(-1);
    
        }
    
        return next;
    
    }

迷宫寻径算法实现

//在格单元ｓ至ｔ之间规划一条道路
    
    bool labyrinth ( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t) {
    
        if ( (AVAILABLE != s->status ) || (AVAILABLE != t->status ) ) return false; //退化情况
    
    
        Stack<Cell*> path; //用栈记录通路
    
        s->incoming = UNKNOWN; s->status = ROUTE; path.push(s); //起点
    
        do { //从起点出发不断试探回溯，直到抵达终点，或者穷尽可能
    
            Cell* c = path.top();
    
            if ( c == t) return true;
    
            while (NO_WAY > (c->outgoing = nextESWN(c->outgoing) ) ) //逐一检查所有方向
    
                if (AVAILABLE == neighbor(c)->status) break; //找到尚未试探的方向
    
            if (NO_WAY <= c->outgoing ) //若所有方向都已尝试
    
            { c->status = BACKTRACKED; c = path.pop(); } //向后回溯一步
    
            else //否则，向前试探一步
    
            { path.push(c = advance(c) ); c->outgoing = UNKNOWN; c->status = ROUTE; }
    
         }while( !path.empty() );
    
         return false;
    
    }

实例：

![70 1][]

[70]: /images/20220518/6e6ce4fc3a364962938cf3059e5b061f.png
[70 1]: /images/20220518/11972acb520e4db19991d6325bfd02b6.png