Tor工具初步探究(感谢Fay,FY和CC同学)

首先,感谢Fay老师,FY老师和CC老师对本人的鞭策,于是我去研究了一下Tor这个东西,撰下此文。

江湖上流传着一句话,叫“想FanQiang,带套吧”,这句话就像我们介绍了一个工具Tor,在FanQiang界,一般来说是用Tor技术的一个FireFox扩展,可以把FireFox发出的请求隐藏起来,以达到逃过GFW的效果。

Tor是第二代洋葱路由的一种实现。弄一堆server搞一个分布式网络出来,这些机器的组成的这个分布式网络提供路由功能,就叫:洋葱路由器。当我们使用这个洋葱路由,本文中对这个洋葱路由的使用就是基于Tor技术的那个插件。

事实上Tor刚刚出现的时候,并不是为了翻墙,而是一款为了维护访问者的隐私而诞生的,在最初的时候这是一个军方支持项目,之后与军方脱离关系,收到EFF的指导和支持,而且作为其一个项目得以继续发展,貌似到了05年EFF也给Tor断了奶,仅仅是继续维护其首页,仅此。

这个Tor的原理就是说,每一个安装了Tor的终端,发出请求时,这个请求会发向洋葱路由,请求包在路由间沿着不固定的路线传播,以达到匿名的作用,并信息在传递过程中,Tor还会对传递的信息进行加密,因此信息在这里传播是安全的。

一个最短路径的问题

题目:

北京的一位出租车司机向你抱怨:城市发展太快,公路越来越多,他已经疲于计算行驶路线,于是求你开发一个自动导航的工具。

出租车只能在公路上行驶。所有的公路都是笔直、双向的,相交的公路视为连通(可以在交叉点处从一条公路开到另一公路上)。由于道路施工,整个城市的公路系统可能并不完全通畅。如果乘客的目的地不在公路边,则乘客下车后要步行前往,步行路线不受公路限制。这位好心的司机还特别提出,乘客步行距离越短越好;其次,出租车行驶里程越短越好。

方便起见,用笛卡儿坐标系来描述城市地图,所有坐标都在第一象限[0, 10000]的范围内。公路宽度忽略不计。

输入格式:

第一行是一个整数k,代表公路条数。以下k行每行用4个非负整数描述一条公路(用空格隔开),前两个表示公路起点的坐标,后两个表示公路终点的坐标。下一行包含4个非负整数(用空格隔开),前两个表示乘客出发点(保证在某条公路上),后两个表示乘客目的地坐标。乘客必须在出发点上车,中途不换车。任意两条公路最多只有一个公共点。

输出格式

仅一行,为出租车行驶的里程数,保留一位小数(四舍五入)。

输入样例 例

2

2 2 10 10

10 2 2 10

3 3 9 4

输出样例

7.8

评分规则:

1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过1秒,否则该用例不得分;

2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

3. 本题包含20个测试点,前10组满足k<=10,后10组满足k<=50。每个测试点10分,共200分。

-----------------解答--------------------

太晚了,不写具体实现了,说说思路吧,明天有时间补代码。

这道题典型的最优路径问题,两种经典算法,Dijkstra和Floyd-warshall,各有优势。纯从算法复杂度上来说呢,Dijkstra要比 Floyd要稍微低一点,但是Dijkstra存在一个问题,每一次查询需要扫描一次节点集合,而Floyd就只需要运行时构建一次列表,而此后的查询只需查表。

考虑这道题目的要求,需要用20个测试点进行测试,就是说节点列表要更新20次,未提到每个测试点采用多少个测试用例,所以我觉得还是采用Dijkstra算法靠谱。

具体的算法设计:

1,算出节点列表

这一步是比较关键的,也相对麻烦,我认为甚至比 4 更麻烦,因为 4 的Dijkstra算法是既有的。

首先,我们有一些线段集合 D={d1, d2, ..., dn},我们记线段di为(Ai, Bi),其中Ai和Bi是线段端点。

然后,对集合D进行计算,即考虑线段交点,扩展集合D,若di和dj两个交点(Mij, Nij),那么D={d1, d2, ..., dn, (Ai, Mij), (Mij, Bi), (Aj, Mij), (Bj, Mij)}。由于两点之间线段最短,因此D中原有的线段不变,只加入新元素。在这一步涉及到一个计算线段交点的算法,分三步:1 通过向量积的方法看是否平行(题目中有,两条路最多1个交点,因此不存在重合问题,若是延长情况,这个问题可忽略),即,积为0无交点;2 有相交的情况,算出交点,这算法不复杂; 3 看交点坐标是否同时在两条线段上。

2,计算权值

权值就是距离,算出来就行了

3,构造可达矩阵

可达矩阵,这不用说了吧,无向图的邻接矩阵,求个n-1次方,然后求并。无向图的邻接是对称的,所以压缩存储,存一半就行了,一般来说是是稀疏的,所以存起来就行了。存矩阵的数据结构也好多,十字链表之类的,随便挑一个就行了。

4,获取起止点,通过dijkstra算法计算最短路径

接下来就是计算两个点,起始点V和终止点U之间的最短路径P,P是点的集合来描述路径的。dijkstra的算法描述也不用仔细写了吧~就是从V开始,列出所有可以直达的点集合S,及其权值,然后看以S中的点作为起点,在继续往下求,顺便看S中有没有可以互达距离小于直达距离的,就是说S中有三个点A, B, C,有A-B,和B-C的关系,且V-C的权值大于V-A, B-C权值之和,则更新V-C的权值,依次,知道S中出现U为止。

这个最优解就求出来啦,哈哈

-----------------------写完了才发现个问题-----------------------

低4步中的点U和V也是要在地1步中计算进D的,这个V是给出的,U是要求的,计算U的算法最SB的就是暴力计算,即把求终点到各个线段的垂直距离,然后找出最小的那个垂足,那个垂线段和已知线段的交点是叫垂足吧?

这就行了,基本就这些,有时间在写实现吧,应该不复杂的。

就怕流氓有文化---我爸跟我的短信对话

坐在办公室,5点半,收拾东西,准备下楼坐班车,突然收到老爸短信,内容如下:
浪淘沙 北戴河
大雨落幽燕,白浪滔天
秦皇岛外打渔船
一片汪洋都不见,知向谁边?
往事越三年
零六夏天
儿子登上山海关
住的套间
没吃海鲜
考了一盘羊肉串
回家冒雨过唐山
抗震碑前
拍照留念
----------------------------

那是06年,我和老爸去北戴河开会的时候
由于赶着下楼,于是回了一个字:

----------------------------

走在路上,收到老爸回复:
水。还潮呢,够冷
----------------------------

明显不服么,待坐在车上,我回:
沁园春 北戴河
晴空如碧,骄阳似火,白浪轻打
问何所是处,第一关口
龙头所处,东海西纳
游人如注,熙熙攘攘
但求一拜山海关下
滨海路,望不尽前处
无限宽广
往事岁月如画,那日尤似江南雨下
然丝丝南国,略逊豪情
无奈追梦,也罢也罢
不忘东海,不惧风雨
薪胆可饮,求成法
再回首,问第一关口
以我为大
----------------------------

30秒后,老爸回:
牛X
----------------------------

至此,此次对话结束。
我的感慨,流氓不可怕,就怕流氓有文化…
看他第一节写的还有点意思,到后边就不好好写了~~~
我本来想写一个好好回忆回忆,难得那两天,结果……写到后边,又忍不住的开始慷慨了……
不过最后还是低调的把“唯我独大”,改成了“以我为大”估计我要是不改,那“牛X”就该变成“吹牛B”了