金晖のBlog

旅行商问题 简介 旅行商问题（简称TSP问题）是这样描述的： 一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。这是一个非常经典的组合优化问题。由于其在交通运输，电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。 问题分析 从图论的角度看，可以把推销员的路径当成一条哈密顿回路，城市与城市之间的道路看做无向边，道路的距离看做无向边的边权，城市看做图中的点。所以，该问题实质是在一个带权完全无向图中，找条权值最小的哈密顿回路。 由于该问题的可行解是所有顶点（假设共有n个顶点）的全排列，所以一般精确算法的时间复杂度为O(N!)O(N!)O(N!)。随着顶点数的增加，时间复杂度会以指数级别的程度上升，所以这是一个NP-Complete问题和NP-Hard问题。 研究历史 早期的研究者使用精确算法（动态规划，暴力搜索等）求解该问题，但是随着问题规模增大，时间复杂度开始指数爆炸，快速增长到无法计算的地步，此时精确算法变得无能为力。因此在后来的研究中，国内外学者更偏向于使用近似算 ...

项目描述 此项目是一款基于 Django 的在线对抗游戏，支持联机对战并可依据玩家段位分数进行匹配 应用技术 Python、Django、Thrift、Js、Css、WebSocket、radius 项目功能 自主研发的游戏引擎以实现游戏界面的动态渲染功能 单人模式下支持 NPC 随机移动并计算概率以定时向其它 NPC 或用户发射炮弹 多人模式下支持联机对战，使用 thrift 在多线程下实现的消息队列、阈值扩大、匹配策略以及匹配成功后的处理方式 多人模式下使用 Django 自带的 websocket 通信实现对战中的同步机制如聊天功能 系统支持多端登录使用，既支持网页端，也支持 Acapp 端的使用（类似小程序），其信息也是保持同步的 使用 shell 脚本对代码打包并利用代码压缩工具防止程序被破解 项目成果 独立开发出一款竞技游戏。联机对战与匹配系统增加了游戏的竞技性、实时渲染与粒子效果粉饰了游戏的画面感、 聊天机制与被动技能也提高了游戏的互动性。 项目可改进: 暂时还没办法显示天梯分，可以完善天梯榜单功能 提供用户上传头像的界面 优化对战平台的界面美化 允许玩家 ...