<<数学之美>> part5

摘要: [图论] [网络爬虫] [图的遍历]

图论

说到图论,必须要提的就是KonigsBerg七桥问题,简单说就是哥尼斯堡这个地方的有四块独立的区域,由七座桥相互连接,如下图:

哥尼斯堡七桥问题

目标是从任意一个点A,B,C,D中的一个出发,不重复的走遍所有的路,并且回到原点,为了验证这个确实是不可能的我们采用递归遍历的方式穷举所有可能,下面是python代码(data表示每个节点可以到达的其他节点,以及与其他节点的连接路线数,因此所有数字加起来是总路线数的两倍,如果需要修改数据验证的话,记得每次都要修改两个地方哦,*例如:如果想把A到B的路线修改为5条,那么同时也要把B到A的修改为5条才行):

# -*- coding:utf8 -*-
#filename:konigsBerg.py
#version:1.0
#author: NemoHo
import sys

data={
#'A':{'B':2,'D':1},
#'B':{'A':2,'C':2,'D':1},
#'C':{'B':2,'D':1},
#'D':{'A':1,'B':1,'C':1}
'A':{'B':1,'D':4},
'B':{'A':1,'C':2,'D':2},
'C':{'B':2,'D':2},
'D':{'A':4,'B':2,'C':2}
}

def check_win(first,cur,data):
    if first != cur:
        return False
    for ch in data:
        for ch_sub in data[ch]:
            if data[ch][ch_sub] > 0:
                return False
    print "===============unbeliverb you win!===================="
    sys.exit(0)
    return True

def check_no_way(ch,data):
    can_go = data[ch]
    for ch in can_go:
        if can_go[ch] > 0:
            return False
    print "no way can go!"
    return True

def konigsberg(first,cur,data):
    new_data = {}
    for key in data:
        new_data[key] = {}
        for key_sub in data[key]:
            new_data[key][key_sub] = data[key][key_sub]
    print "cur pos : %s" % cur
    if check_win(first,cur,new_data) or check_no_way(cur,new_data):
        return
    can_go = new_data[cur]
    for ch_sub in can_go:
        if can_go[ch_sub] > 0:
            can_go[ch_sub]-=1
            new_data[ch_sub][cur]-=1
            konigsberg(first,ch_sub,new_data)
            can_go[ch_sub]+=1
            new_data[ch_sub][cur]+=1

if __name__ == '__main__':
    for ch in data:
        konigsberg(ch,ch,data)
        print "---------------------------"

当data中存在奇数,也就是说连接到某个地方的路线为奇数条时的运行结果图(结果太长,只截取了最后一段):

存在奇数时的运行结果图

当data中全是偶数时:

全是偶数时的运行结果图

这样我们起码从结果上来看发现结论是正确的,原理很简单:假设我们能够走遍所有的路并回到原点,那么说明进出原点的路线个数需要时偶数,也就是说最简单的讲AB两个点,我们从A出发,如果想要走遍AB以及所有路线并回到A,那么A到B的路线必须是进出成对出现的,也就是要满足偶数即可,如果是奇数的话在不重复的前提下,是不可能回到A的;

遍历方式

对于一张图,最重要的操作就是遍历,这里就涉及到两种遍历方式:

• BFS(广度优先遍历):例如从A出发,可以到达B,C,D,然后B可以到达E,F,那么根据广度优先,我们先从A到B,然后是C,D,也就是说优先级是跟到达A所需走的路线数成反比;
• DFS(深度优先遍历):同样的从A出发,到达B后,不忙着去C,而是观察B是否能到达其他地方,也就是将一条路走到底,没得走之后,再回退找其他的路走;

网络爬虫

之前写的一篇文章有提到,搜索引擎使用布尔代数的位运算的方式判断一篇文章是否满足某些关键字的条件来确定这篇文章是否应该被呈现给用户,当时主要是介绍了一下对关键字是否满足的判断,但是做这一切的前提是下载互联网上的网页到本地以及维护关键字表(这个就是网络爬虫的作用),这里我们重点介绍一下下载网页:

• 既然要下载网页,那么首先我们起码要找到这些网页,那么就涉及到了图的遍历问题,而对于搜索引擎来说,这个遍历不是简单的BFS或者DFS,可以这么说在网站跟网站之间,更像是DFS,而在同一个网站中则是BFS,原因如下:
  • 网站跟网站之间:这个涉及到握手的开销问题,所谓握手其实就是搜索引擎服务器与网站服务器建立连接通道的过程,这个过程是比较耗时的,因此尽可能的减少这个过程可以有效提高效率,所以如果以网站为节点看的话,更新是DFS;
  • 网站内部:对于一个网站内部的N多的网页来说,我们不可能全部都下载下来,我们的目的应该是尽可能下载多的有价值的网页,所谓有价值就是大家访问的多,那么哪些网页访问的多呢?答案是首页,以及点击一次链接或者很少次点击就能到达的网页,那么这种情况下我们采用BFS能够下载更多有价值的网页;
• 页面分析&URL提取:早期的网络爬虫并不太需要考虑这个问题,因为那时候的网页基本由HTML构成,也就是说URL就以文本的形式存在页面中,简单的用正则提取即可,但是目前的很多网页更多的使用js等脚本语言生成,不能再简单的从文本中检索URL了,目前的做法是将爬虫伪装成一个浏览器,因为既然浏览器可以解析js得到URL,那么让爬虫也做这件事就可以了(因此更好的爬虫应该是由浏览器内核开发人员来开发更合适也更强大);
• 最后为了不重复下载网页,需要维护一个HashTable存在已经下载过的网页,使用哈希表的原因是大部分的查询只需要一次运算即可,而随着互联网规模的增加,HashTable的大小甚至不能在一台服务器上存储,这时就涉及到分布式系统的问题,如果优化这个系统才是这个问题的核心和难点,不过基本优化手段都包含以下两条:
  • 避免重复查询URL:也就是说尽可能的不要让多台服务器重复的去查询同一个URL是否下载过等等,做到这一步的方法通常是为服务器尽可能的规定好访问范围,避免相互覆盖;
  • 批量查询写入:访问维护HashTable的服务器本身也是一个通信的过程,那么批量的查询和写入数据能够有效减少通信的次数;

Thanks Doctor JunWu;