Forever Loop.

Trouble Busters

TVアニメ『はいふり』EDテーマ「Ripple Effect」/春奈るな

haifuri-ed

 

2016 年度的四月新番也在近期逐渐完结,其中《高校舰队》(青春波纹)是我个人非常喜欢的一部作品。看少女打船真的是太刺激了

最后一集的节奏把握的非常出色,无论是中间的营救作战还是最后的“感谢”,都让我内心为之颤动。推荐给所有还没有看过这部作品的同学。

这次的歌曲是作为剧集 ED,由春奈るな演唱的 Ripple Effect,只有在看完了整部作品后才发现歌词写的是多么的充满能量。

(更多…)

《恋×シンアイ彼女》——星への手紙から始まる恋

如果有人问你做什么最赚钱?
不知道大家会怎么回答。贸易?贩毒?抢劫?印钞?……
你说我么?恩,虽然可能印钞的确看起来很“赚钱”,但我也不是学金融的,对那方面也不了解。所以要我说的话应该是那个吧。恩,不难,很简单。这根本就是零成本的。虽然不想说绝对,但是每个人都能做的。说极端点的话,每个人都做过的。
所以,你明白我想说的了么?恩,明白就好。明白了的话我也就没必要赘言了。
所以,换个角度看GALGAME
这次我们来促膝谈:
《恋×シンアイ彼女》

恋×シンアイ彼女1

——多一项才能的少女与少一项才能的少年的恋爱故事

(更多…)

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) 发生时,插入操作有可能只在树的一侧插入以至整个树失去平衡。尽管我没有可靠的用例。

(更多…)