Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 实现(下)

Thoughts on Pathfinding – 实现(上)的部分中,我们说到了一些不同数据结构对于整个算法复杂度的影响,今天我们将继续列举一些数据结构带来的影响,以及在实际情况中的应用。

哈希表

索引数组使用了大量的内存来保存那些不在 OPEN 集中的节点。一个改变的方法就是使用哈希表,使用哈希函数 h(n) 把图上的每一个节点 n 映射到一个哈希码。让哈希表的大小是 N 的两倍来让发生冲突的可能性降到最小。假设 h(n) 的复杂度是 O(1),因为我们需要搜索整个结构,那么关系检查操作复杂度为 O(1),插入操作复杂度是 O(1),移除操作复杂度是 O(numnodes)。提升优先级操作的复杂度是 O(1)。

伸展树

堆是一种基于树的结构,它的期望时间复杂度是 O(log F)。在 A* 中,当你移出一个节点时由于其他节点需要移动的特性,最佳复杂度以及最差复杂度的变化会比较大。如果我们能够设计一种数据结构使得复杂的的变化趋于可控,哪怕最佳情况下的花费可能会变高。

伸展树就是一种可以自我调整的树形结构。任何对节点的访问都尝试把该节点推到树的顶部。这就产生了一种类似“缓存”的效果:很少被使用的节点将在不影响速度的情况下被慢慢地被移动到树的底部。你的伸展树有多大并不重要,因为操作的所需要的时间与你的“缓存空间”有关。在 A* 中,低花费的节点会被经常使用,高花费的节点不会被长时间使用,所以那些高花费的节点可以移动到树的底部。

在使用了伸展树以后,集合关系检查,插入,移除最佳以及优先级操作的最佳复杂度都是 O(log F),最差复杂度是 O(F)。有代表性的是,伸展树带来的缓存效果能避免最坏情况的发生。迪杰斯特拉算法以及带有低估的启发式函数的 A* 算法却有一些特性让伸展树达不了最优。特别是对于某个节点 n 以及邻居节点 n’ ,理论上当 f(n’) >= f(n) 发生时,插入操作有可能只在树的一侧插入以至整个树失去平衡。尽管我没有可靠的用例。

(更多…)

『僕たちはひとつの光/Future style』「僕たちはひとつの光」/μ’s

最近开始实习了,正在成为社会人的过程中不断进修中(纪念:仅有一个礼拜的暑假)。公司环境不错,目前带队的 leader 感觉也酷酷 der,总体来说还是挺满意的。唯一觉得有点不满意的就是每次下班回家路上所花费的时间比较久,到家以后会有点累,ORZ。坚持一下好了~

这次给大家带来的歌曲是《LoveLive! 剧场版》中的 Ending Song:僕たちはひとつの光。翻译成中文的意思大概就是:我们是融合在一起的光。是一首让 LLer 感动的曲子,不仅仅因为剧场版中的剧情,同时也因为有了这一段不算太长时间的追随,一点点看着 LL Project 从一开始只有一个简简单单的 PV 动画变得越来越有人气,在各方面都被大众所接受、所喜欢。无论是二次元中的 μ’s,还是给她们带来灵魂的现实中的 μ’s。我都很喜欢。

@tkg_ori

跳转之后可见歌词,歌词中出现了九个人的名字,你能发现么?

(更多…)

课程设计:基于 Jpacap 的简单流量监控软件

本学期的课程设计有两门,一门是有关 Java 的,另一门是有有关 Web 的。Web 的课程设计目前还在进行中,Java 的已经结束了。因为感觉这次 Java 课程设计写的这个小东西比起其他那些“XX 管理系统”貌似更有点实用价值(凑表脸),然后顺便凑个更(这样明目张胆的说出来真的好么?!)就 PO 出来了。

本次 Java 课程设计,我的选题是:《基于 Jpcap 的简单流量监控软件》。

(更多…)

『Angelic Angel/Hello,星を数えて』「Angelic Angel」/μ’s

一句话感受:最近真的是非常炎热捏!(T_T)

这首歌出自于在 2015 年 6 月 13 日上映的《LoveLive! 剧场版》,同时也被选择作为之前各种宣传 PV (哦哦哦,那个 90 秒的 PV 很赞的好么!)的 BGM,仅仅是听了一遍就彻底喜欢上了。特别是歌词中“Ah!「もしも」は欲しくないのさ、「もっと」が好きAngel ”这一段,截取下来做了铃声。

虽然是 Eli 推,但是这里的话还是放一张全员吧(我们家 Eli 是 Center!)w:

id=51060143

惯例的,跳转之后可见歌词。

(更多…)

Thoughts on Pathfinding – 实现(上)

如果不考虑具体的实现代码,A* 算法其实是相当简单的。想象它有一个 OPEN 集和一个 CLOSED 集。其中 OPEN 集保存着等待那些筛选的节点。在最初,OPEN 集只包含一个元素,那就是最开始的起始节点。CLOSED 集包含那些已经被访问过的节点。在最初,CLOSED 集是没有任何内容的。如果用图的方式来理解,那么 OPEN 集就是边境而 CLOSED 集就是那些可访问区域的内部。由于每一个节点同时保存着指向其父节点的指针,所以我们可以知道它是如何被访问到的。

在实际流程中,有一个主要的循环不停地从 OPEN 集中取出最佳的节点 n(拥有最小 f 值的节点)并检查这个节点。如果 n 是最终的目标节点,那么我们的任务就完成了。否则,节点 n 将从 OPEN 集中移除并加入 CLOSED 集。接着检查节点 n 的邻居,节点 n’。如果 n’ 也被访问过,那么我们就不再考虑这个节点(注)。如果 n’ 在 OPEN 集中,那么它以后肯定是会被检查到的,所以我们现在也不需要考虑这个节点(注)。否则,我们把 n’ 加入 OPEN 集中,并把它的父节点设置成 n。通往节点 n’ 的花费 g(n’) 将被设置成 g(n) + movementcost(n, n’)。

你可以在这里查看一些交互式图例的演示。

注:我在这里忽视了一个小小的细节。操作时你其实需要检查节点的 g 值是否变小了,如果变小了,你应该重新 OPEN 它。

注:如果你使用的是始终最小的启发式,这种情况不会发生。在实际设计中,通常使用的是不最小的启发式

你可以在这里看到 Python 的 C++ 的实现方法。

(更多…)