第五章状态空间各种搜索.ppt

第五章状态空间的各种搜索 习题课 by 刘曦 广度优先搜索框架（仅供参考版） // 表示状态结点的结构 Struct Node { // problem-specific data fields // 例如迷宫问题里，记录所在位置 // 又如模板问题里，记录当前布局 int curr_cost; // 当前的耗费（步长） }; 广度优先搜索框架（仅供参考版） // open表，先进先出队列 Node open[MAX_NODES]; // 队列的头尾指针 int head; // 头指针总指着队列头元素的位置 int tail; // 尾指针总指着队列尾的下一个位置 广度优先搜索框架（仅供参考版） // 初始化/清空队列 void initialize() { head = 0; tail = 0; } 广度优先搜索框架（仅供参考版） // 检查队列是否为空 bool is_empty() { return head tail; } 广度优先搜索框架（仅供参考版） // 入队 void push(Node node) { open[tail++] = node; } 广度优先搜索框架（仅供参考版） // 出队 void pop() { ++head; } 广度优先搜索框架（仅供参考版） // 查看队头元素 Node front() { return open[head]; } 广度优先搜索框架（仅供参考版） initialize(); while (!is_empty()) { Node curr_node = front(); pop(); if (is_solution(curr_node)) { // do sth, maybe break directly. } /* for each operation: new_node = operation(curr_node); generally, new_node.curr_cost = curr_node.curr_cost + 1 if (!visited(new_node)) { push(new_node); } */ } 广度优先搜索框架（仅供参考版） // 检查某个结点是否已访问过 bool visited() { // Hash-table could be used here // it will be problem-specific } 广度优先搜索框架（仅供参考版） 哈希表其实不像它的名字那样难搞 简单的： 最短步数遍历迷宫时，开一个和迷宫一样大小的标记数组。 复杂的： 魔板里面用到的“康托展开”，把1～8的一个排列映射到一个[1, 8!]整数上。 广度优先搜索框架（仅供参考版） STL里面的queue // using std::queue; // queueNode open; // open.push(); // open. pop(); // open.front(); // open.empty(); // 没有clear函数。。。DIY pls… // while (!open.empty()) open.pop(); 深度优先搜索框架（仅供参考版） void dfs(int depth /*, params */) { if (/*满足终止条件*/) { do_sth_with(depth, params); return; } for each operation: dfs(depth + 1, operation(params)); } 第五章课后习题 1317 1050 1215 1150 1151 1152 1153 1317. Sudoku 数独历史 from wikipedia 相传数独源起于拉丁方阵（Latin Square），1970年代在美国发展，改名为数字拼图（Number Place）、之后流传至日本并发扬光大，以数学智力游戏智力拼图游戏发表。在1984年一本游戏杂志《パズル通信ニコリ》正式把它命名为数独，意思是“在每一格只有一个数字”。后来一位前任香港高等法院的新西兰籍法官高乐德（Wayne Gould）在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的《泰晤士报》上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程式，并将它放在网站上，使这个游戏很快在全世界流行。 香港是在2003年7月30日由《AM730》引入数独。 后来更因数独的流行衍生了许多类似的数学智力拼图游戏，例如：数和、杀手数独。 数