启发式搜索算法在公交查询系统中的应用 毕业论文.doc

启发式搜索算法在公交查询系统中的应用 摘 要本文研究了启发式搜索算法应用于公交查询系统。在每一步启发式搜索算法通过对状态空间中搜索的每一站点进行评估，得到最好的位置，然后再从这个位置进行搜索直到目标。本文设计了一个启发式算法搜索公交线路，用来查询起点站和终点站之间的线路，它为公交查询系统提供了一种有效的解决方法。关键词公交系统；启发式搜索算法；数据库。heuristic searchingalgorithm in bus systems application abstract: this paper studied the application of heuristic algorithm on bus enquiry system., through evaluate each standpoint of state space at each step,the heuristic algorithm get the optimum position of bus station ,and then go on seaching until to the target point.this paper design a heuristic algorithm to seach bus lines between start station and terminate station.thus provding a vailid solution to bus enquiry system.key words: bus system; heuristic algorithm; database.前言公共交通运输覆盖面广、经济快捷，是大多数出行者的首选方式，也是各地城市政府大力发展的一种交通方式。如果能够提供一种服务，为市民和外来游客了解本地道路情况，方便、快捷、经济、高效地利用公交线路的方案，将方便他们的出行和生活，同时减少不必要的交通流量，提高交通运输的效率和城市的地位。在我国，大部分城市在公交方面都作出做出了很大努力，提出了“优先发展城市公共交通”的交通政策。然而目前大多数城市在公交线网布局规划、公交站点设置以及公交换乘枢纽设计等方面还存在一定的不合理因素，换乘比率高是我国城市公交出行的一个普遍现象。根据相关资料对乘客的出行心理进行了调查分析，其结果表明，“换乘次数”是大部分公交乘客在选择出行方案时首先考虑的因素。城市公交查询系统正是在这种情况下提出的。本人开发出以换乘次数最少为第一目标、站数最少和路径最短为第二目标的公交查询系统，这对于市民特别是外来旅游、出差、就医等急需了解本地道路情况的人提供了极大的方便，同时提高交通运输的效率和公交运输在城市中的地位，减少不必要的交通流量，具有很重要的现实意义。1 启发式搜索算法1.1 启发式搜索算法的概述启发式搜索算法最早是由g.波利亚提出，其主要针对数学题的解题及方法（前提为有解存在）。而现代启发式搜索算法要解决的问题，其解的存在往往呈现不确定性，亦或问题的初始与目标系统看起来是明显矛盾的。启发式搜索算法就是利用搜索过程所得到的问题自身的一些特性信息来对每个搜索的位置进行评估, 得到最好的位置，再从这个位置进行搜索直到目标。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。1.2 启发式搜索算法的优点启发式算法能够迅速发展是因为它有以下长处：1.跟广度和深度优先搜索相比，广度和深度优先搜索都是在一个给定的状态空间中穷举，在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率很低，甚至不可完成。然而启发式搜索克服了这个缺点，它在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。2.跟盲目搜索相比，盲目搜索利用计算机计算快速的特点,遍历所有可能的路径,最后找到结果,对于规模比较小的问题,是相当有效的,但对于一个规模很大的问题,计算机无法保存其全部状态空间,而且,与解有关的状态空间一般仅是全部状态空间的一部分。而启发式搜索则是对搜索的位置进行评估，取得最好的位置，再从这个位置进行搜索直目标，无需搜索所有的路径。3.一些启发式算法可以用在最优算法中，如在分支定界算法中，可以用启发式算法估界。4简单易行；比较直观；易被使用者接受。5.速度快，在适时管理中非常重要。6多数情况下，程序简单，因此易于修改。1.3 启发式搜索的过程启发式搜索基本过程如下:(1)给定初始状态s,产生一个状态的有限描述。(2)使用发生函数q(x)对s产生其后的每个后续状态。(3)对产生的状态检查,有无目标状态g,如果有则搜索成功。(4)如果目标状态g没有出现,就用估价函数f(x)对这些节点进行评估,选择最有希望的节点,继续使用q(x)产生它的子节点,重复步骤3。(5)如果所有可能的节点都使用q(x)拓展过,目标状态g还是没出现,则搜索失败1.4 估价函数和启发信息在具体问题中,往往能利用与该问题有关的信息来简化搜索过程,此类信息即为启发信息,启发式搜索就是利用该信息进行的搜索过程。利用控制性的启发信息有两种情况:一种是没有任何控制性知识做为搜索依据,因而搜索的每一步都是随意的;另一种是有充分控制性知识做为依据的,因此搜索的每一步都是正确的,也就是每一步都落在最佳的路径上,这种搜索叫最佳搜索。一般情况下是介于两者之间。与具体问题有关的控制性知识称为搜索的启发信息,它反映在估计函数中。估价函数的作用是估计open表中每个状态的估价函数值,按照值的大小重新排序。设计估计函数要考虑两方面内容:己经付出的代价和将要付出的代价。一般把估价函数f(x)定义为初始节点经过n节点到达目标节点的最小代价路径的代价估计值。其一般形式为:f(n)=g(n)+h(n)其中g(n)是从初始点s到n的实际代价,而h(n)是从n到目标节点g的最佳路径的估计代价。一般来说,在f(n)中,g(n)的比重越大,越倾向于横向搜索,h(n)的比重越大,表示启发性越强。保持g(n)项就保持了搜索的宽度优先成分,这有利于搜索的完备性,但会影响搜索的效率。在特殊情况下,如果只希望找到到达目标节点的路径,而不关系已经付出的代价,那么g(n)的作用可以忽略。另外,当h(n)g(n)时,也可以忽略g(n),这时有f(n)=h(n),有利于搜索效率,但是影响搜索的完备性。1.5 使用启发式搜索线路当只知道起点站和目的站时，本系统采用的是启发式算法，启发式搜索是在状态空间中的一种搜索，它对每一个搜索的位置进行评估，据给定的权值得出最好的位置，再从这个位置继续进行搜索直到目标。2 系统设计2.1 系统目标本系统以南宁公交路线为实例，为本市的乘客提供全面、准确的公交信息。在实现的功能上，系统还可以进行用户管理、信息查询功能，包括公交车站、公交线路和地名查询。本系统的核心功能是公交出行方案查询，当用户输入起始站点和终止站点时，就可以查询出以最少换乘为目标的公交出行方案。 在界面设计上，本系统特别注意美观大方、操作简单、界面友好，就算是不懂计算机的普通用户也能操作，获得自己所需要的信息。2.2 系统平台选择2.2.1 系统硬件平台由于本系统面对的用户是南宁市的乘客或外来的游客，因此系统对硬件平台的要求不应该太高，越低越好。2.2.2 系统操作平台考虑到国内个人计算机的操作系统一般都是microsoft的windows系列，因此本系统操作平台选择windows系列。2.2.3 开发工具visual c+ 6.0visual c+是一个功能强大的可视化软件开发工具。自1993年microsoft公司推出visual c+1.0后，随着其新版本的不断问世，visual c+已成为专业程序员进行软件开发的首选工具。visual c+应用程序的开发主要有两种模式，一种是win api方式，另一种则是mfc方式，传统的win api开发方式比较繁琐，而mfc则是对win api再次封装，所以mfc相对于win api开发更具备效率优势，因此，本系统采用的是mfc方式的开发模式。 vc作为一个主流的开发平台一直深受编程爱好者的喜爱，是因为它具有以下特点:1.可视化编程不像传统的程序设计语言，通过编程计算来设计用户界面，visual c+提供了可视化设计工具，把windows界面设计的复杂性“封装”起来，开发人员只需写少量的代码，就能够得到很美的界面。2.访问数据库visual c+具有很强的数据库管理功能。利用数据控件和数据库管理窗口，可以直接建立或处理microsoft access格式的数据库，并提供强大的数据存储和检索功能。同时，visual c+还能直接编辑和访问其它外部数据库。另外，visual c+提供开放式数据连接(open database connectivity)，即odbc功能，可以通过直接访问或建立连接的方式使用并操作后台大型的网络数据库，如sql server. oracle等。3.动态数据交换(dde )利用动态数据交换(dynamic data exchange)技术，可以把一种应用程序中的数据动态地链接到另一种应用程序中，使两种完全不同的应用程序可以交换数据、进行通信，在windows环境下为多个应用程序之间以client/server方式建立起一条动态数据链路。当原始数据变化时，可以自动更新链接的数据。4.动态链接库(dll)visual c+可以通过动态链接库技术将c/c+或汇编语言编写的程序加入到visual c+中，可以象调用内部函数一样调用其它语言编写的函数。此外，通过动态链接库，还可以调用windows应用程序接口(api)函数，实现sdk所具有的功能。2.2.4 数据库平台accessaccess 是微软公司推出的基于windows的桌面关系数据库管理系统（rdbms），是office系列应用软件之一。它提供了表、查询、窗体、报表、页、宏、模块7种用来建立数据库系统的对象；提供了多种向导、生成器、模板，把数据存储、数据查询、界面设计、报表生成等操作规范化；为建立功能完善的数据库管理系统提供了方便。 access是一种关系型数据库管理系统，其主要特点如下：存储方式单一access管理的对象有表、查询、窗体、报表、页、宏和模块，以上对象都存放在后缀为（.mdb）的数据库文件种，便于用户的操作和管理。界面友好、易操作access是一个可视化工具，用户想要生成对象并应用，只要使用鼠标进行拖放即可，非常直观方便。系统还提供了表生成器、查询生成器、报表设计器以及数据库向导、表向导、查询向导、窗体向导、报表向导等工具，使得操作简便，容易使用和掌握。集成环境、处理多种数据信息access基于windows操作系统下的集成开发环境，该环境集成了各种向导和生成器工具，极大地提高了开发人员的工作效率，使得建立数据库、创建表、设计用户界面、设计数据查询、报表打印等可以方便有序地进行。2.3 系统需求分析公交查询系统需求分析如下：（1）公交查询系统需要满足来自两方面的需求，这两个方面分别是乘客和系统管理员。（2）乘客功能能修改自己的登录密码、能按不同的排序方式查看公交线路的信息、能查询公交路线。（3）系统管理员的功能的信息量大，数据安全性和保密性要求最高。除了具有管理系统的基本功能外，还要管理乘客的基本信息，如乘客的删除、添加等。还要不定期的检查系统，发现系统的不足，改善系统，维持系统的稳定性。 3 系统总体框架设计3.1系统结构3.1.1系统结构框架启发式搜索算法在公交查询系统中的应用应用按起点站升序按起点站降序按路线名升序按路线名降序按终点站升序按终点站降序排序操作数据管理备份数据库户还原数据库查询操作站点查询换乘查询用户管理添加用户修改密码删除用户用户管理添加用户修改密码删除用户本系统主要有五大模块：用户管理，排序操作、查询操作、数据管理。其框架如下图所示：3.1.2 功能模块介绍系统主要功能模块介绍：用户管理模块该模块可以对用户的基本信息进行修改，包括：修改密码、添加用户、删除用户。排序操作模块该模块可以对不同的要求对线路进行不同的排列，包括：线路名升序、线路名降序、起点站升序、终点站升序等。查询操作模块该模块主要包括：按路线名查询、起点站查询、站点查询、换乘查询。按路线名查询，分为精确查询和模糊查询。精确查询：乘客输入需要查找的路线名，同时可以定位。模糊查询：乘客只是输入只需输入一个或几个字，系统就可以找到与之匹配的信息。按起点站查询，也分为精确查询和模糊查询。站点查询，站点查询采用模糊查询方式。换乘查询该查询包括以最少换乘为前提，站数最少的公交出行方案查询和最短路径的公交出行方案。3.2 系统界面组织界面是系统和用户实现交互的部分，它表现了系统的整体感觉。界面是否友好是用户能否接受系统的前提。系统界面的设计原则: 1)以用户为中心; 2)界面整洁; 3)菜单和工具栏能够根据需要切换，使用方便;4)整体风格一致，尤其是对话框字体大小、按钮摆放位置等。4 数据库详细设计4.1 txt文件介绍 txt文件是一个最简单的文本文件，它用来顺序储存公交线路的主要信息，包括路线名、该线路的完整路线（上行、下行）。该文件用来启发式搜索计算两个站点之间的最优路线。下面我简要说明一下文件的基本操作：文件打开本系统我采用c语言对进行操作，打开文件为：file *fp; /定义文件指针*fpfp=fopen(line.txt,r);读文件内容目前获取文件内容的方法有很多，如read、fgetc、getw等。根据本人和实践的需要，我选择了fgetc进行文件读取，它一次只能读取一个字符。代码如下：char ch;ch = fgetc(fp)关闭文件在对文件操作完毕以后，我们一定要记住关闭文件，代码如下：fclose(fp);4.2 access数据库用户除了对两个站点之间的路线进行查询外，还会进行其他的一些操作，如按路线名查找某一条路线的详细信息；输入一个站点，求出经过该站点的所有路线；对公交线路的顺序进行不同的排序，以便进行查询。基于这种情况，我设计了一个linetable表，用来储存公交线路的详细信息。如下图：另外，系统对不同的用户进行了特殊的限定和管理。系统用户能对所有的功能进行操作，一般用户只能对一部分功能进行操作。因此，我设计了一个usertable表，对用户进行相关的储存。如下图：当“popedom”为“系统管理员”是，则该用户为系统管理员，能够操作系统的所有功能，否则，该用户为一般用户。 5 算法分析与实现5.1 数学模型由于在乘坐公交车的时候，可能会涉及到许多的因素，比如：任意两个站之间的路程都可能不相等；每一辆公车的速度也不相同，意外的停车等。针对这些因素，我们对公车进行如下理想的假设：1假设到达相临两个站点时间相等。2不考虑意外，如道路损坏、乘车高峰期、交通事故。3各处路况都相同，公交跟地铁在任何路线上的速度不变。4公交车只能在行使路线上的相应站点停靠。5假设公交一直处于理想的行驶状态下。 定义下面的符号：lk：第k条路线，k=1,2,3,。si：第i个站点，i=1，2，3。s：表示起始站点。t：表示目标站点。5.2启发式搜索算法的实现根据启发式搜索的原理，具体的求解步骤为：1.将待展开的节点集合(open 表)为 s，已展开的节点集合(closed 表)为 ，节点 s 的权值为 g(s) = 0。2如果open=，搜索失败退出程序。3每次从 open 表中取出一个节点 n，如果n=t，则搜索成功，退出程序。4. 将n根据规则扩展产生一组节点 mi，然后把 n 放入 closed 表中。 5如果open表和closed表都没有mi，则把 mi 的源标记为 n，权值：在同一线路时，g(mi) = g(n) + 1 ，并放入 open 表中。 换车时，g(mi) = g(n) + 3 ，并放入 open 表中。 6如果 open 表中已存在mi的节点，并且权值 g(mi) g(n) + 1（不换车时）或g(mi) g(n) + 3（换车时），说明从 s 到 mi 并且经由 n 的路径要比先前搜索得到的路径要短。因此，把 mi 的源改记为 n，权值 g(mi) g(n) + 1（不换车时）或g(mi) g(n) + 3（换车时），仍放入 open 表中。 7如果 closed 表中已存在的mi节点，并且权值 g(mi) g(n) + 1（不换车时）或g(mi) g(n) + 3（换车时）。同理，把 mi 的源改记为 n，权值 g(mi) g(n) + 1（不换车时）或g(mi) g(n) + 3（换车时），并从 closed 表中取出重新放入 open 表中，留待以后重新搜索计算 mi 的子节点的层深。 8open中的结点按g值从小到大排序9回到步骤2继续执行。6 系统详细设计6.1 数据库连接编写为了使用程序方便移植，新建crecorduser和crecordline两个类，他们都是继承crecordset类，crecroduser用于连接usertable表，主要代码为：cstring crecorduser:getdefaultconnect()return _t(odbc;dsn=bus);cstring crecorduser:getdefaultsql()return _t(usertable);crecordline用于连接linetable表，主要代码为： cstring crecordline:getdefaultconnect()return _t(odbc;dsn=bus);cstring crecordline:getdefaultsql()return _t(linetable);6.2 登录界面这个界面比较简单，两个编辑框，一个用于输入用户名，一个用于输入用户密码；两个按钮,一个“登陆”按钮，一个“退出”按钮；还有几个静态文本框。如下图：“登陆”按钮的代码如下：void cnanninggjcxxitongdlg:onok() / todo: add extra validation herecrecorduser record; cstring msqlstr;updatedata(true);if (m_username.isempty() messagebox(请输入用户名！,提示！);return;else if (m_password.isempty() messagebox(密码不能为空！,提示！);return;msqlstr = select * from usertable where username=;msqlstr = msqlstr + m_username;msqlstr = msqlstr + ;str=m_username; if (!record.open(afx_db_use_default_type, msqlstr)messagebox(usertable表打开失败！,提示！);return;if (!record.iseof()if(m_username!=record.m_username)messagebox(用户名请注意大小写！,提示！);return;else if(m_password!=record.m_password)messagebox(密码不正确或大小写不对！,提示！);return;else if(m_password=record.m_password&m_username=record.m_username) if(record.m_popedom=系统管理员)i=1;elsei=0;cdialog:onok(); cbus bus;bus.domodal();elsemessagebox(用户名不正确！,提示！);return;登陆后的主界面如下图：6.3 线路名查询在主界面上选择单选按钮“线路名称”,然后再编辑框中输入你想要查找的路线名，点击“精确查询”或“模糊查询”按钮，查询的结果将会在下面显示出来。“精确查询”按钮的主要代码如下：if(m_name.isempty()m_adodc.setrecordsource( select id ,name as 路线名 ,fstation as 起点站 ,ftime as 首班时间 ,ltime as 末班时间 ,lstation as 终点站 , piaozhi as 票制 ,lucheng as 路程 ,sxing as 上行 ,xxing as 下行 from linetable);elsemsqlstr=select id ,name as 路线名 ,fstation as 起点站 ,ftime as 首班时间 ,ltime as 末班时间 ,lstation as 终点站 , piaozhi as 票制 ,lucheng as 路程 ,sxing as 上行 ,xxing as 下行 from linetable where name=;msqlstr = msqlstr + m_name;msqlstr = msqlstr + ;m_adodc.setrecordsource(msqlstr);m_adodc.refresh();refresh_data();messagebox(搜索完毕!,提示!);“模糊查询”按钮的主要代码如下：if(m_name.isempty()m_adodc.setrecordsource(select id ,name as 路线名 ,fstation as 起点站 ,ftime as 首班时间 ,ltime as 末班时间 ,lstation as 终点站 , piaozhi as 票制 ,lucheng as 路程 ,sxing as 上行 ,xxing as 下行 from linetable);elsemsqlstr=select id ,name as 路线名 ,fstation as 起点站 ,ftime as 首班时间 ,ltime as 末班时间 ,lstation as 终点站 , piaozhi as 票制 ,lucheng as 路程 ,sxing as 上行 ,xxing as 下行 from linetable where name like;msqlstr = msqlstr + %;msqlstr = msqlstr + m_name;msqlstr = msqlstr + %;msqlstr = msqlstr + ;m_adodc.setrecordsource(msqlstr);num=m_adodc.getcachesize();m_adodc.refresh();refresh_data();messagebox(搜索完毕!,提示!);6.4 按起点站查询在主界面上选择单选按钮“起点站”,然后再编辑框中输入你想要查找的路线名，点击“精确查询”或“模糊查询”按钮，查询的结果将会在下面显示出来。它的代码与“按路线名查询”代码相似。6.5按站点查询点击菜单上的“查询”按钮，再在列表中点击“按站点查询”，然后进入按站点查询主界面，如下图：在编辑框中输入你要查询的站点名，按“查询”按钮，将会在下面显示出经过该站点的所有路线的详细信息。“查询”按钮的代码如下：void ccheckstation:oncheckstation() cstring msqlstr;updatedata();if(m_station.isempty()m_adodc.setrecordsource(select id, name as 线路名,fstation as 起点站,ftime as 首班车,ltime as 末班车,lstation as 终点站,piaozhi as 票制,pay as 票价,sxing as 上行方向停靠车站,xxing as 下行方向停靠车站 from linetable);elsemsqlstr=select id, name as 线路名,fstation as 起点站,ftime as 首班车,ltime as 末班车,lstation as 终点站,piaozhi as 票制,pay as 票价,sxing as 上行方向停靠车站,xxing as 下行方向停靠车站 from linetable where sxing like;msqlstr = msqlstr + %;msqlstr = msqlstr + m_station;msqlstr = msqlstr + %;msqlstr = msqlstr + ;m_adodc.setrecordsource(msqlstr);m_adodc.refresh(); refresh();messagebox(搜索完毕!,提示!);6.6 换乘查询点击菜单上的“查询”按钮，再在列表中点击“换乘查询”，然后进入按换乘查询主界面，如下图：在起点和终点输入框中输入起点和终点，点击“查询”按钮，将会在下面显示出这两点之间的基于启发式搜索的最优路线和换乘次数。“查询”按钮的主要代码如下：if(!(p1=searchopen(open,strtemp,line)&!(ptemp=searchclose(close,strtemp, line)pnewnode=new node(strtemp,line);if(strcmp(pexpand-line,0000)=0)pnewnode-f=pexpand-f+1; /从根结点扩展新结点，权值加1else if(strcmp(pexpand-line,pnewnode-line)=0)pnewnode-f=pexpand-f+1;/同一条线路，权值加1else pnewnode-f=pexpand-f+3;/要换车，权值加3pnewnode-parent=pexpand;pexpand-childreni=pnewnode;addopen(open,pnewnode);i+;/保存下一个孩子