详解寻路算法(2)-生成图
1. 引言
上篇文章 中主要讲解了 A* 算法. 然而 A* 算法只是一个图搜索算法, 我们在游戏中的地图通常是用一些不规则图形定义的一片行走区域, A* 算法并不能识别这样的地图.
因此我们要做的工作就是把一张这样的地图抽象成可用邻接矩阵或邻接链表表示的数学上的图 $G=(V,E)$. 本文介绍两种方法, 可视图(visibility graph) 法和 导航网络(Navigation Meshes)法.
2. 可视图(visibility graph)
对于大多数地图来说, 我们可以看成由一个无限大的行走区域和若干个障碍物组成; 为了简化问题, 障碍物通常都可以看做多边形. 如下图所示:
想象我们处于起始点, 要绕过障碍物到达目标点. 当我们绕过障碍物时, 最短的方式...
编辑距离
题目源自Leetcode: 编辑距离-leetcode
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
解法: 动态规划
这是一道很漂亮的动态规划问题. 我们这样想: 越长的单词求解就越困难, 越短的单词求解就越简单: 长度为1的单词只需比较字母是否相...
详解寻路算法(1)-图搜索
1. 引言
寻路算法广泛应用在各种游戏中. 寻路算法要解决的问题是, 给定一个 "地图"(定义可行走区域), 一个起点, 和一个目标点, 求起点到目标点的最短路径. 解决寻路问题是一个复杂的过程, 涉及到若干个算法. 大体可以分为两个步骤:
把 地图 抽象成 图. 这里的图指的是数学上的图 $G=(V,E)$;
对图进行搜索.
相比图搜索, 把地图抽象成图通常会比较复杂. 这篇文章先介绍介绍图搜索算法. 在下篇文章中, 我会介绍几种把地图抽象成图的方法.
图搜索算法有很多. 在寻路算法中, 主要用到 A* 算法. 这里我会先介绍 Dijkstra 算法, 然后引出 A* 算法. 稍后会看到, 这两种算法很相似: Dijkstra 算法总是搜索最近的, 适用于求解单源对所...
牛顿迭代法求平方根
1.先说结论
$\sqrt{a}$ 可这样求得: 令 $x_0$ 为任意实数, 执行以下迭代式:
\[x_i = \frac{x_{i-1}+\frac{a}{x_{i-1}}}{2} \tag{1}\]
迭代若干次, 当 $|x_i-x_{i-1}|$ 小于想要的精度时便可停止迭代. 最终的 $x_i$ 便可视为 $\sqrt{a}$. 根据 (1) 式我们可以很快写出求平方根的代码:
def sqrt(a):
x = 1.0
while True:
pre = x
x = (x + a / x) / 2
if abs(x - pre) < 1e-6:
break
retur...
在Lua中使用装饰器
引言
使用过 Python 的同学都会喜欢上 Python 的装饰器. 它提供一种语法, 对函数进行"声明":
def decorator(f):
def wrapper(x):
print 'call %s' % f.__name__
return "The 2nd power of {0} is {1}".format(x, f(x))
return wrapper
@decorator
def foo(x):
return x ** 2
装饰器本质上只是一种语法糖: 把目标函数作为参数传入装饰器. 巧妙地使用装饰器, 可以让程序变得简洁优雅. 比如说, 声明一个函数是事件, 声明一个函数是远程调用接口, 等等.
在...
调和级数的渐进表示
令 $H_n$ 为第 n 项调和数
\[H_n=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\sum_{i=1}^{n}\frac{1}{i}\]
证明 $H_n$ 是 $O(\log n)$ 的
证明 如下图所示:
$\sum_{i=1}^{n}\frac{1}{i}$可以看作图中蓝色阴影的面积; 而橙色部分的面积则可以看作函数 $y=\frac{1}{x}$ 的积分 $\int_{0}^{n}\frac{1}{x}\mathrm{d}x$. 因此有
\[\sum_{i=2}^{n}\frac{1}{i}\lt \int_{0}^{n}\frac{1}{x}\mathrm{d}x=\ln n\]
\[\sum_{i=1}^...
在Jekyll中使用LaTeX
我准备用 Jekyll + Github page 搭建自己的技术博客. 但是有个问题, 技术文章中不可避免地需要使用到数学公式, Jekyll 原生的 Markdown 解释器总是不能很好地使用 Latex. 通过查阅资料, 我最终解决了这个问题. 下面是我的做法:
禁用 Kramdown 自带的公式解释器:
在 _config.yml 中加入:
kramdown:
math_engine: null
导入 mathjax 的 javascript 代码:
在 _includes 下新建文件 latex.html, 粘贴上以下内容:
<script type="text/x-mathjax-config...
跳跃游戏
题目源自Leetcode: 跳跃游戏II-leetcode
给定一个非负整数数组, 你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置.
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2.
从下标为 0 跳到下标为 1 的位置, 跳 1 步, 然后跳 3 步到达数组的最后一个位置.
思路1: 动态规划
我们令 dp[i] 为 从第 i 个位置到最后一个位置所需的跳跃次数. 显然, 若数组长度为 n , dp[n] = 0. 对于其他的位置 i, 假设 j 是任意一个 i 能跳到的位置, dp[i] 应为 所有 dp[j] ...
51 post articles, 7 pages.