2010年第01期，第43卷 通 信 技 术 Vol.43，No.01,2010 总第217期Communications Technology No.217,Totally
基于递归搜索的公交换乘算法研究
罗 晟
（中国地质大学 信息工程学院，湖北 武汉 430071）
【摘 要】在城市的公共交通网络中，公交换乘是乘客出行的一个重要的问题。随着城市公交规模的不断扩大，有相当部分的出行难以直达，乘客必须换乘才可到达目的地。在研究公交换乘的最优路径算法时，有必要先了解乘客出行时所考虑的因素，通过对乘客出行心理、行为的研究来确定模型的优化目标和约束条件。文中从换乘算法、出行时间、出行距离等方面进行分析，在综合考虑相关因素的情况下，加权平均得出了一种最小换乘次数为主的广度优先算法，并应用于武汉号码百事通系统中。
【关键词】地理信息系统；公交换乘；数据模型
【中图分类号】TP311.13 【文献标识码】B【文章编号】1002-0802(2010)01-0159-03 Studies on Buses Exchange Algorithm Based on Recursive Search
LUO Sheng
（Information Engineering College, China University of Geosciences, Wuhan Hubei 430071, China）
【Abstract】In urban traffic network, the transit exchange is the principal issue for passengers. With the on-going expansion of urban traffic scale, it is hard, to some extent, to get to the planned destination directly. However, the passengers have to exchange some buses and reach their destinations. In search of the better alternatives, it is necessary to know the related factors of the passengers and thus to determine the optimized goal and restrictions through the study of their psychology, behaviors. The paper makes its analysis on three parts: exchange algorithm, jouney time, travel distance. With all related factors and through weighing the average of minimum bases exchange, a broad optimization algorithm is obtained.
【Key words】geographic information system；buses exchange；data model
0 引言
通信行业作为数字城市重要基础之一，担负着通信网络基础设施资源的管理重任，对其它行业提供庞杂的通信服务支撑。通过对通信资源数据库的各种操作，就可以实现对通信网络的操作指导和资源调度指派。因此，由通信GIS和交通GIS及其数据融合产生的号码百事通系统就是一个很好的空间信息服务的实例。
公交系统是城市生活中不可缺少的一个重要组成部分,社会公众、政府部门对公共交通的服务质量提出了信息化、智能化、实时化、现场化的要求[1]。人们讨论有关交通线路问题时，一般着重解决任意两个站点之间的最短路径问题，很少考虑该路径的换乘代价，而公交换乘的过程将直接影响到出行时间的长短。因此，一个高效的换乘方案会使出行变得非常便捷[2]。
基于城市交通现代化的基本原则与思路, 通过分析与收集武汉市城区的所有公交车号和公交车路线, 用户可以随意选择自己的目的地, 算法就会给出相应的乘车方式，科学布局公交运行路线, 使居民公交出行的换乘次数控制在平均1次内, 最大限度利用公交资源。
1 基于最短路径和基于站点优先级的换乘技术
目前普遍的换乘算法主要基于最短路径和基于站点优先级两种。其中基于最短路径的换乘技术要求先计算从源地点到目的地点的最短路径，然后根据这条最短路径和经过这条路径的公交站点，为乘客提供换乘方案求最短路径一般使用Dijkstra 算法[3]，该算法可求出任一源点到其它所有网络结点的最短路径。该算法的优点是在计算点对间的最短路径时
收稿日期：2009-03-12。
作者简介：罗 晟（1982-），男，博士研究生，主要研究方向为分布式
地理信息系统，WebGis，网格GIS以及GIS的应用研究。
159
160 效率非常高，特别是对于近距离点之间的最短路径计算。在实际应用中，需要计算的网络规模通常都较大，在网络结点数呈线性递增时，计算时间将以级数递增。以武汉市城区为例，公交站点和道路的交点共同构成结点数就达2000多个，计算速度会慢得难以忍受。
基于站点优先级的换乘技术就是通过使用特殊的数据结构，根据公交站点的车流、人流等设置其换乘优先级，计
算换乘方案时优先选择这些站点进行换乘[4]
。该技术避免了
一些基于最短路径人性化程度较低的方面，但在换乘效率及出行时间方面仍有其弊端。例如让乘客先乘车到总站，再从总站乘车到目的地，这种情况用户显然无法接受。
2 基于递归搜索的公交换乘算法
2.1 算法概述
查找从出发地到目的地的公交换乘方案，首先搜索n 次换乘方案（n 为零表示直达），如果搜索不到n 次换乘方案，则继续搜索n +1次换乘方案；如果找到n 次换乘方案，就不再搜索n +1次换乘方案。当n >0时，程序采用递归算法搜索方案。当然搜索出的n 次换乘方案很可能不止一条，在这种情况下我们按代价从小到大排序，目前公交换乘有按换乘最少优先,按价格最低优先和按步行最短优先选择换乘方案三种。选择代价最小的前十种方案给用户。这里的代价＝步行的距离＋乘车经过的总的车站数×50米。（即将乘车经过一站路等价为步行50米） 2.2 数据结构
该算法需要在数据库中建立一种存储所有公交线路实
图1 公交线路数据结构示意
（1）公交站点（TeDev）
包括城市公交网络中所有的公交站点，可以通过点模型来描述其空间位置，并将其站点名称等信息记录在属性数 据中。
（2）公交线路（TeGjxl）
各公交线路具有唯一编号，并且可将公交线路名称、起点、终点、开班、收班时间等信息记录在属性数据中。 （3）公交段（TeCirc）
公交段是公交线路中相邻两公交站点之间的实际路径。 （4）线路与站点关联(TeGjxlcz)
记录公交线路经过站点的信息，并且按顺序记录各站点，以此记录线路与站点的关联信息。
（5）站点与线路关联(TeGjczxl)
记录站点所经过的线路信息，记录站点与线路的关联。 2.3 算法逻辑步骤
在客户端输入起点和终点的名称，名称可以是公交车站的名称，也可以是公共设施名称。点击查询，系统判断输入的合法性然后传送相关的数据与指令给服务器。当服务器接收到客户端的请求，调用函数分步骤处理数据：① 系统查询出起始、终止点的车站；② 查询经过此两个站点的车次信息；③ 判断是否能够直达到目的地，如果不能，则查询是否有某两路相交的线路能够贯穿起始地和目的地，也即进行第一次换乘，依次类推，直到找到方案；④ 服务器将执
行结果传回客户端，客户端进行相应的显示。如图2所示。
图2 公交换乘流程
步骤：
① 建立数据缓存，查找数据中对应的公交车站与线路的全部对应信息放到内存中；
② 查找起点附近M 米范围内的所有公交车站, 取距离最近的十个车站；
③ 查找经过起点附近十个车站的所有线路；
④ 查找终点附近M 米范围内的所有公交车站,取距离最近的十个车站；
⑤ 查找经过终点附近的十个车站的所有线路； ⑥ 把所有经过终点附近的十个车站的所有线路标识为可以到达的线路；
⑦ 查找经过起点附近十个车站的所有线路,如果有线路标识为可以到达,则找到换乘方案；
⑧ 如果不能到达,则把经过终点附近十个车站的所有线
161
路的所有车站的线路标识为可以到达；
⑨ 重复步骤⑦,如果仍然没有找到换乘方案,则重复步骤⑧,直到找到换乘方案为止。如图3所示。
图3 算法逻辑流程
2.4 算法评估
本算法在基于递归的思想上，综合考虑相关因素，在无法一次或较少次到达目的地的情况下，选取距离起始点和终点最近的10个站点作为暂时替代，然后通过计算步行距离比较，得出较为优化的换乘方案，既避免了使用最短路径技术造成的多次换乘，也避免了使用站点优先级技术中的效率低下和忽略时间因素的缺陷。
3 算法应用
本文提出的换乘算法在“武汉号码百事通系统”项目中得到了成功应用。该算法的实现结合了GIS 中的电子地图来表示空间信息。在系统公交换乘查询面板中，用户确定好起止站点后，可以选择按照“最少换乘”、“最小费用”、“最少步行”点击查询按钮，系统就会列出两个站点之间的10个
优先换乘方案；双击其中的某个换乘方案，系统就会在地图上高亮度闪烁地显示乘车路线以及经过的公交站点。
4 结语
基于递归搜索的换乘算法是传统的换乘算法的优化和改良，它解决了公交换乘计算中存在的存储和计算效率问题。在武汉号码百事通系统中的测试表明，任意两个站点间的换乘方案计算时间小于0.3 秒（主频2.2 G，内存1 G）。该算法能够很好地满足实际应用的需求。
另外，通信行业作为较早与GIS技术结合的准IT行业，其GIS应用技术相对较为成熟。而面向大众的空间信息服务往往涉及到大众日常生活如衣食住行的各个层面，所需信息量巨大，它们多与通信网络相关。随着社会经济的发展，交通拥挤、线路阻塞和交通事故频繁发生正越来越严重的困扰
着世界上的各大城市[5]
，如果能够通过一定的方式和手段将
通信网络与交通的数据进行有效融合，建立一个横向多专业，纵向多层次的信息共享模式，无疑将彻底改变当前各行业领域专业系统所形成的无数个“信息孤岛”的尴尬处境。
参考文献
[1] 龙安国. 基于GPS/GPRS 的智能公交系统的设计与实现[J]. 通信
技术，2009,42(01):326-329.
[2] 徐兵，谢仕义.基于站点优先级的公交换乘算法实现[J]. 计算机时
代，2005(07):16-17.
[3] 严寒冰，刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算
机学报,2000,23(02)：210-215.
[4] 王钦，王炜，李铁柱.城市公交换乘枢纽规划方法[J].交通运输系统
工程与信息,2004,4(03):82-85.
[5] 梁松， 梁艳， 陈继努. 基于 GPRS 的智能公交系统通信平台的实
现[J].通信技术,2007,40(10):56-58.
（上接第158页）
报:信息与管理工程版，2008，30(01):14-17.
[7] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-
Efficient Communication Protocol for Wireless Microsensor Networks[C]. Hawaii:[s.n.], 2000:3005-3014.
[8] Heinzelman W. Application-specific Protocol Architectures for
Wireless Networks [D].Boston: Massachusetts Institute of Technology, 2000.
[9] Younis O, Fahmy S. HEED: A Hybrid, Energy-efficient,
Distributed Clustering Approach for Ad hoc Sensor Networks[J]. IEEE Transaction on Mobile Computing,2004,3(04): 366-379. [10] Manjeshwar A, Agrawal D. TEEN: A Routing Protocol for Enhanced
Efficiency in Wireless Sensor Networks[C]. USA:[s.n.], 2001:2009-2015.
[11] Lindsey S, Raghavendra C. PEGASIS: Power-Efficient Gathering
in Sensor Information Systems[C].USA:[s.n.],2002:1-6. [12] 刘昌鑫. 无线传感器网络路由协议比较研究[J].微计算机信
息,2006(25): 205-207.
[13] Ibriq J, Mahgoub I. Cluster-Based Routing in Wireless Sensor
Networks: Issues and Chanllenges[C]. California: SPECTS’04, 2004:759-766.
[14] 雷阳,尚凤军,任宇森.无线传感网络路由协议现状研究[J].通信技
术,2009,42(03):117-120.
[15] Chong C Y,Kumar S P. Sensor Networks: Evolution，Opportunities
and Challenges[J]. Proceedings of the IEEE，2003, 91(08): 1247-1256.
[16] 刘希若,袁康敏,李院民.无线传感器网络新型MAC 协议研究[J].通
信技术,2008, 41(08):160-165.
公交车路线查询系统后台数据库设计--查询算法 1. 公交车路线信息在数据库中的存储方式 显然，如果在数据库中简单的使用表bus_route(路线名,路线经过的站点,费用)来保存公交车路线的线路信息，则很难使用查询语句实现乘车线路查询，因此，应该对线路的信息进行处理后再保存到数据库中，笔者使用的方法是用站点-路线关系表stop_route(站点,路线名,站点在路线中的位置)来存储公交车路线,例如，如果有以下3条路线 R1: S1->S2->S3->S4->S5 R2: S6->S7->S2->S8 R3: S8->S9->S10 则对应的站点-路线关系表stop_route为
注：Stop为站点名，Route为路线名，Position为站点在路线中的位置 2.直达乘车路线查询算法 基于表stop_route可以很方便实现直达乘车路线的查询，以下是用于查询直达乘车路线的存储过程InquiryT0： create proc InquiryT0(@StartStop varchar(32),@EndStop varchar(32)) as begin select sr1.Stop as 启始站点, sr2.Stop as 目的站点, sr1.Route as 乘坐线路, sr2.Position-sr1.Position as 经过的站点数 from stop_route sr1, stop_route sr2 where sr1.Route=sr2.Route and sr1.Position 递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) { 随机直接搜索优化算法NLJ 辨识算法 NLJ 优化算法是随机直接搜索优化算法的一种，它是由随机数直接搜索算法算法发展而来，可以有效地解决各种复杂的问题。因其结构简单以及收敛迅速使其在随机搜索算法中始终占有一席之地。这种算法的核心思想是利用收缩变量来缩小搜索域，找到次优解，然后再基于次优解重复上述过程直到最终获得最优解。 假设待辨识的系统模型为： 1110 1 ()(0,1,...,)n n n H s i n a s a s a s a -= =++ ++ （3.1） 其中，01,,...,n a a a 表示待辨识模型的系数值。 该算法主要有以下步骤： Step 1、初始化参数。根据辨识数据，通过手工调整模型参数大致拟合出一个初始模型，确定模型初始参数(0)k i a ，其次，确定参数搜索范围c 。()k i a j 表示参数i a 在第k 次迭代的搜索结果，0,1,...,k p =，j 表示迭代组数，0,1,...,j m =。参数的搜索范围可由设定参数初始值的倍数决定，具体规则如下： 0l i i r ca = ，当 时，1k k k i i i r ca v -=?。 （3.2） 其中，根据经验知识，c 取值为2。 Step 2、计算性能指标。选择如式（3.3）所示的输出误差指标，作为辨识性能指标式，将待辨识的参数带入系统模型，求解估计值()y t 。 0[()()]N t J y t y t ==-∑ （3.3） 其中，()y t 为t 时刻的实际数据。 Step 3、计算参数估计值。在第k 代计算参数估计参数k l a ，其中rand 是在 [0.5,0.5]-之间分布的随机数，k i a 由下式给出： 1()()k k k l i i a j a j rand r -=+? （3.4） 在第k 次迭代计算后，计算m 组性能指标，选择使得性能指标最小的参数值作为下一次迭代的初始值： 11min[(())](0)|k i k k i i J a j a a --= （3.5） Step 4、修改搜索范围。在第k 次搜索前需要根据下式（3.6）对搜索范围进行修正防止局限的搜索范围导致搜索陷入局部极值。 （3.6） 在此处引入变化率η，首先，计算判断每组参数幅值的变化率，并选择变化 3k >1k k k i i i r cr v -= 深度优先与广度优先 （一）深度优先搜索的特点是：（1）从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2- 7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法 （二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。（2）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当搜索深度较大时，如例题2- 5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。（3）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点 的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。（4）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。（5）从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 二、广度优先搜索法的显著特点是：（1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。（2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。（3）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一 多机器人路径规划研究方法 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multi robot.Then discussed the criterion of path planning research for multi robot based large of literature.Meanwhile,it expounded the bottleneck of the path planning research for multi robot，forecasted the future development of multi robot path planning. Key words:multi robot；path planning;reinforcement learning;evaluating criteria 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multi agent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、Dempster Shafer 证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划 n！非递归算法的设计与实现 1 课题描述 尽管递归算法是一种自然且合乎逻辑的解决问题的方式，但递归算法的执行效率通常比较差。因此在求解许多问题时常采用递归算法来分析问题，用非递归方法来求解问题；另外一些程序不支持递归算法来求解问题，所以我们都会用非递归算法来求解问题。 本次课程设计主要内容是：用非递归算法实现n!的计算，由于计算机中数据的存储范围有限，而又要求出尽可能大的n的阶乘的值，用数组构造n的运算结果的存储结构,用栈的存储方式，最后输出n!的运算结果。 本次课程设计的目的是：通过本次课程设计，可以使大家了解缓存中数据的存储范围，提高自学能力，增强团队合作意识。 2 需求分析 本次n!非递归算法的课程设计中主要用到的知识有：数组、函数、栈，选择条件中的结构语句（if…else），和循环结构语句中的语句while()语句、do…while()语句和for()语句，选择语句if的运用。 对n!的非递归的算法，主要是运用非递归的算法实现n的阶乘。 限制条件： (1).要求的n必须是整数； (2). n的范围； (3). 数据类型和表数范围。 递归和非递归算法是相通的，递归是一种直接或间接调用自身的算法，而非递归不调用自身函数递推采用的是递归和归并法，而非递推只采用递归法。递推法一般容易溢出，所以一般都采用递推法分析，而用非递推法设计程序。 将n定义为float型，便于查看n是否为整数； 本次试验分为两个模块： (1).当n小于都等于12时，实现阶乘的模块m(n): 直接用sum*=i;实现求n的阶乘，相对简单，容易就算。 (2).当n大于12时，如果用long型结果就会溢出，所以实现阶乘需调用的模块f(n): 采用数组存放计算的结果，用队列输出运行结果。由于计算结果较大，将结果除以数组最大存储位数，将高位结果存放在数组的起始地址上，将低位的结果存放在数组的末端地址上，最后采用队列输出运行结果。 (3).模块调用关系如图3.1所示 图3.1 模块调用图 深度优先搜索和广度优先搜索的比较 （一）深度优先搜索的特点是： （1）从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2-7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。 但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法（二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。 （2）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当搜索深度较大时，如例题2-5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。 （3）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。 （4）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。 （5）从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。 如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 二、广度优先搜索法的显著特点是： （1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。 （2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。 （3）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度（或广度）优先搜索算法：找到一个目标后，不是立即退出，而是记录下目标结点的路径和费用，如果有多个目标结点，就加以比较，留下较优的结点。把所有可能的路径都搜索完后，才输出记录的最优路径。 （4）广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。 最佳优先模式--搜索引擎算法分析 搜索时大部分用户只关注排在最前面的搜索结果。尽管视系统，用户，任务和界面的不同，具体的搜索结果数量也不同，但可以肯定的是前三个搜索结果将吸引你80%的主意力。搜索结果第一页的其他链接也会得到部分关注，但其后的内容则不然。 有两个原因决定了这很重要。首先，搜索的最简单用例就是：浏览有用的搜索结果。用户输入关键词，扫视前面几个搜索结果，点击链接，搜索就完成了。要让搜索简单，快速，有用，最佳优化搜索模式非常重要。其次，最前面的几个搜索结果对于查询重构有着极大的影响。用户输入搜索字词，浏览最初的几个结果，然后再试试搜索其他的内容。大约20%~50%的搜索都包括查询重构。前三个搜索结果是用户界面的重要组成部分。 因此，选择搜索引擎时，应该首先考虑最佳优先模式。高质量，透明，灵活的结果排序算法是成功的关键。他们自始至终都应该是优秀而出色的，能够根据特定内容集而变或是随着应用的独特需求而变。其算法应该包括： 相关性 包括主题的相关性，目的在于将搜索关键字和内容文本元数据匹配起来。有效算法包括词汇排序，相似性，位置，频度和文档长度等。短标题里的精确词汇匹配比起长篇内容里的AND共现匹配要有价值得多。在一个网页上反复出现，但在网站上其他地方却难寻踪迹的词语其权重也更高。相关性算法必须处理好文本查询的特殊情况，包括复数和其他单词变体，比如诗人和诗歌。只有做出调整才能在查准率和查全率之间取得合适的平衡。相关性是典型的搜索引擎默认设置，而且事实上往往也是一种混合模式，把多种算法整合到一个平衡的解决方案中。 流行性 在大多数情境中，社会化数据能够极大地改善语义算法。谷歌的PageRank算法把链接视为投票，这是一个大获成功的做法。如今流行性已经成为典型的多算法度量。在Flickr 上，照片的兴趣度有浏览数，评论数，注释数和收藏次数等决定。在亚马逊网站上，用户按照最畅销或最佳评论来排序。不过，及时用户按照相关性来排序时，社会化数据也影响着搜索结果的显示排序。 日期 默认日期排序并不好，但这一选项也自有用处。尤其是对于新闻和邮件应用来说，按照反向时间顺序（即最新的内容优先显示）相对更加常见。在许多情况下，出版日期或是修改日期可以为通用相关性算法提供有价值的数据，从而改善首选搜索结果的实时性。 格式 在单一形式中，格式和内容类型就像过滤器一样有用，用户可以选择只查看特定格式的内容，比如图片，视频或新闻。而且，他们还可以帮助改善最佳搜索结果。比如，在企业内 三个表（最简单化，不考虑模糊查询，单行线等其他东西）： 1，站点表stop(stop_id,stop_name) 2，路线表line(line_id,line_name) 3，路线站点表(点线路关系表)linestops( line_id, stop_id, seq )此处的seq指某站点在某线路中的顺序。 现在分析算法： 1，直达线路 首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2 然后查询 select line_id from (select line_id from linestops where stop_id = id1) A, (select line_id from linestops where stop_id = id2) B where A.line_id = B.line_id 即得到可直达的线路列表 2,一次换乘 首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2 然后搜寻两个站点通过直达方式各自能够到达的站点集合，最后他们的交集就是我们所需要的换乘站点。 select stop_id from ( select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id1) )A, ( select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id2) )B where A.stop_id= B.stop_id 得到换乘站（可能有多个或0个）后，剩下的就是显示能够到达换乘站的两边线路，这通过前面的直达查询即可。 3，二次换乘 首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2 算法的中心思想是：站点1能够通过直达到达的所有站点集合A，站点2能够通过直达到达的所有站点集合B，A和B之间有直达的线路。 一步一步来： 站点1能够通过直达到达的所有站点集合A： select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id1) 站点2能够通过直达到达的所有站点集合B： select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id2) 而直达的查询是 select line_id from 可定制的路线规划 第一部分：对《Customizable Route Planningshortestpath》进行总结分析： 过去的十年里，在道路网络上找到最短路径的方法已经有很多了。实际算法主要包括：预处理需要几分钟，然后产生线性的数据用于实时查询。然而现实世界对交通路线的规划提出了更高的要求，需要支持其他的自然量度，例如最短距离，步行，骑行等。 可定制的路线规划能够在支持这种个性化的出行方式，类似于我们日常生活中的百度地图，高德地图一样，我们可以实时选择最为合适的出行方式。这种系统能够支持流量的更新和动态场景的改变。为了制定这样的系统，需要一种快速查询的算法，这种算法还需有一定的稳健性。 为了实现这种目标，我们区分了道路的两个特征，运用拓扑的方法描述道路的物理特性，比如物理长度，转弯类型，速度限制等；道路的度量指标来表示实际的道路情况，在算法中运用在函数里。这里假设道路的物理特性是很少发生变化的，而实际的指标经常发生变化。 为了实现这种分离，有三个阶段，第一个阶段将独立的指标预处理相对较慢，仅作为拓扑方法的输入指标，第二个阶段，指标的定制必须很快，第三个阶段查询使用的是前两个阶段的输出，并且实时的查询要很快。在点到点的算法属性中，该论文主要阐述了三类方法：CH,SHARC,这类的层次结构度量，PCD,ALT基于目标方向的技术和基于图形分离的技术，在对比后选择了基于图形分离技术。 本文作者的思路是先建立一个基本的算法，然后再考虑几个技术的结合使它更实用。 基本算法：以分离器为基础的算法 其他技术：稀疏化：边缘收缩，并做出了一个轻量级的收缩计划 目标方向化：PCD技术，但是是在定制和查询期间使用 ALT技术，ALT预处理运行Dijkstra算法 多层次的叠加图表 流水线操作：快于基于邻接集的操作，有效取决于度量，使用了MLD伴 随原始2级CALT操作 以上的所有内容都是在考虑道路网络的简化，但是没有考虑到转弯的成本，作者进一步处理了转向问题，最后对路径解压完成了可定制化的路线规划。 第二部分：对于我们项目的启发： 我们需要建立一个合适的数学模型来实时模拟可定制的路径规划问题，对实时的数据进行清洗和处理。路径规划的数学模型在现代的科学技术中已经比较成熟了，我们只需要选取合适的模型来解决问题就行了。在下一阶段中我们将建立基本的算法和采集数据。通过查 1.怎样成为搜索高手——选择适当的查询词 搜索技巧，最基本同时也是最有效的，就是选择合适的查询词。选择查询词是一种经验积累，在一定程度上也有章可循： A.表述准确百度会严格按照您提交的查询词去搜索，因此，查询词表 述准确是获得良好搜索结果的必要前提。 一类常见的表述不准确情况是，脑袋里想着一回事，搜索框里输入 的是另一回事。 例如，要查找2004年国内十大新闻，查询词可以是“2004年国内十 大新闻”；但如果把查询词换成“2004年国内十大事件”，搜索结果就 没有能满足需求的了。 另一类典型的表述不准确，是查询词中包含错别字。 例如，要查找林心如的写真图片，用“林心如写真”，当然是没什么 问题；但如果写错了字，变成“林心茹写真”，搜索结果质量就差得 远了。 不过好在，百度对于用户常见的错别字输入，有纠错提示。您若输 入“林心茹写真”，在搜索结果上方，会提示“您要找的是不是: 林心 如写真”。 B.查询词的主题关联与简练目前的搜索引擎并不能很好的处理自然 语言。因此，在提交搜索请求时，您最好把自己的想法，提炼成简单的，而且与希望找到的信息内容主题关联的查询词。 还是用实际例子说明。某三年级小学生，想查一些关于时间的名人名言，他的查询词是“小学三年级关于时间的名人名言”。 这个查询词很完整的体现了搜索者的搜索意图，但效果并不好。 绝大多数名人名言，并不规定是针对几年级的，因此，“小学三年级” 事实上和主题无关，会使得搜索引擎丢掉大量不含“小学三年级”，但非常有价值的信息；“关于”也是一个与名人名言本身没有关系的词，多一个这样的词，又会减少很多有价值信息；“时间的名人名言”，其中的“的”也不是一个必要的词，会对搜索结果产生干扰；“名人名言”，名言通常就是名人留下来的，在名言前加上名人，是一种不必要的重复。 因此，最好的查询词，应该是“时间名言”。 试着找出下述查询词的问题，并想出更好的能满足搜索需求的查询词： 所得税会计处理问题探讨 周星驰个人档案和所拍的电影 几大搜索引擎排名算法趣味解析 做优化最关心的是什么，当然是在几大搜索引擎的排名，几年的淘汰，现在的格局是百度一家独大，然后带领360和新搜狗二个小弟，谷歌中国只剩下不到3%的市场，基本上可以忽略不计，但是谷歌毕竟在全球还是搜索老大，粉丝效应还有一些的用户。 百度：个人觉得百度在排名算法是最人性的，虽然说这个话可能引来好多人的吐槽，因为好多人深受百度其害，认为百度是是难伺候的，算法层出不穷，而且经常所谓的大姨妈，很是伤了好多人的心，但是从我感觉来看，从来没有感受过百度所谓的K站，优化手法也是一直采用正规的白帽手法，几年来优化过的一些站也是得到了自己心仪的排名，为什么说百度最人性呢，最近上了一个新站，到现在差不多刚好一个月的时间，虽然关健词的指数都不高，不过几个关健词已经齐齐的奔入了百度前三页，而且还在稳步的上升中，为什么能这样呢，就是因为百度的新站效应这个人性化的举措，好些优化人士也说，只要你网站按照百度要求搭建，然后内容建设也符合百度规律，那么你网站上线收录不久后百度就会给部份关健词相应的排名，大家都知道优化是一个相当枯燥的事情，能坚持是一件相当困难的事情了，给了甜头，当然有干下去的动力，只要你持续，那后来一定会收到一个比较理想的排名的，但是也有好些人一直所谓的抱怨这，抱怨那，一直没有得到自己想要的排名，这个呢估计得自己找原因了， 360：上线以来，给了人们好大的期望，但是我感觉期望的这部份人应该大部份是来自百度受害者，欺许能在这里得到心灵的安慰，也就出现了一些研究360排名的人，但是至今网上也没有关于这方面的文章，个人感觉360应该没有什么核心算法，搜索结果跟百度也是惊人的雷同，新站基本上不可能在360出现排名，一些老站排名和百度差不多，为什么新站不给排名呢，估计是在等百度排名稳定后再抄袭，这个也就是最近百度频繁推出新算法的的原因，推出新算法一方面是为了提高体验，一方面是打造技术门槛防止被抄袭。 谷歌：在说谷歌之前先上一幅图，这个是这几天在A5上面看到的一篇文章 现在不知道还有多少人是这样的，经常聊天的时候也听到类似的一些观点，认为谷歌怎么怎么的好，谷歌虽然是全球巨头，但是谷歌中文我感觉来是最差的，排版布局上面首先就让人看得难受，我也不知道好多人所说的谷歌好是指的是谷歌中文，还是谷歌英文了，也不知道他们到底是谷歌的用户，还是谷歌的粉丝，还是因为就像以前流行的那样，搜索用谷歌，聊天用MSN等这样的，谷歌中文排名也是我感觉最简单的，那就是一句话外链至上，就是如果你有足够的外链， 习题 3 1、答：深度优先搜索算法的特点是 ①一般不能保证找到最优解； ②当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制； ③方法与问题无关，具有通用性； ④属于图搜索方法。 宽度优先搜索算法的特点是 ①当问题有解时，一定能找到解； ②当问题为单位耗散值，并且问题有解时，一定能找到最优解； ③效率低； ④方法与问题无关，具有通用性； ⑤属于图搜索方法。 2、答：在决定生成子状态的最优次序时，应该采用深度进行衡量，使深度大的 结点优先扩展。 3、答：（1）深度优先 （2）深度优先 （3）宽度优先 （4）宽度优先 （5）宽度优先 4、答：如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那 么给以后放皇后留下的余地就大，找到解的可能性也大；反之留下的余地就小，找到解的可能性也小。 并不是任何启发函数对搜索都是有用的。 6、讨论一个启发函数h在搜索期间可以得到改善的几种方法。 7、答：最短路径为ACEBDA，其耗散值为15。 8、解：（1）（S，O，S0，G） S：3个黑色板和3个白色板在7个空格中的任何一种布局都是一个状态。 O：①一块板移入相邻的空格； ②一块板相隔1块其他的板跳入空格； ③一块板相隔2块其他的板跳入空格。 S0： B B B W W W G： W W W B B B W W W B B B W W W B B B W W W B B B W W W B B B W W W B B B W W W B B B （2）1401231231234567333377 =???????????=?P P P （3）定义启发函数h 为每一白色板左边的黑色板数的和。 显然，)()(n h n h *≤，所以该算法具有可采纳性。 又，?? ?≤-=),()()(0)(j i i j n n c n h n h t h ，所以该启发函数h 满足单调限制条件。 9、解： ((( ),( )),( ),(( ),( ))) ((S,( )),( ),(( ),( ))) ((A,( )),( ),(( ),( ))) ((A,S),( ),(( ),( ))) ((A,A),( ),(( ),( ))) ((A),( ),(( ),( ))) (S,( ),(( ),( ))) (A,( ),(( ),( ))) (A,S,(( ),( ))) (A,A,(( ),( ))) (A,(( ),( ))) 汉诺塔递归与非递归算法研究 作者1，作者2，作者33 (陕西师范大学计算机科学学院，陕西西安 710062) 摘要: 摘要内容(包括目的、方法、结果和结论四要素) 摘要又称概要,内容提要.摘要是以提供文献内容梗概为目的,不加评论和补充解释,简明,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法,结果和结论.具体地讲就是研究工作的主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立性和自明性,并且拥有与文献同等量的主要信息,即不阅读全文,就能获得必要的信息. 关键词:关键词1; 关键词2；关键词3；……（一般可选3~8个关键词，用中文表示，不用英文 Title 如：XIN Ming-ming , XIN Ming (1.Dept. of ****, University, City Province Zip C ode, China；2.Dept. of ****, University, City Province Zip C ode, China；3.Dept. of ****, University, City Province Zip C ode, China) Abstract: abstract（第三人称叙述，尽量使用简单句；介绍作者工作（目的、方法、结果）用过去时，简述作者结论用一般现在时） Key words: keyword1;keyword2; keyword3;……（与中文关键词对应，字母小写(缩略词除外)）； 正文部分用小5号宋体字，分两栏排，其中图表宽度不超过8cm.。设置为A4页面 1 引言（一级标题四号黑体加粗） 这个问题当时老和尚和众僧们，经过计算后，预言当所有的盘子都从基柱A移到基座B上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。其实，不管这个传说的可信度有多大，如果考虑把64个盘子，由一个塔柱上移到另一根塔柱上，并且始终保持上小下大的顺序。假设有n个盘子，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都早已经灰飞烟灭。 对传统的汉诺塔问题，目前还有不少的学者继续研究它的非递归解法，本文通过对递归算法的研究……. 提示：（1）可以定义问题的规模n,如盘子的数量；（2）塔柱的数量（目前有部分理论可以支撑，不妨用计算机实现）分析规模的变化与算法的复杂度比较。（3）可以对经典的汉诺塔问题条件放松、加宽，如在经典的汉诺塔问题中大盘只能在小盘下面，放松其他条件可以定义相邻两个盘子必须满足大盘只能在小盘下面。其它盘子不作要求。 2 算法设计 2.1 汉诺塔递归算法描述（二级标题小五黑体加粗） 用人类的大脑直接去解3，4或5个盘子的汉诺塔问题还可以，但是随着盘子个数的增多，问题的规模变的越来越大。这样的问题就难以完成，更不用说吧问题抽象成循环的机器操作。所以类似的问题可用递归算法来求解。下面n个盘的汉 百度搜索技巧的四个方法 大家都知道搜索方法正确后可以大大提高搜索效率，会使大家的工作既省心又省力！网上针对百度搜索技巧的方法也很多，但是我在这里做一个总结，总结出十大百度搜索技巧！这十大百度搜索技巧可以帮助大家更迅速准确的找到相应信息，详情如下： 1、十大百度搜索技巧之（一）—-“-” 百度支持减除不相关的资料的“-”功能，可以用于删除某些无关页面，注意建号前面必须要有空格 例如：“A-B”意思就是说想在搜索A的同时屏蔽关于B的信息 2、十大百度搜索技巧之（二）—-“|“ 百度支持并行搜索功能来搜索例如：“A|B”意思是想要搜索包含A的信息或者包含B的信息比方说你要查询seo和侯瑞男时，可以用”seo|侯瑞男“来搜索，无需分两次查询，百度就会提供跟“|”前后任何相关关键词相关的网站和资料 3、十大百度搜索技巧（三）—-intitle intitle的作用是把搜索范围限定在网页标题中，网页标题往往就是本篇内容的简要概括，将查询内容界定在网页标题中会起到很好的效果。 使用方法：把查询内容中，特别关键的部分用”intitle:“做前缀 例如：想要查找标题中带有Yadid’s World的如何优化长尾关键词的内容，您就可以如下： 可以用[如何优化长尾关键词intitle:Yadid's World]输入搜索框就可以查 到想要得到的结果注意：“intitle:”后面不能有空格 4、十大百度搜索技巧（四）—-site site的作用就是将搜索范围界定在指定网站中,有时我们如果知道某一个站内就有自己想要的东西，那么我们就可以把这个界定界定到这个站内，来提高查询效率 本文由销售技巧培训整理编辑https://www.doczj.com/doc/dd14875795.html,/ 一、深度优先搜索和广度优先搜索的深入讨论 （一）深度优先搜索的特点是： （1）从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2-7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。 但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法（二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。 （2）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当搜索深度较大时，如例题2-5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。 （3）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。 （4）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。 （5）从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。 如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 二、广度优先搜索法的显著特点是： （1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。 （2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。 （3）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度（或广度）优先搜索算法：找到一个目标后，不是立即退出，而是记录下目标结点的路径和费用，如果有多个目标结点，就加以比较，留下较优的结点。把所有可能的路径都搜索完后，才输出记录的最优路径。 （4）广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。 （5）比较深度优先和广度优先两种搜索法，广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索算法法要快些。 #include ny=sta.p[top].y+Htry2[z]; sta.p[top].dir=z; top++; sta.p[top].x=nx; sta.p[top].y=ny; board [nx][ny]=top; chech [nx][ny]=true; z=-1; } else if(z==7)//如果不可行，而且是最好一次检查 { chech [sta.p[top].x][sta.p[top].y]=false; top--; while(1) { z=sta.p[top].dir; if(z!=7) break; else { chech [sta.p[top].x][sta.p[top].y]=false; top--; } } } if(top==-1||top==63)break;//如果回溯到-1，或者栈满，则退出循环 z++; } for(i=0;i<8;i++) { for(j=0;j<8;j++) cout< 深度优先搜索的基本思想 搜索是人工智能中的一种基本方法，也是信息学竞赛选手所必须熟练掌握的一种方法，它最适合于设计基于一组生成规则集的问题求解任务，每个新的状态的生成均可使问题求解更接近于目标状态，搜索路径将由实际选用的生成规则的序列构成。我们在建立一个搜索算法的时候．首要的问题不外乎两个：以什么作为状态?这些状态之间又有什么样的关系?我们就简单的说一下深度优先搜索的基本思想吧。 如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。在深度优先搜索中，对于当前发现的结点，如果它还存在以此结点为起点而未探测到的边，就沿此边继续搜索下去，若当结点的所有边都己被探寻过．将回溯到当前结点的父结点，继续上述的搜索过程直到所有结点都被探寻为止。 深度优先搜索在树的遍历中也称作树的先序遍历。对于树而言，深度优先搜索的思路可以描述为： (1)将根结点置为出发结点。 (2)访问该出发结点． (3)依次将出发结点的子结点置为新的出发结点．进行深度优先遍历(执行(2))。 (4)退回上一层的出发结点。 深度优先搜索的具体编程可用递归过程或模拟递归来实现。他们各有各的优缺点。递归形式的程序符合思维习惯．编写起来较容易．但由于递归过程的调用借助较慢的系统栈空间传递参数和存放局部变量，故降低了执行效率。模拟递归使用数组存放堆栈数据，在管理指针和每层选择决策上不如递归容易编程．但一旦熟悉了程序框架，调试起来要比递归程序方便，由于数组一般使用静态内存．访问速度较快，执行效率也较高． 经典例子、找零钱（money.pas） 问题描述：有2n个人排队购一件价为0.5元的商品，其中一半人拿一张1元人民币，另一半人拿一张0.5元的人民币，要使售货员在售货中，不发生找钱困难，问这2n个人应该如何排队？找出所有排队的方案。（售货员一开始就没有准备零钱） 输入： 输入文件money.in仅一个数据n 输出： 输出文件money.out若干行，每行一种排队方案，每种方案前加序号No.i，每种方案0表示持0.5元钞票的人，1表示持1元钞票的人 样例： money.in递归算法和非递归算法的区别和转换
随机直接搜索优化算法NLJ辨识算法
深度优先与广度优先
多机器人路径规划研究方法
n!非递归算法的设计与实现
深度优先与广度优先
最佳优先模式--搜索引擎算法分析
公交换乘算法
可制定的路线规划
搜索方法
几大搜索引擎排名算法趣味解析
答深度优先搜索算法的特点是
汉诺塔问题的非递归算法分析
百度搜索技巧的四个方法
深度优先搜索和广度优先搜索的深入讨论
马踏棋盘非递归算法
深度优先搜索的基本思想
相关主题
文本预览