网站建设制作设计公司佛山,中科建建设发展有限公司网站,购物网站服务器硬件配置,线上推广方式目录 前言一、栈的应用#xff08;迷宫问题#xff09;1.1 问题描述1.2 算法选择1.3 算法精化1.4 算法实现1.5 问题结果 二、队列的应用#xff08;农夫过河问题#xff09;2.1 问题描述2.2 算法选择2.3 算法精化2.4 算法实现2.5 问题结果 总结 前言
本篇文章使用两个例子… 目录 前言一、栈的应用迷宫问题1.1 问题描述1.2 算法选择1.3 算法精化1.4 算法实现1.5 问题结果 二、队列的应用农夫过河问题2.1 问题描述2.2 算法选择2.3 算法精化2.4 算法实现2.5 问题结果 总结 前言
本篇文章使用两个例子说明栈和队列的应用 对于迷宫问题使用栈实现深度优先策略解决迷宫问题 对于农夫过河问题使用队列实现广度优先策略解决农夫过河问题。
一、栈的应用迷宫问题
1.1 问题描述
从入口进入迷宫如何可以尽快找到迷宫的出口这是一个十分有趣的经典游戏。 迷宫可用如图1.1所示的方块表示其中每个元素或为通道以空白方块表示或为墙以带阴影的方块表示。迷宫问题要求的是从入口到出口的一个以空白方块构成的无环路径。
图1.1 迷宫的图形表示 1.2 算法选择
求解迷宫问题的简单方法是从入口出发沿某一方向进行探索若能走通则继续往前走否则沿原路返回换一方向再进行探索直到找到了一个出口或者所有可能的探索都以失败而告终。这类探索方法统称为回溯法也可以称为深度优先探索方法。实现深度优先探索的工具是栈。 其算法的基本框架如下
mazeFrame(void)
{创建一个保存探索过程空栈把入口位置压入栈中while(栈不为空){取栈顶位置并设置为当前位置while(当前位置存在试探的可能性){取下一试探位置if(下一位置是出口)打印栈中保存的探索过程然后返回if(下一位置是通道)把下一位置进栈并且设置为当前位置}}
}1.3 算法精化
在求解程序中迷宫可用二维数组maze[m][n]表示其中数组中元素是0表示通道1表示墙。 入口坐标为(1,1) 出口坐标为(6,9)
图1.2 迷宫的二维数组表示 为了细化前面的框架还要考虑试探方向的表示 假设某时刻所在迷宫的位置坐标为(i,j)相邻的四个位置分别标E、S、W、N表示东、南、西、北方向 为了简化算法可以建立一个数组direction这个数组给出了相对于位置(i,j)的4个方向上,i和j的增量值 使用一个变量elem_d表示试探方向 0-表示方向E 1-表示方向S 2-表示方向W 3-表示方向N 则某个方向的试探位置i和j的变化值为
new_i i direction[elem_d][0] 新的行坐标
new_j j direction[elem_d][1] 新的列坐标例如,当位置坐标为(3,4)时
elem_d 0 表示试探方向为E
则试探坐标为
new_i i direction[0][0] 3 0 3
new_j j direction[0][1] 4 1 5
则新坐标为(3,5)图1.3 迷宫中方向的表示 另外为了避免走到已经试探过的位置包括现在探索路径上的和曾经在探索路径上的位置凡是已经探索过的位置都应该做上标记。根据约定值为1表示墙0表示通道那么凡是探索过的位置可以赋予一个既非0又非1的值假设取值为2这样做可以节省空间缺点是破坏了maze数组的状态否则要设置一个与迷宫那样大小的数组来保存标记。一旦将某一位置(i,j)纳入到当前路径中就将maze[i][j]设置为2。为了记录探索路径中当前位置以及在该位置上的试探方向算法设置了一个栈栈中元素包括三项分别记录当前位置的行坐标、列坐标和以及在该位置上的试探方向。
//栈数据元素类型
struct ElemType {int x; //行坐标int y; //列坐标int direction; //试探方向
};1.4 算法实现
经过上述设计求迷宫中一条路径上的算法可以从入口开始对每个当前位置都从E方向(elem_d 0)开始试探若不能通过则顺时针依次试探S方向、W方向和N方向。当选定一个可以前进的位置要把当前所在的位置纳入探索路径中并将当前所在位置以及试探方向记录下来以便走不通时可以顺序原路一步步回退每退一步以后接着试探在该位置上的其他未试探过的方向如此循环直到找到出口。
/*
int(*maze)[11] 数组指针类型表示传入迷宫数组
int(*direction)[2] 数组指针类型表示传入direction数组
int entrance_x 入口行坐标
int entrance_y 入口列坐标
int eixt_x 出口行坐标
int exit_y 出口纵坐标
*/
void mazePath(int (*maze)[11], int(*direction)[2], int entrance_x, int entrance_y, int exit_x, int exit_y)
{int elem_x 0;int elem_y 0;int elem_d 0;int newDirection_x 0;int newDirection_y 0;//初始化栈SeqStack stack { 0 };initSeqStack(stack);//初始化入口坐标元素SElemType element { 0 };maze[entrance_x][entrance_y] 2; //从入口开始标记element.x entrance_x; element.y entrance_y;element.direction -1; //未试探任何方向if (!pushSeqStack(stack, element)) //将入口点进栈{destroySeqStack(stack);return;}while (!isEmptySeqStack(stack)) //走不通时一步步回退{if (!popSeqStack(stack, element)) //获取栈顶元素并出栈{destroySeqStack(stack);return;}elem_x element.x;elem_y element.y;elem_d element.direction1;while (elem_d 3) //一次试探一个方向{newDirection_x elem_x direction[elem_d][0];newDirection_y elem_y direction[elem_d][1];if (newDirection_x exit_x newDirection_y exit_y maze[newDirection_x][newDirection_y] 0)//走到出口{element.x elem_x;element.y elem_y;element.direction elem_d;if (!pushSeqStack(stack, element)){destroySeqStack(stack);return;}element.x newDirection_x;element.y newDirection_y;element.direction 4;if (!pushSeqStack(stack, element)){destroySeqStack(stack);return;}printf(The revers path is:\n); //打印路径while (!isEmptySeqStack(stack)){if (!popSeqStack(stack, element)){destroySeqStack(stack);return;}printf(The node is: (%d %d)\n, element.x, element.y);}//销毁栈destroySeqStack(stack);return;}if (maze[newDirection_x][newDirection_y] 0) //走到没走过的点{maze[newDirection_x][newDirection_y] 2; //标记走过的点element.x elem_x;element.y elem_y;element.direction elem_d;if (!pushSeqStack(stack, element)) //进栈{destroySeqStack(stack);return;}elem_x newDirection_x; //下一点转换成当前点elem_y newDirection_y;elem_d -1;}elem_d;}}printf(The path has not been found!\n);//销毁栈destroySeqStack(stack);
}注意 顺序栈的代码已经省略
1.5 问题结果
二、队列的应用农夫过河问题
2.1 问题描述
一个农夫带着一只狼、一只羊和一颗白菜身处河的南岸。农夫要把这些东西全部运到河的北岸。问题是农夫只有一条小船船小到只能容下农夫和一件物品当然船只有农夫能撑。另外因为狼能吃羊而羊能吃白菜所以农夫不能留下羊和狼或者羊和白菜单独在河一边自己离开。好在狼属于食肉动物它不吃白菜。请问农夫该采取什么方案才能将所有的东西安全运过河呢
2.2 算法选择
求解这个问题的最简单的方法是逐步进行试探。每一步都在前一步选择基础上搜素下一步的所有可能的状态。用计算机实现上述系统搜索过程可以采用两种不同的策略一种是广度优先搜索breadth first另一种是深度优先搜索(depth first)。实现广度优先搜索的工具是队列实现深度优先搜索的工具是栈。本节讨论队列的应用所以重点介绍广度优先搜索策略。 广度优先搜索的思想就是在搜索过程中总是首先搜索下面一步的所有可能情况然后再进一步考虑更后面的各种情况。要实现广度优先搜索一般都采用队列作为辅助结构把每一步所有可能达到的状态都列举出来放在这个队列中然后顺序取出来分别进行处理在处理中又再把下一步的情况全部放在队列里。由于队列的操作原则是先进先出所以只有在前一步的所有情况都处理完后才能开始后面一步各情况的处理。 以遍历二叉树为例使用广度优先搜索策略进行层序遍历。
图2.1 广度优先遍历二叉树 2.3 算法精化
要模拟农夫过河问题首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的方法是用4位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或某物品在河的南岸1表示在河的北岸。因此整数5其二进制表示为0101表示农夫和白菜在河的南岸而狼和羊在北岸。这时农夫不在因此狼会把羊吃掉所以是一种不安全的状态。问题的初始状态是整数0其二进制为0000而问题的终结状态是整数15其二进制表示为1111。
图2.2 二进制位置表示图 用整数location表示用上述方法描述的状态可以用下面的4个函数从上述状态得到每个角色所在位置的代码。函数返回值为真1表示农夫或物品的位置在河的北岸否则在南岸。
//农夫过河问题
//个体判断函数
/* 四位二进制数分别表示农夫狼白菜羊的位置0 表示在南岸 1 表示在北岸初始状态 location 0000二进制 表示农夫狼白菜羊都位于河的南岸使用按位 操作取出每个位置的信息例如 location 0x08 取出农夫的位置信息
*///取出农夫位置信息
int farmer(int location)
{return (0 ! (location 0x08));
}//取出狼位置信息
int wolf(int location)
{return (0 ! (location 0x04));
}//取出白菜位置信息
int cabbage(int location)
{return (0 ! (location 0x02));
}//取出羊位置信息
int goat(int location)
{return (0 ! (location 0x01));
}此外还应该分析问题中的所有角色构成的状态确定其中那些状态是安全的哪些是不安全的。因为单独留下白菜和羊或单独留下狼和羊在某一岸是不安全的所以安全状态的判断可以使用下面的函数实现。
//安全状态的判断函数
/*不能单独留下狼和羊例如 location 0101 是一种不安全的状态不能单独留下白菜和羊例如 location 1100 是一种不安全的转态安全返回 1不安全返回 0
*/int safe(int location)
{//判断羊和白菜是否单独if ((goat(location) cabbage(location)) (farmer(location) ! goat(location))){return 0;}//判断狼和羊是否单独if ((wolf(location) goat(location)) (farmer(location) ! goat(location))){return 0;}return 1; //其他状态安全
}2.4 算法实现
完成了上面的准备工作后现在的问题变成从初始状态二进制0000出发寻找一种全部由安全状态构成的、能够实现的状态变迁序列序列中的每状态都可以从前一状态通过农夫带东西划船过河到达到达最终状态二进制1111.为避免不必要的重复在序列中不应该出现重复的状态。 根据广度优先搜索的思想算法中需要使用一个整数队列moveTo把搜索过程中每一步所有可能到达的状态都保存起来。队列中的每个元素表示可以安全到达的中间状态。 另外使用一个整数数组rooute记录已被访问过的各个状态以及已被发现的能够到达这些状态的前驱状态。由于在这个问题中需要列举的所有状态二进制0000~1111一共16种所以route数组只需要使用16个元素。route的每个元素初始化为-1每当在队列中加入一个新的状态时就把route中以该状态作下标的元素的值改为达到这个状态的前一转态的下标值。所以数组的第i个元素不仅记录了状态i是否已经被访问过同时对于以及被访问过的状态还保存了这个状态的前驱状态下标。算法结束后可以利用route数组元素的值生成一个正确的路径。
图2.3 route数组 代码实现如下
//农夫问题求解/*从初始状态二进制0000出发寻找一种全部由安全状态构成、能够实现的状态变迁序列序列中的每个状态都可以从前一状态通过农夫带东西划船过河到达到达最终的状态1111。为避免不必要的重复在序列中不应该出现重复的状态整数队列moveTo把搜索过程中每一步所有可能到达的状态都保存起来。队列中的每个元素表示可以安全到达的中间状态整数数组route用于记录已被访问过的各个状态以及已被发现的能够到达这些状态的前驱状态由于在这个问题中需要列举的状态二进制0000~1111一共16种则数组长度大小为16每个数组的元素值初始化为-1每当在队列中加入一个新的状态时就把route中以该状态做下标的元素的值改为达到这个状态的下标值数组的第i个元素不仅记录状态i是否已被访问过同时对于已被访问过的状态还保存了这个状态的前驱状态算法结束后可以利用route数组元素的值生成一个正确的状态路径
*/void farmerProblem()
{int movers, location, newlocation;int route[16]; //用于记录已考虑的状态路径struct SeqQueue moveTo; //用于记录可以安全到达的中间状态initSeqQueue(moveTo); //初始化队列enSeqQueue(moveTo, 0x00); //初始状态二进制0000入队for (int i 0; i 16; i)//初始化数组route{route[i] -1;}route[0] 0;while (!isEmptySeqQueue(moveTo) (route[15] -1)){getQElemSeqQueue(moveTo, location); //取出队头状态为当前状态QElemType e;deSeqQueue(moveTo, e);//循环值依次表示羊、白菜、狼、农夫的移动情况//movers的值用二进制表示依次为0001(羊)、0010(白菜)、0100(狼)、1000(农夫)for (movers 1; movers 8; movers 1){if ((0 ! (location 0x08)) (0 ! (location movers))) //农夫与移动的物品在同一岸{// 0x08 | movers 得到的结果表明农夫或物品应该在船上物品无法单独过河// location ^ (0x08 | movers) 把坐船过河的农夫与物品的状态翻转newlocation location ^ (0x08 | movers); //计算新状态if (safe(newlocation) route[newlocation] -1) //新状态安全且未处理{route[newlocation] location; //记录旧状态且作为新状态的前驱enSeqQueue(moveTo, newlocation); //将新状态入队}}}}if (route[15] ! -1){printf(The reverse path is :\n);for (location 15; location 0; location route[location]){printf(The location is : %d\n, location);if (location 0){exit(0);}}}else{printf(No solution\n);}
}注意这里实现队列的代码已省略感兴趣可查看文章https://blog.csdn.net/pyc68/article/details/145093486?spm1001.2014.3001.5501
算法开始时把初始状态为0表明人和物都在南岸放入队列中。while循环时只要队列不为空便取出队头元素for循环用于列举所有可以移动的角色包括农夫本身用movers表示for循环的增量表达式里使用了左移位操作循环值依次为1、2、4、8分别表示羊、白菜、狼和农夫的移动情况。由于在每一次移动时农夫都必须改变状态所以只有农夫与被移动的东西在同一岸时农夫才可以将其带走。当然农夫可以什么都不带单独过河。将变量movers与二进制0x08进行按位异或运算所得结果为1表明相应的农夫或物品应该在船上再将原有状态与这个结果进行一次按位异或运算得到移动后的一个新状态。最后检验新状态是否安全是否未被处理过。如果成立就确认这个状态转换可行把这个状态放入队列中并且修改route数组的值
2.5 问题结果
图2.4标出了送入队列的各个状态位置和广度优先搜索的顺序编号。 通过图2.4得出一条从0000到达1111的路径 0000-1001农夫把羊从南岸带到北岸 1001-0001农夫独自从北岸回到南岸 0001-1011农夫把白菜从南岸带到北岸 1011-0010农夫把羊从北岸带回南岸 0010-1110农夫把狼从南岸带到北岸 1110-0110农夫独自从北岸回到南岸 0110-1111农夫把羊从南岸带到北岸
图2.4 广度优先搜索的结果和顺序图 总结
迷宫问题完整代码: https://gitee.com/PYSpring/data-structure/tree/master/maze_code 农夫过河问题完整代码https://gitee.com/PYSpring/data-structure/tree/master/queue_code
