金晖のBlog

模拟退火 规定函数f(x)f(x)f(x)为所求问题所需的成本代价函数，选取合适的x使得成本代价尽可能小。 一般来说，函数图像具有一定的连续性。对于某一个局部区域，左右邻域的值相对于当前选取的方案来说不会差距太大。可以利用该性质，优化一下搜索的方法。 概念 温度T：相当于步长，区间范围的这么一个概念。温度越大，对于当前选择的点来说，考虑的邻域的范围就越大。温度是一个不断降低的过程，每次随机的区间都会不断缩小。最终，温度会收敛到一个最低值，所选的点也就固定住了。 初始温度T0T_0T0​：一开始的温度 终止温度TET_ETE​：最后的温度。下降到该温度后程序结束。 衰减系数kkk：T′=T×kT_{}'=T \times kT′​=T×k 。衰减系数k可以规定温度衰减的形式，可以是线性衰减，也可以是指数衰减。范围一般取(0,1)。衰减系数越接近于1，温度衰减的越慢，找到最优解的可能性就越大。 过程 以下内容摘抄于oi-wiki Quote / 参考 模拟退火时我们有三个参数：初始温度 T0T_{0}T0​，降温系数 d，终止温度 TkT_{k}Tk​。其中T0 ...

旅行商问题 简介 旅行商问题（简称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 脚本对代码打包并利用代码压缩工具防止程序被破解 项目成果 独立开发出一款竞技游戏。联机对战与匹配系统增加了游戏的竞技性、实时渲染与粒子效果粉饰了游戏的画面感、 聊天机制与被动技能也提高了游戏的互动性。 项目可改进: 暂时还没办法显示天梯分，可以完善天梯榜单功能 提供用户上传头像的界面 优化对战平台的界面美化 允许玩家 ...