学位论文 > 优秀研究生学位论文题录展示

航海距离系统的服务器端设计与实现

作　者: 蔡文健
导　师: 潘维民
学　校: 北京邮电大学
专　业: 计算机科学与技术
关键词: 航线设计启发式搜索 A*算法缓存系统多线程通信
分类号: TP393.05
类　型: 硕士论文
年　份: 2010年
下　载: 16次
引　用: 0次
阅　读: 论文下载

内容摘要

随着海运事业的发展,海运从业人员的增加,作为风险规避中的一项重要参考因素——海运航线及航线距离成为业内人士需要掌握的重要资料。然而,对于非海运从业人员来说,传统航线设计的复杂、专业过程无法适应需求,同时,现有的网站提供的航线里程表查询工具存在数据量少、更新慢、无航线显示等缺点。这样设计实现可视化、简单易用、自动设计任意两港口间航线以及计算两港口间距离的工具显得很有必要性。本文对世界海洋地图采用二级分区的思想建立起连通的航段网络图,并根据港口经纬度和所处地形的特点设计航线上港口和港口之间的路由关系。基于航段网络图,本文主要研究了最优航线的生成算法。在研究传统的静态最优路径算法的基础上,通过对其缺陷的分析和改进,最终实现并改进了以启发式搜索 A*算法为寻径算法的最优航线算法。在分析了A*算法常用的数据结构后,采用二叉堆和关联表混合实现的数据结构,从而极大地提高了算法的搜索性能。另外,由于海洋航线本身的特殊性,通过使用海洋上两点间的大圆航线距离作为A*算法的启发函数,极大提高了航线的准确性。由于航线服务的实时性、同步请求的特点,所以服务器端对航线数据的读取速度有很高的要求。为此,本文研究了开源的高性能缓存系统Memcached。另外,本文还研究了航线服务的发布方式——以客户机／服务器模型为基础的Socket多线程通信方式。针对本系统的特点,采用多线程的Socket通信方式可以处理大量客户端的航线请求。

全文目录

摘要  4-5
Abstract  5-9
第一章绪论  9-14
  1.1 课题背景  9
  1.2 传统航线设计  9-11
    1.2.1 航线类型  9-10
    1.2.2 传统航线设计的方法  10-11
  1.3 主要研究内容及意义  11-13
  1.4 本文组织结构  13-14
第二章航线设计  14-18
  2.1 基本概念  14
  2.2 两级分区  14-16
  2.3 路由点设计  16
  2.4 航线设计  16-17
  2.5 数据库设计  17-18
第三章缓存系统设计  18-27
  3.1 缓存系统概述  18-19
    3.1.1 缓存系统目标  18
    3.1.2 一般原理  18-19
  3.2 memcached缓存系统  19-24
    3.2.1 memcached介绍及其特点  19-20
    3.2.2 memcached内存存储方式  20-22
    3.2.3 memcached的分布式  22-24
  3.3 航海距离系统缓存设计  24-27
    3.3.1 航段数据缓存设计  24-25
    3.3.2 路由数据缓存设计  25-27
第四章寻径算法  27-39
  4.1 概述  27-28
    4.1.1 图的定义  27
    4.1.2 最短路径定义  27-28
  4.2 搜索策略  28-29
    4.2.1 一般搜索过程  28-29
    4.2.2 搜索策略的评价准则  29
  4.3 传统寻径算法  29-33
    4.3.1 深度优先搜索  30
    4.3.2 广度优先搜索  30-31
    4.3.3 Dijkstra算法  31-32
    4.3.4 算法分析  32-33
      4.3.4.1 深度优先搜索(DFS)  32
      4.3.4.2 广度优先搜索(BFS)  32
      4.3.4.3 Dijkstra算法  32-33
  4.4 A~*算法  33-39
    4.4.1 启发式搜索  33-34
    4.4.2 启发函数  34
    4.4.3 评价函数的优劣  34-35
    4.4.4 搜索过程  35-36
    4.4.5 数据结构  36-39
      4.4.5.1 未排序的数组或链表  36
      4.4.5.2 排序数组  36-37
      4.4.5.3 排序链表  37
      4.4.5.4 索引数组  37
      4.4.5.5 关联表  37
      4.4.5.6 二叉堆  37-38
      4.4.5.7 混合实现  38-39
第五章航线算法  39-50
  5.1 算法概述  39
  5.2 算法流程  39-40
  5.3 主要数据结构  40-50
    5.3.1 航段网络图  41-43
    5.3.2 寻径算法  43-50
第六章 socket通信  50-64
  6.1 基本概念  50
  6.2 socket类型  50-51
  6.3 客户机/服务器模型  51-52
  6.4 系统调用  52-56
    6.4.1 创建套接字  52-53
    6.4.2 绑定套接字  53-54
    6.4.3 监听  54
    6.4.4 接受连接  54-55
    6.4.5 连接服务器  55
    6.4.6 发送与接受数据  55
    6.4.7 关闭套接字  55-56
  6.5 多线程机制  56-61
    6.5.1 线程概述  56-57
    6.5.2 编程接口  57-61
      6.5.2.1 创建线程  57
      6.5.2.2 等待线程  57-58
      6.5.2.3 线程结束  58
      6.5.2.4 线程属性  58-60
      6.5.2.5 同步机制  60-61
  6.6 航线请求服务  61-64
第七章总结及展望  64-65
参考文献  65-66
致谢  66-67
作者攻读学位期间发表的学术论文  67

航海距离系统的服务器端设计与实现

内容摘要

全文目录

相似论文