精华内容
参与话题
问答
  • 夜深人静写算法(一)- 搜索入门

    万次阅读 多人点赞 2017-12-28 14:43:02
    搜索入门:深度优先搜索(记忆化、剪枝、IDA*)、广度优先搜索(A*、双向广搜)
    目录

    一、深度优先搜索
          1、DFS
          2、基于DFS的记忆化搜索   
          3、基于DFS的剪枝
                1) 可行性剪枝
                2) 最优性剪枝
          4、基于DFS的A* (迭代加深,IDA*)

    二、广度优先搜索
           1、BFS
           2、基于BFS的A*
           3、双向广搜

    三、搜索题集整理

    一、深度优先搜索
          1、DFS
               1) 算法原理
                深度优先搜索即Depth First Search,是图遍历算法的一种。用一句话概括就是:“一直往下走,走不通回头,换条路再走,直到无路可走”。
                DFS的具体算法描述为选择一个起始点v作为当前结点,执行如下操作:
                        a. 访问 当前结点,并且标记该结点已被访问,然后跳转到b;
                        b. 如果存在一个和 当前结点 相邻并且尚未被访问的结点u,则将u设为 当前结点,继续执行a;
                        c. 如果不存在这样的u,则进行回溯,回溯的过程就是回退 当前结点
                 上述所说的当前结点需要用一个栈来维护每次访问到的结点入栈,回溯的时候出栈(也可以用递归实现,更加方便易懂)。
                 如图1所示,对以下图以深度优先的方式进行遍历,假设起点是1,访问顺序为1 -> 2 -> 4,由于结点4没有未访问的相邻结点,所以这里需要回溯到2,然后发现2还有未访问的相邻结点5,于是继续访问2 -> 5 -> 6 -> 3 -> 7,这时候7回溯到3,3回溯到6,6回溯到5,5回溯到2,最后2回溯到起点1,1已经没有未访问的结点了,搜索终止,图中圆圈代表路点,红色箭头表示搜索路径,蓝色虚线表示回溯路径。 

    图1
             2) 算法实现
              深搜最简单的实现就是递归,写成伪代码如下:
    1      def DFS(v):
    2          visited[v] = true
    3          dosomething(v)
    4          for u in adjcent_list[v]:
    5              if visited[u] is false:
    6                  DFS(u)
               其中dosomething表示访问时具体要干的事情,根据情况而定,并且DFS是允许有返回值的。
               3) 基础应用
                   a. 求N的阶乘;
                   令f(N) = N!,那么有f(N) = N * f(N-1) (其中N>0)。由于满足递归的性质,可以认为是一个N个结点的图,结点 i (i  >= 1 ) 到结点 i-1 有一条权值为i的有向边,从N开始深度优先遍历,遍历的终点是结点0,返回1(因为0! = 1)。如图2所示,N!的递归计算看成是一个深度优先遍历的过程,并且每次回溯的时候会将遍历的结果返回给上一个结点(这只是一个思想,并不代表这是求N!的高效算法)。
    图2
                   b. 求斐波那契数列的第N项;
                   令g(N) = g(N-1) + g(N-2), (N > 2),其中g(1) = g(2) = 1,同样可以利用图论的思想,从结点N向N-1和N-2分别引一条权值为1的有向边,每次求g(N)就是以N作为起点,对N进行深度优先遍历,然后将N-1和N-2回溯的结果相加作为N结点的值,即g(N)。这里会带来一个问题,g(n)的计算需要用到g(n-1)和g(n-2),而g(n-1)的计算需要用到g(n-2)和g(n-3),所以我们发现g(n-2)被用到了两次,而且每个结点都存在这个问题,这样就使得整个算法的复杂度变成指数级了,为了规避这个问题,下面会讲到基于深搜的记忆化搜索。
    图3
                   c. 求N个数的全排列;
                   全排列的种数是N!,要求按照字典序输出。这是最典型的深搜问题。我们可以把N个数两两建立无向边(即任意两个结点之间都有边,也就是一个N个结点的完全图),然后对每个点作为起点,分别做一次深度优先遍历,当所有点都已经标记时输出当前的遍历路径,就是其中一个排列,这里需要注意,回溯的时候需要将原先标记的点的标记取消,否则只能输出一个排列。如果要按照字典序,则需要在遍历的时候保证每次遍历都是按照结点从小到大的方式进行遍历的。
    图4
               4) 高级应用
                   a. 枚举:
                       数据范围较小的的排列、组合的穷举; 
                   b. 容斥原理:
                       利用深搜计算一个公式,本质还是做枚举;
                   c. 基于状态压缩的动态规划:
                      一般解决棋盘摆放问题,k进制表示状态,然后利用深搜进行状态转移;
                   d.记忆化搜索:
                      某个状态已经被计算出来,就将它cache住,下次要用的时候不需要重新求,此所谓记忆化。下面会详细讲到记忆化搜索的应用范围;
                   e.有向图强连通分量:
                      经典的Tarjan算法;
                      求解2-sat问题的基础;
                   f. 无向图割边割点和双连通分量:
                       经典的Tarjan算法;
                   g. LCA:
                       最近公共祖先递归求解;
                   h.博弈:
                      利用深搜计算SG值;
                   i.二分图最大匹配:
                       经典的匈牙利算法;
                       最小顶点覆盖、最大独立集、最小值支配集 向二分图的转化;
                   j.欧拉回路:
                       经典的圈套圈算法;
                   k. K短路:
                       依赖数据,数据不卡的话可以采用2分答案 + 深搜;也可以用广搜 + A*
                   l. 线段树
                       二分经典思想,配合深搜枚举左右子树;
                   m. 最大团
                       极大完全子图的优化算法。
                   n. 最大流
                        EK算法求任意路径中有涉及。
                   o. 树形DP:
                       即树形动态规划,父结点的值由各个子结点计算得出。

          2、基于DFS的记忆化搜索
                1) 算法原理
               上文中已经提到记忆化搜索,其实就是类似动态规划的思想,每次将已经计算出来的状态的值存储到数组中,下次需要的时候直接读数组中的值,避免重复计算。
                来看个例子,如图5所示,图中的橙色小方块就是传说中的作者,他可以在一个N*M的棋盘上行走,但是只有两个方向,一个是向右,一个是向下(如绿色箭头所示),棋盘上有很多的金矿,走到格子上就能取走那里的金矿,每个格子的金矿数目不同(用蓝色数字表示金矿的数量),问作者在这样一个棋盘上最多可以拿到多少金矿。

    图5
                我们用函数DFS(i, j)表示从(1, 1)到(i, j)可以取得金矿的最大值,那么状态转移方程 DFS(i, j) = v[i][j] + max{ DFS(i, j-1), DFS(i-1, j) }(到达(i, j)这个点的金矿最大值的那条路径要么是上面过来的,要么是左边过来的),满足递归性质就可以进行深度优先搜索了,于是遇到了和求斐波那契数列一样的问题,DFS(i, j)可能会被计算两次,每个结点都被计算两次的话复杂度就是指数级了。
                所以这里我们可以利用一个二维数组,令D[i][j] = DFS(i, j),初始化所有的D[i][j] = -1,表示尚未计算,每次搜索到(i, j)这个点时,检查D[i][j]的值,如果为-1,则进行计算,将计算结果赋值给D[i][j];否则直接返回D[i][j]的值。
                记忆化搜索虽然叫搜索,实际上还是一个动态规划问题,能够记忆化搜索的一般都能用动态规划求解,但是记忆化搜索的编码更加直观、易写。
     
          3、基于DFS的剪枝
               1) 算法原理
              搜索的过程可以看作是从树根出发,遍历一棵倒置的树——搜索树的过程。而剪枝,顾名思义,就是通过某种判断,避免一些不必要的遍历过程,形象的说,就是剪去了搜索树中的某些“枝条”,故称剪枝(原话取自1999年OI国家集训队论文《搜索方法中的剪枝优化》(齐鑫))。如图6所示,它是一棵利用深度优先搜索遍历的搜索树,可行解(或最优解)位于黄色的叶子结点,那么根结点的最左边的子树完全没有必要搜索(因为不可能出解)。如果我们在搜索的过程中能够清楚地知道哪些子树不可能出解,就没必要往下搜索了,也就是将连接不可能出解的子树的那根“枝条”剪掉,图中红色的叉对应的“枝条”都是可以剪掉的。
     
    图6
              好的剪枝可以大大提升程序的运行效率,那么问题来了,如何进行剪枝?我们先来看剪枝需要满足什么原则:
                  a. 正确性
                      剪掉的子树中如果存在可行解(或最优解),那么在其它的子树中很可能搜不到解导致搜索失败,所以剪枝的前提必须是要正确;
                  b. 准确性
                      剪枝要“准”。所谓“准”,就是要在保证在正确的前提下,尽可能多得剪枝。
                  c. 高效性
                      剪枝一般是通过一个函数来判断当前搜索空间是否是一个合法空间,在每个结点都会调用到这个函数,所以这个函数的效率很重要。
                剪枝大致可以分成两类:可行性剪枝、最优性剪枝上下界剪枝)。
               2) 可行性剪枝
                可行性剪枝一般是处理可行解的问题,如一个迷宫,问能否从起点到达目标点之类的。
                举个最简单的例子,如图7,问作者能否在正好第11秒的时候避过各种障碍物(图中的东西一看就知道哪些是障碍物了,^_^)最终取得爱心,作者每秒能且只能移动一格,允许走重复的格子。
    图7
                仔细分析可以发现,这是永远不可能的,因为作者无论怎么走,都只能在第偶数秒的时候到达爱心的位置,这是他们的曼哈顿距离(两点的XY坐标差的绝对值之和)的奇偶性决定的,所以这里我们可以在搜索的时候做奇偶性剪枝(可行性剪枝)。
                类似的求可行解的问题还有很多,如N (N <= 25) 根长度不一的木棒,问能否选取其中几根,拼出长度为K的木棒,具体就是枚举取木棒的过程,每根木棒都有取或不取两种状态,所以总的状态数为2^25,需要进行剪枝。用到的是剩余和不可达剪枝(随便取的名字,即当前S根木棒取了S1根后,剩下的N-S根木棒的总和 加上 之前取的S1根木棒总和如果小于K,那么必然不满足,没必要继续往下搜索),这个问题其实是个01背包,当N比较大的时候就是动态规划了。
                 3) 最优性剪枝上下界剪枝
                 最优性剪枝一般是处理最优解的问题。以求两个状态之间的最小步数为例,搜索最小步数的过程:一般情况下,需要保存一个“当前最小步数”,这个最小步数就是当前解的一个下界d。在遍历到搜索树的叶子结点时,得到了一个新解,与保存的下界作比较,如果新解的步数更小,则令它成为新的下界。搜索结束后,所保存的解就是最小步数。而当我们已经搜索了k歩,如果能够通过某种方式估算出当前状态到目标状态的理论最少步数s时,就可以计算出起点到目标点的理论最小步数,即估价函数h = k + s,那么当前情况下存在最优解的必要条件是h < d,否则就可以剪枝了。最优性剪枝是不断优化解空间的过程。

          4、基于DFS的A*(迭代加深,IDA*)
               1) 算法原理
               迭代加深分两步走:
               1、枚举深度。
               2、根据限定的深度进行DFS,并且利用估价函数进行剪枝。

               2) 算法实现
               迭代加深写成伪代码如下:
    1  def IDA_Star(STATE startState):
    2      maxDepth = 0
    3      while true:
    4          if( DFS(startState, 0, maxDepth) ):
    5              return 
    6          maxDepth = maxDepth + 1
    图8
               3) 基础应用
               如图8所示,一个“井”字形的玩具,上面有三种数字1、2、3,给出8种操作方式,A表示将第一个竖着的列循环上移一格,并且A和F是一个逆操作,B、C、D...的操作方式依此类推,初始状态给定,目标状态是中间8个数字相同。问最少的操作方式,并且要求给出操作的序列,步数一样的时候选择字典序最小的输出。图中的操作序列为AC。
               大致分析一下,一共24个格子,每个格子三种情况,所以最坏情况状态总数为3^24,但实际上,我们可以分三种情况讨论,先确定中间的8个数字的值,假设为1的话,2和3就可以看成是一样的,于是状态数变成了2^24。
               对三种情况分别进行迭代加深搜索,令当前需要搜索的中间8个数字为k,首先枚举本次搜索的最大深度maxDepth(即需要的步数),从初始状态进行状态扩展,每次扩展8个结点,当搜索到深度为depth的时候,那么剩下可以移动的步数为maxDepth - depth,我们发现每次移动,中间的8个格子最多多一个k,所以如果当前状态下中间8个格子有sum个k,那么需要的剩余步数的理想最小值s = 8 - sum,那么估价函数:
               h = depth + (8 - sum)
               当h > maxDepth时,表明在当前这种状态下,不可能在maxDepth歩以内达成目标,直接回溯
               当某个深度maxDepth至少有一个可行解时,整个算法也就结束了,可以设定一个标记,直接回溯到最上层,或者在DFS的返回值给定,对于某个搜索树,只要该子树下有解就返回1,否则返回0。
               迭代加深适合深度不是很深,但是每次扩展的结点数很多的搜索问题。
    、广度优先搜索
          1、BFS
               1) 算法原理
                广度优先搜索即Breadth First Search,也是图遍历算法的一种。用一句话概括就是:“我会分身我怕谁?!”。
                BFS的具体算法描述为选择一个起始点v放入一个先进先出的队列中,执行如下操作:
                        a. 如果队列不为空,弹出一个队列首元素,记为当前结点执行b;否则算法结束;
                        b. 将与 当前结点 相邻并且尚未被访问的结点的信息进行更新,并且全部放入队列中,继续执行a;
                维护广搜的数据结构是队列和HASH,队列就是官方所说的open-close表,HASH主要是用来标记状态的,比如某个状态并不是一个整数,可能是一个字符串,就需要用字符串映射到一个整数,可以自己写个散列HASH表,不建议用STL的map,效率奇低。
                 广搜最基础的应用是用来求图的最短路。
                 如图9所示,对以下图进行广度优先搜索,假设起点为1,将它放入队列后。那么第一次从队列中弹出的一定是1,将和1相邻未被访问的结点继续按顺序放入队列中,分别是2、3、4、5、7,并且记录下它们距离起点的距离dis[x] = dis[1] + 1 (x 属于集合 {2, 3, 4, 5, 7});然后弹出的元素是2,和2相邻未被访问的结点是10,将它也放入队列中,记录dis[10] = dis[2] + 1;然后弹出5,放入6(4由于已经被访问过,所以不需要再放入队列中);弹出7,放入8、9。队列为空后结束搜索,搜索完毕后,dis数组就记录了起点1到各个点的最短距离;
    图9
             2) 算法实现
              广搜一般用队列维护状态,写成伪代码如下:
    def BFS(v):
        resetArray(visited,false)
        visited[v] = true
        queue.push(v)
        while not queue.empty():
            v = queue.getfront_and_pop()
            for u in adjcent_list[v]:
                if visited[u] is false:
                    dosomething(u)
                    queue.push(u)
               3) 基础应用
                   a. 最短路:
                       bellman-ford最短路的优化算法SPFA,主体是利用BFS实现的。
                       绝大部分四向、八向迷宫的最短路问题。
                   b. 拓扑排序:
                       首先找入度为0的点入队,弹出元素执行“减度”操作,继续将减完度后入度为0的点入队,循环操作,直到队列为空,经典BFS操作;
                   c. FloodFill:
                       经典洪水灌溉算法;
               4) 高级应用
                   a. 差分约束:
                       数形结合的经典算法,利用SPFA来求解不等式组。
                   b. 稳定婚姻:
                       二分图的稳定匹配问题,试问没有稳定的婚姻,如何有心思学习算法,所以一定要学好BFS啊;             
                   c. AC自动机:
                        字典树 + KMP + BFS,在设定失败指针的时候需要用到BFS。
                        详细算法参见:http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html
                   d. 矩阵二分:
                        矩阵乘法的状态转移图的构建可以采用BFS;
                   e. 基于k进制的状态压缩搜索:
                       这里的k一般为2的幂,状态压缩就是将原本多维的状态压缩到一个k进制的整数中,便于存储在一个一维数组中,往往可以大大地节省空间,又由于k为2的幂,所以状态转移可以采用位运算进行加速,HDU1813HDU3278以及HDU3900都是很好的例子;
                   f. 其它:
                       还有好多,一时间想不起来了,占坑;
          2、基于BFS的A*
               1) 算法原理
               在搜索的时候,结点信息要用堆(优先队列)维护大小,即能更快到达目标的结点优先弹出。
               2) 基础应用
                a.八数码问题
                    如图10所示,一个3*3的棋盘,放置8个棋子,编号1-8,给定任意一个初始状态,每次可以交换相邻两个棋子的位置,问最少经过多少次交换使棋盘有序。
     
    图10
             遇到搜索问题一般都是先分析状态,这题的状态数可以这么考虑:将数字1放在九个格子中的任意一个,那么数字2有八种摆放方式,3有七种,依此类推;所以状态总数为9的排列数,即9!(9的阶乘) = 362880。每个状态可以映射到0到362880-1的一个整数,
              对于广搜来说这个状态量不算大,但是也不小,如果遇到无解的情况,就会把所有状态搜遍,所以这里必须先将无解的情况进行特判,采用的是曼哈顿距离和逆序数进行剪枝,具体参见 SGU 139的解法:
              网上对A*的描述写的都很复杂,我尝试用我的理解简单描述一下,首先还是从公式入手:
              f(state) = g(state) + h(state)

             g(state)   表示从初始状态 到 state 的实际行走步数,这个是通过BFS进行实时记录的,是一个已知量;
              h(state)   表示从 state 到 目标状态 的期望步数,这个是一个估计值,不能准确得到,只能通过一些方法估计出一个值,并不准确;
              f(state)   表示从 初始状态 到 目标状态 的期望步数,这个没什么好说的,就是前两个数相加得到,也肯定是个估计值;
              
              对于广搜的状态,我们是用队列来维护的,所以state都是存在于队列中的,我们希望队列中状态的f(state)值是单调不降的(这样才能尽量早得搜到一个解),g(state)可以在状态扩展的时候由当前状态的父状态pstate的g(pstate)+1得到;那么问题就在于h(state),用什么来作为state的期望步数,这个对于每个问题都是不一样的,在八数码问题中,我们可以这样想:
              这个棋盘上每个有数字的格子都住了一位老爷爷 (-_-|||),每位老爷爷都想回家,老爷爷的家就对应了目标状态每个数字所在的位置,对于 i 号老爷爷,他要回家的话至少要走的路程为当前状态state它在的格子pos[i] 和 目标状态他的家target[i] 的曼哈顿距离。每位老爷爷都要回家,所以最少的回家距离就是所有的这些曼哈顿距离之和,这就是我们在state状态要到达目标状态的期望步数h(state),不理解请回到两行前再读一遍或者看下面的公式。
              h(state) = sum( abs(pos[i].x - (i-1)/3) + abs(pos[i].y - (i-1)%3) )  (其中 1 <= i <= 8,  0 <= pos[i].x, pos[i].y < 3 )
             最后附上原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1043
              b.K短路问题
              求初始结点到目标结点的第K短路,当K=1时,即最短路问题,K=2时,则为次短路问题,当K >= 3时需要A*求解。
              还是一个h(state)函数,这里可以采用state到目标结点的最短距离为期望距离;
              附上原题链接:http://poj.org/problem?id=2449
          3、双向广搜
               1) 算法原理
                初始状态 和 目标状态 都知道,求初始状态到目标状态的最短距离;
                利用两个队列,初始化时初始状态在1号队列里,目标状态在2号队列里,并且记录这两个状态的层次都为0,然后分别执行如下操作:
                        a.若1号队列已空,则结束搜索,否则从1号队列逐个弹出层次为K(K >= 0)的状态;
                                i.  如果该状态在2号队列扩展状态时已经扩展到过,那么最短距离为两个队列扩展状态的层次加和,结束搜索;
                                ii. 否则和BFS一样扩展状态,放入1号队列,直到队列首元素的层次为K+1时执行b;
                        b.若2号队列已空,则结束搜索,否则从2号队列逐个弹出层次为K(K >= 0)的状态;
                                i.  如果该状态在1号队列扩展状态时已经扩展到过,那么最短距离为两个队列扩展状态的层次加和,结束搜索;
                                ii. 否则和BFS一样扩展状态,放入2号队列,直到队列首元素的层次为K+1时执行a;
                 如图11,S表示初始状态,T表示目标状态,红色路径连接的点为S扩展出来的,蓝色路径连接的点为T扩展出来的,当S扩展到第三层的时候发现有一个结点已经在T扩展出来的集合中,于是搜索结束,最短距离等于3 + 2 = 5;
    图11
               双广的思想很简单,自己写上一两个基本上就能总结出固定套路了,和BFS一样属于盲搜。

    三、搜索题集整理
       1、DFS
       Red and Black              ★☆☆☆☆    FloodFill
          The Game                   ★☆☆☆☆    FloodFill
          Frogger                    ★☆☆☆☆    二分枚举答案 + FloodFill  
          Nearest Common Ancestors   ★☆☆☆☆    最近公共祖先 
          Robot Motion               ★☆☆☆☆    递归模拟
          Dessert                    ★☆☆☆☆    枚举
          Matrix                     ★☆☆☆☆    枚举
          Frame Stacking             ★☆☆☆☆    枚举
          Transportation             ★☆☆☆☆    枚举
          Pairs of Integers                    ☆☆☆    枚举
          方程的解数                                      ☆☆☆    枚举 + 散列HASH
          Maze                                             ☆☆☆    建完图后FloodFill
          Trees Made to Order                ☆☆☆    递归构造解
          Cycles of Lanes                        ☆☆☆    简单图最长环
          The Settlers of Catan           ☆☆☆    简单图最长链
          Parity game                                ☆☆☆    简单图判奇环(交错染色)
          Increasing Sequences              ☆☆☆    枚举
          Necklace Decomposition         ☆☆☆    枚举
          Rikka with Tree            ★★☆☆☆    统计
           Mahjong tree               ★★★☆☆    统计
          Machine Schedule                     ☆☆    二分图最大匹配
          Chessboard                                 ☆☆    棋盘覆盖问题
          Air Raid                                      ☆☆    DAG图 最小路径覆盖
          Entropy                                        ☆☆    枚举 + 适当剪枝
          Dropping the stones                ☆☆    枚举 + 适当剪枝
          Dreisam Equations                    ☆☆    表达式求值
          Firefighters                              ☆☆    表达式求值 
          Cartesian Tree                          ☆☆    笛卡尔树的构造
          Binary Stirling Numbers        ☆☆    分形
          Obfuscation                               ☆☆    字符串匹配
          Graph Coloring             ★★★☆    最大团
        Pusher                         ★★★     暴力搜索
          Self-Replicating Numbers          枚举
          Last Digits                                    DFS + 欧拉函数   
          Secret Code                                    实复数进制转化
          Anniversary Cake                         矩形填充
          A Puzzling Problem                      枚举摆放
          Vase collection                            图的完美匹配
          Packing Rectangles                      枚举摆放
          Missing Piece 2001                      N*N-1 数码问题,强剪枝

       2、IDA* (确定是迭代加深后就一个套路,枚举深度,然后 暴力搜索+强剪枝)
          Addition Chains                        ☆☆☆    
          DNA sequence               ★★☆☆☆    
          Booksort                                      ★☆☆    
          The Rotation Game          ★★★☆☆    迭代加深的公认经典题,理解“最少剩余步数”            
          Paint on a Wall            ★★★☆☆    The Rotation Game 的简单变形
          Escape from Tetris         ★★★★☆    
          Maze                       ★★★★☆ 
          Rubik 2×2×2                ★★★★★    编码麻烦的魔方题

       3、BFS
          Pushing Boxes              ★☆☆☆☆    经典广搜 - 推箱子
          Jugs                       ★☆☆☆☆    经典广搜 - 倒水问题
          Space Station Shielding    ★☆☆☆☆    FloodFill
          Knight Moves               ★☆☆☆☆    棋盘搜索
          Knight Moves               ★☆☆☆☆    棋盘搜索      
          Eight                      ★★☆☆☆    经典八数码
          Currency Exchange          ★★☆☆☆    SPFA
          The Postal Worker Rings    ★★☆☆☆    SPFA
          ROADS                      ★★☆☆☆    优先队列应用 
          Ones                       ★★☆☆☆    同余搜索
       Dogs                            ★★☆☆☆
       Lode Runner                     ★★☆☆☆
       Hike on a Graph                    ★★☆☆☆
          Find The Multiple          ★★☆☆☆    同余搜索
          Different Digits           ★★★☆☆    同余搜索
          Magic Multiplying Machine  ★★★☆☆    同余搜索
          Remainder                  ★★★☆☆    同余搜索
          Escape from Enemy Territory★★★☆☆    二分答案 + BFS
          Will Indiana Jones Get     ★★★☆☆    二分答案 + BFS
          Fast Food                  ★★★☆☆    SPFA
          Invitation Cards           ★★★☆☆    SPFA
          Galactic Import            ★★★☆☆    SPFA
          XYZZY                      ★★★☆☆    最长路判环
          Intervals                  ★★★☆☆    差分约束
          King                       ★★★☆☆    差分约束
          Integer Intervals          ★★★☆☆    差分约束
          Sightseeing trip           ★★★☆☆    无向图最小环
          N-Credible Mazes           ★★★☆☆    多维空间搜索,散列HASH
          Spreadsheet                ★★★☆☆    建立拓扑图后广搜
          Frogger                    ★★★☆☆    同余搜索
          Ministry                   ★★★☆☆    需要存路径
          Gap                        ★★★☆☆    A*
          Maze                       ★★★☆☆    二进制压缩钥匙的状态  
          Hike on a Graph            ★★★☆☆    
          All Discs Considered       ★★★☆☆
          Roads Scholar              ★★★☆☆    SPFA
          Holedox Moving             ★★★☆☆
          昂贵的聘礼                   ★★★☆☆
          Maze Stretching            ★★★☆☆
          Treasure of the Chimp      ★★★☆☆
          Is the Information Reliable★★★☆☆    最长路判环
          It's not a Bug, It's a     ★★★☆☆
       Warcraft                          ★★★☆☆
       Escape                                                      ★★★☆☆
          Bloxorz I                  ★★★☆☆    当年比较流行这个游戏
          Up and Down                        ★★★★☆    离散化 + BFS
          Sightseeing                ★★★★☆    SPFA
          Cliff Climbing             ★★★★☆    日本人的题就是这么长 
          Cheesy Chess               ★★★★☆    仔细看题
          The Treasure               ★★★★☆                        
          Chessman                   ★★★★★    弄清状态同余的概念
          Puzzle                     ★★★★★    几乎尝试了所有的搜索 -_-||| 让人欲仙欲死的题
          Unblock Me                 ★★★★★    8进制压缩状态,散列HASH,位运算加速

       4、双向BFS(适用于起始状态都给定的问题,一般一眼就能看出来,固定套路,很难有好的剪枝)
          Solitaire                  ★★★☆☆
          A Game on the Chessboard   ★★★☆☆
          魔板                        ★★★★☆
       Tobo or not Tobo               ★★★★☆
          Eight II                    ★★★★★

    展开全文
  • 搜索功能的实现

    万次阅读 2018-06-03 16:31:52
    搜索功能的实现效果图模块划分需要的

    搜索功能的实现

    效果图

    模块划分


    需要的我们自己写dao层mapper层

    dao层存在我们搜索的结果

    /**
     * 商品搜索dao
     */
    @Repository
    public class SearchDao {
        @Autowired
        private SolrServer solrServer;
    
        /**
         * 根据查询条件查询索引库
         * @param solrQuery
         * @return
         */
        public SearchResult search(SolrQuery solrQuery) throws SolrServerException {
            //根据solrQuery查询索引库
            QueryResponse query = solrServer.query(solrQuery);
            //取查询结果
            SolrDocumentList results = query.getResults();
            //取查询结果总记录数
            long numFound = results.getNumFound();
            //创建一个SearchResullt对象
            SearchResult searchResult=new SearchResult();
            searchResult.setRecordCount(numFound);
            //取商品列表,需要取高亮的显示
            Map<String, Map<String, List<String>>> highlighting = query.getHighlighting();
            //创建一个存储商品列表的集合
            List<SearchItem> itemList =new ArrayList<>();
            //遍历文档列表,从域中去内容取高亮中的需要的字段id必须要有
            for (SolrDocument document :results) {
                //创建一个SearchItem对象
                SearchItem searchItem=new SearchItem();
                //设置需要SearchItem对象的属性
                searchItem.setId((String) document.get("id"));
                searchItem.setCategory_name((String) document.get("item_category_name"));
                searchItem.setImage((String) document.get("item_image"));
                searchItem.setPrice((Long) document.get("item_price"));
                searchItem.setSell_point((String) document.get("item_sell_point"));
                //取高亮显示
                List<String> list = highlighting.get(document.get("id")).get("item_title");
                //创建一个title空字符串
                String title="";
                //判断title数据中是否有高度数据
                if (list !=null && list.size()>0){//有高亮数据
                    title=list.get(0);
                }else {//没有高亮数据就取文档中的数据
                    title= (String) document.get("item_title");
                }
                //将标题添加到searchItem对象中
                searchItem.setTitle(title);
                //添加到商品列表
                itemList.add(searchItem);
            }
            //添加商品列表到SearchResullt对象
            searchResult.setItemList(itemList);
            //返回结果
            return searchResult;
        }
    }
    

    Itemmapper.xml配置

    <?xml version="1.0" encoding="UTF-8" ?>
    <!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd" >
    <mapper namespace="com.e3mall.search.mapper.ItemMapper">
        <!--查询商品信息-->
        <select id="getItemList" resultType="com.e3mall.common.pojo.SearchItem">
          SELECT
            a.id,
            a.title,
            a.sell_point,
            a.price,
            a.image,
            b.name category_name
          FROM
             tb_item a
           LEFT JOIN tb_item_cat b
          on a.cid=b.id
           WHERE a.status=1;
        </select>
        <!--通过id查询SearchItem pojo中的属性数据-->
        <select id="getItemById" resultType="com.e3mall.common.pojo.SearchItem" parameterType="long">
          SELECT
            a.id,
            a.title,
            a.sell_point,
            a.price,
            a.image,
            b.name category_name
          FROM
             tb_item a
           LEFT JOIN tb_item_cat b
          on a.cid=b.id
           WHERE a.status=1 and a.id=#{itemId};
        </select>
    
    </mapper>

    依照我红色的字体写对应ItemMapper接口类即可附图依照


    SearchItemServiceImpl.java

    /**
     * 商品数据索引库Service
     */
    @Service
    public class SearchItemServiceImpl implements SearchItemService {
        @Autowired
        private ItemMapper itemMapper;
        @Autowired
        private SolrServer solrServer;
        /**
         * 将删商品数据导入索引库
         * @return
         */
        @Override
        public E3Result importItems() {
            try {
            //查询商品列表
            List<SearchItem> itemList = itemMapper.getItemList();
            //导入到索引库
            for (SearchItem item :itemList) {
                //创建文档对象
                SolrInputDocument document=new SolrInputDocument();
                //向文档添加域
                document.addField("id",item.getId());
                document.addField("item_title",item.getTitle());
                document.addField("item_sell_point",item.getSell_point());
                document.addField("item_price",item.getPrice());
                document.addField("item_image",item.getImage());
                document.addField("item_category_name",item.getCategory_name());
                //写入索引库
                solrServer.add(document);
            }
            //提交
            solrServer.commit();
            //返回成功
            return E3Result.ok();
            }catch (Exception e){
                e.printStackTrace();
                return E3Result.build(500,"商品导入失败!");
            }
        }
    }

    applicationContent-service.xml配置

    代码

    <dubbo:service interface="com.e3mall.search.service.SearchItemService" ref="searchItemServiceImpl" timeout="600000"/>

    表现层

    /**
     * 商品搜索Controller
     */
    @Controller
    public class SearchController {
    
        @Autowired
        private SearchService searchService;
    
        @Value("${SEACHER_RESULT_ROWS}")
        private Integer SEACHER_RESULT_ROWS;
        /**
         * 分页查询功能
         * @param keyword 查询添加
         * @param page 结果从第几条记录开始显示这里我们设置了默认值1
         * @param model
         * @return
         */
        @RequestMapping("/search")
        public  String search(String keyword, @RequestParam(defaultValue = "1") Integer page, Model model) throws Exception {
            keyword=new String(keyword.getBytes("ISO-8859-1"),"utf-8");
            //调用服务查询商品列表
            SearchResult result = searchService.search(keyword, page, SEACHER_RESULT_ROWS);
            //把结果传递给页面
            model.addAttribute("query",keyword);
            model.addAttribute("totalPages",result.getTotalPages());
            model.addAttribute("page",page);
            model.addAttribute("recourdCount",result.getRecordCount());
            model.addAttribute("itemList",result.getItemList());
            //返回逻辑页面
            return "search";
        }
    }

    springmvc.xml引入服务

    <!-- 引用dubbo服务 -->
    <dubbo:application name="e3-manager-web"/>
    <dubbo:registry protocol="zookeeper" address="192.168.25.128:2181"/>
    <!--调用搜索服务-->
    <dubbo:reference interface="com.e3mall.search.service.SearchService" id="searchService" />

    展开全文
  • 搜索方法汇总

    千次阅读 2018-09-09 10:39:18
    搜索方法汇总 今天呢?心血来潮给大家分享一个,我平时用的到的搜索小技巧,我总结了下,如下: 1.网站搜索 关键词+空格+site:网站名 例子:悬疑电影推荐 site:douban.con 2.格式搜索 关键词+空格+filetype:+...

    搜索方法汇总

    今天呢?心血来潮给大家分享一个,我平时用的到的搜索小技巧,我总结了下,如下:


    1.网站搜索
    关键词+空格+site:网站名
    例子:悬疑电影推荐 site:douban.con

    2.格式搜索
    关键词+空格+filetype:+格式名后缀
    例子:征服filetype:mp3

    3.排除式搜索
    关键词+空格+减号+排除的关键词
    例子:悬疑电影推荐 -国产

    4.精准搜索
    “关键词”
    例子:“悬疑电影推荐”

    5.排除式的精准搜索
    intitle:+“关键词”
    例子:intitle:“国产”

    注意事项:以上英文字母、符号,均为英文键盘

    搜索思想
    1.关键词提炼 自上而下的思维方式
    2.找寻定点 专业的搜索源

    展开全文
  • 腾讯面试题: 百度搜索为什么那么快?

    万次阅读 多人点赞 2020-05-07 19:17:06
    我还记得去年面腾讯时,面试官最后一个问题是:百度/google的搜索为什么那么快? 这个问题我懵了,我从来没想过,搜素引擎的原理是什么 然后我回答:百度爬取了各个网站的信息,然后进行排序,当输入关键词的时候...

    我还记得去年面腾讯时,面试官最后轻飘飘的问:百度/google的搜索为什么那么快?

    这个问题我懵了,我从来没想过,搜索引擎的原理是什么

    然后我整整思考了2000ms,回答:百度爬取了各个网站的信息,然后进行排序,当输入关键词的时候进行文档比对……巴拉巴拉

    面试官:这不是我想要的答案

    我内心
    在这里插入图片描述


    这个问题我一直耿耿于怀,终于今天,我把他写出来,以后再问,我直接把这篇文章甩给他!!!

    两个字:倒排,将贯穿整篇文章,也是面试官想要的答案

    首先我们知道,百度肯定是有爬虫,到处爬取网页,进行某种处理。然后通过你输入的关键词进行某种计算再返回给你的

    我们先来看看什么是某种处理

    某种处理

    当百度爬取了海量网页后,每一个网页我们称为”文档“,不可能就杂乱无章的放着,它使用了文档集合,就是类似的文档放在一个集合中

    那什么样的文档算类似呢?相信你猜到了,文档中有相同关键字的就可以放在一个集合中

    来举例说明

    假设全世界只有下面5个文档(网页),文档内容也很简单,就一句话(注意是文档内容,不是标题)

    image-20200507163757569

    百度爬取后,将他们进行编号,然后对文档进行扫描分词,因为百度内部有词库,匹配上的词将被切分,所以文档1号将被切分为【谷歌,地图,之父,跳槽,FaceBook】,后面的文档也一样,然后对切分出来的单词进行倒排处理,形成倒排列表

    image-20200507164140174

    啥是倒排处理?右边这堆杂乱无章的数字咋来的?别急,仔细看,1号单词“谷歌”是不是在1,2,3,4,5号文档都出现过?9号单词“离开”是不是只在3号文档出现过?

    是的,倒排列表所做的,就是保存对应单词所出现过的文档编号

    我想你开始明白他的目的了,当我们搜索“谷歌”的时候,他就会获得“谷歌”这一单词对应的倒排列表,知道哪些文档包含他,然后将这些文档提取出来返回给你,这就是一种单词映射文档的方法

    但是,没那么简单,因为只有这样的话,我在一篇博客上把所有的单词都写上,这样杂乱无章的文章岂不是要被推荐给全体中国人???

    所以倒排列表还要保存下列信息

    image-20200507164836182

    保留的信息变成了二元组,比如16号单词“网站”的(5:1),5表示出现的文档编号,1表示出现的次数,也就是说,有了这个信息,如果一个单词在文档中频率越高(英文缩写TF),搜索引擎就可以把他排在前面推给你

    除了频率,还有位置,比如”谷歌“就是在1号文档中出现了一次的单词,位置在第一个,用<1>表示

    image-20200507165150616

    可能到这你有点记不住有哪些网页了,再看一遍比对下

    image-20200507163757569

    这样子,搜素引擎就可以根据你的关键词在倒排列表中找到含有这个关键词的文档集合,然后根据关键词在文档集合中各个文档出现的频率和位置综合判断返回给你排序后的文档

    上句话比较长,加粗部分连在一起读意思不变

    实际上很多搜索引擎基本就是这样做的,只不过各家还有别的参考标准,比如百度还会参考热度,你的搜索记录,还有网站给的钱(你懂的)等等综合打分,按评分高低返回搜索结果的排序

    上面的所以记录处理好后都会存放在磁盘中,然后等你关键词来后再调入内存


    假设世界上只有5个文档,那么上面的东西完全够了,但实际上,世界上有亿万个文档,此时,问题的性质已经变了,不是找不找得到的问题,而是怎么找更快,更准的问题,这需要算法,也就是我们上面提到的某种计算

    某种计算

    第一个问题就是,词库那么多,当你输入“苹果”的时候,百度如何将你的关键词和他内部倒排列表的“苹果”一词联系起来?

    计算机是不认识“苹果”的,这里,可以通过哈希的方法将“苹果”转换为一个编号

    所谓哈希,即是将一个词通过某种算法映射为一个符号,比如“将单词转换为其长度”就是一种算法,虽然很low,这样“苹果”就是2,“梨”就是1,不同的哈希算法有不同的转换结果,但是必然会有一个东西——哈希冲突,比如“桃子”也是2,此时,需要使用链表,也称冲突表,将编号相同的单词链在一起

    image-20200507170500512

    当我们搜索“苹果”的时候,经过哈希计算,得知其编号为2,然后发现2中有一个链表,里面可能保存着“苹果”,”桃子”,“蘑菇”等,然后再遍历链表找到苹果即可

    这里和java8中的hashmap思想一致,不过链表也会过长,所以可以使用别的数据结构代替,比如红黑树,b树等

    解决了第一个问题,我们就可以通过关键词获得他的Id,然后得到所建立的倒排列表了,比如“谷歌

    image-20200507171253060

    第二个问题,由于文档的数量庞大,我们获取的文档往往编号位数都很多,而不像上图那样1,2,3,4,5,导致倒排列表无谓的扩大,所以我们这里进行作差

    在这里插入图片描述

    就是后面的文档编号减去前面的,在取文档(从磁盘中读取)的时候加回来即可

    第三个问题,如何从磁盘中读取文档

    现在我们已经有了倒排列表

    在这里插入图片描述

    可以有两种方法从磁盘中读取文档

    两次遍历法

    第一遍,扫描文档集合,找到文档数量N, 文档集合内所包含的不同单词数M,和每个单词出现的频率DF(如下图),以及一些别的必要信息,这些东西所占内存加起来,得到需要开辟的内存空间,

    在这里插入图片描述

    同时这个空间是以单词为单位划分,比如“谷歌”一词有5篇文档,

    1. 第一遍主要就是确定要开辟多大的内存空间来显示文档

    2. 第二遍扫描,就是边扫描,匹配对应的文档编号(三元组中的第一个数),载入内存

    但是这个方法有一个问题,那就是文档集合有多大,内存就有多大,所以,很可能内存会溢出,不过都放在内存中速度也很快,这是一种空间换时间的方法

    相信你发现了,但凡涉及到读取,一定有两种以上的方法,空间优先或是时间优先,第二种就是时间换空间——排序法

    排序法

    现在我们只用固定大小的内存,如何从上图中的倒排列表得知每个单词对应的文章集合所需要的内存空间有多少呢?

    我们需要解析文档,构造(单词ID,文档ID,单词频率)三元组,然后进行排序,按单词ID,文档ID,单词频率先后排,最后如果规定的内存满了,就将这些三元组通通写入一个临时文件A中

    在这里插入图片描述

    为什么要这样呢?想想看,如果我们最后拿到了一个(单词A,文档A,单词频率),我们就可以很轻松的知道一个单词对应哪个文档,和对应的频率,

    也就是一个三元组告诉我们单词A对应的文档A,另一个三元组告诉我们单词A对应文档B……,这些三元组加起来我们就知道了单词A对应的文档集合,就可以知道他需要多少内存空间来填补这些文档了

    可能解析50个文档后规定的内存就满了,然后把这些三元组们写入磁盘临时文件A,就可以再读下一篇50个文档了,注意,词典是不断增加的,比如前50个文档只有上面7个单词,后50个文档可能出现了别的单词,此时要插入词典中,词典一直在内存

    这样,只用固定大小的内存就可以50一批的解析完所有文档,写入了一个个的临时文件A,B,C,D,再将这些临时文件合并,就是把他们分别读入内存中的缓冲区,合成最终索引后再写入磁盘,这样通过最终索引就知道有哪些单词对应多少文档,还有频率,然后根据这些开辟内存空间读取进入内存返回给你即可

    image-20200507181036502

    排序法叙述起来比较复杂,但是其实理解起来很简单,耐心读一定能懂哦

    限于篇幅,这里只讲了你输入关键词到他返回给你大致的网页的过程,其实,百度如何爬取网页?如何保证网页的时效性?如何筛选垃圾网站?如何分布式存储海量网页?如何应对超长关键字查询?如何根据用户历史记录精准分析用户意图?
    等等都需要大量的篇幅详解,一篇文章不可能讲完,下次有机会再分析吧

    作者简介 :【小松漫步】,微信公众号同名,喜欢读书和收集书,文章参考自《这就是搜索引擎核心技术详解》,关注公众号回复【搜索引擎】,即可获取资源,一起交流学习吧

    展开全文
  • 各大磁力种子搜索引擎对比

    万次阅读 2018-12-04 10:45:55
    现在磁力种子搜索引擎质量参差不齐,现在就重点整理几个常用的种子搜索站,做个对比分析 1.屌丝搜-最懂屌丝的BT搜索引擎(www.diaosisou.com) 号称最懂屌丝的BT搜索引擎,确实名副其实,屌丝搜索功能强大。其种子...
  • 搜索引擎

    2020-03-22 10:25:25
    本篇博客总结一些常用的搜索引擎 1.谷歌 谷歌搜索在全球的占比最高,当然在国内是不能使用的 2.百度 全球最大的中文搜索引擎及最大的中文网站 3.搜搜 搜搜是腾讯旗下的搜索网站,是腾讯主要的业务单元之一。网站于...
  • 搜索

    2020-10-29 00:31:35
    搜索 基本概念 搜索(search)是各种数据结构中的一种常见运算. 搜索是在给定的数据集合中,寻找符合特定条件的数据,用来搜索的这个特定条件称之为键值. 按数据集合所含数据量的大小来分,搜索可分内部搜索和外部搜索. ...
  • 几款磁力搜索引擎,找资料更方便

    万次阅读 2018-02-28 17:37:00
    一款强大的磁力搜索引擎网站,这款网站包含有7万多个磁力链接,提供提供网盘形式和磁力形式的储存,有很多你想要的东西。如果是音频和视频的话支持在线观看。 Bt977 磁力搜索引擎,支持网盘播放,磁力下载。 ...
  • 原标题:在 Windows 10 上高效搜文件,自带搜索功能其实就够了 快速搜索和效率启动,是大多数用户的刚需,为此也诞生了一大波启动器应用,如 macOS 平台的Alfred、LaunchBar,Windows 平台的Wox、Listary等。其实...
  • 制作“搜索页面”

    2020-09-15 09:46:20
    制作“搜索页面”part11. 打开VSCode,在自己的文件夹中新建网页文件,文件名05baidu.html,输入 "!",按Tab键自动生成H5网页框架标签。2. 将title标签内容改为“搜索页面”,在内添加文字素材,分别设置标签和...
  • Google的一个代理网站: 仅限技术搜索,不要输入账户密码https://www.osjapan.nethttps://ipv6.google-api.ac.cn 转载于:https://blog.51cto.com/moerjinrong/2365704
  • python 手把手教你基于搜索引擎实现文章查重

    万次阅读 多人点赞 2020-09-13 22:18:19
    本文使用搜索引擎结果作为文章库,再与本地或互联网上数据做相似度对比,实现文章查重;由于查重的实现过程与一般情况下的微博情感分析实现流程相似,从而轻易的扩展出情感分析功能(下一篇将在此篇代码的基础上完成...
  • 在线识图搜索引擎

    万次阅读 2017-07-30 17:18:06
    Google 图片 https://images.google.com.hk/?gws_rd=cr 百度识图, “鉴”你所见 image.baidu.com/ TinEye Reverse Image Search 专业识图搜索引擎 搜狗图片-上网从搜狗开始10个识图网站
  • 2019搜索BT种子搜索引擎推荐大全

    万次阅读 2019-11-29 13:34:13
    原文链接:... 有时候换一个地方想找最新电影或者动漫,浏览器收藏的网址,想要查看还要去下载这个浏览器才行,这样就比较麻烦,看见简书可以记录,先搜集几个方便以后用,有需求...
  • 爬虫搜索,简单的搜索引擎,java爬虫,搜索引擎例子,爬虫demo,java实现互联网内容抓取,搜索引擎大揭密.java爬虫程序。web搜索。爬虫程序。sigar搜索,定时搜索互联网内容信息。
  • 搜索引擎技术之概要预览

    万次阅读 多人点赞 2011-09-27 20:04:45
    搜索引擎技术之概要预览前言 近些天在学校静心复习功课与梳理思路(找工作的事情暂缓),趁闲暇之际,常看有关搜索引擎相关技术类的文章,接触到不少此前未曾触碰到的诸多概念与技术,如爬虫,网页抓取,分词,索引...
  • 99%的人不知道搜索引擎的6个技巧

    万次阅读 多人点赞 2019-11-27 00:55:22
    加“星标★”,每天11.50,好文必达 全文约900字,预计阅读时间1分钟 ...搜索引擎一般都会有一些高级的搜索技巧,掌握这些技巧之后就可以过滤掉一些不想要的噪音,迅速找带自己想要的信息,只是很少...
  • 大数据平台下的各种搜索引擎的API

    万次阅读 2019-03-02 17:49:42
    首先,我做了一个网站,这个网站是基于电视剧、电影、app、图片、...用户可以通过首页的所有链接和搜索框进行分类检索。 具体的api如下: (1)查询百度云网盘的数据api https://ljxwtl.cn/getSearchPagingBaiduY...
  • 搜索引擎和知识图谱那些事

    万次阅读 2017-09-15 17:41:25
    搜索引擎和知识图谱那些事 分类: 知识图谱(14) 版权声明:本文为博主原创文章,转载请注明CSDN博客源地址!共同学习,一起进步~ 目录(?)[+] 这是一篇基础性文章,主要介绍搜索引擎和知识图谱的一些原理...
  • Lucene搜索引擎-搜索

    千次阅读 2018-10-29 22:28:04
    文章目录 如果对Lucene不熟悉的,请移步:Lucene搜索引擎-分词器
  • 搜索引擎介绍

    千次阅读 2017-02-06 11:41:51
    自从1994年问世以来,搜索引擎逐渐成为了人们获取Internet信息资源的主要方式,相关搜索引擎网站也逐渐成为Web用户使用Internet时的首选访问站点之一,另外搜索引擎和实时通讯、电子邮件等服务已经成为当今各大门户...
  • 详解搜索引擎的高级搜索语法指令

    万次阅读 2018-12-18 21:49:20
    搜索引擎是SEO最常用到的工具,也是程序员最得力的助手。用好搜索引擎是每个程序员的必修课,这里介绍一些常用的搜索引擎高级搜索语法指令。 1、site: site:是SEO最熟悉的高级搜索指令(例如:site:...
  • 搜索引擎原理

    千次阅读 2014-04-30 10:42:30
    搜索引擎技术之概要预览 前言  近些天在学校静心复习功课与梳理思路(找工作的事情暂缓),趁闲暇之际,常看有关搜索引擎相关技术类的文章,接触到不少此前未曾触碰到的诸多概念与技术,如爬虫,网页...
  • 本文来源于:http://www.java3z.com/cwbwebhome/article/article5/51093.html<br />  在做商务E流量分析的时候,需要实现一个功能:如果访客是通过搜索引擎的搜索找到客户网站的,要统计出访客是通过...
  • 几个好用搜索福利网站

    万次阅读 2019-04-06 13:43:24
    1.http://www.w3school.com.cn/ w3school,很好的在线web学习网站,免费 2.... sklearn文档,虽然是文档,但能学到很多很多具体的机器学习例子和知识 ... 菜鸟教程,也是在线学习网站,免费 ...
  • 一、搜索引擎篇-揭开es神秘的面纱

    万次阅读 2020-05-03 23:45:15
    一、为什么需要搜索引擎? 数据库适合结构化数据的精确查询,而不适合半结构化、 非结构化数据的模糊查询及灵活搜索(特别是数据量大时),无法提供想要的实时性。 结构化数据:用表、字段表示的数据 半结构化...
  • 开源搜索引擎 种子搜索 很久以前,互联网很小,只有几个人可以将它们编入索引,这些人收集了所有网站的名称和位置,并按页面或印刷书籍中的主题列出了它们。 随着万维网网络的发展,“网络响动”惯例得到了发展,在...
  • 搜索引擎索引之索引基础

    万次阅读 多人点赞 2012-02-13 22:00:10
    本文节选自《这就是搜索引擎:核心技术详解》第三章  本节通过引入简单实例,介绍与搜索引擎索引有关的一些基础概念,了解这些基础概念对于后续深入了解索引的工作机制非常重要。   3.1.1单词—文档矩阵 ...
  • 海量数据搜索——搜索引擎

    千次阅读 2018-11-14 17:57:12
    那么百度是如何在海里数据中找到自己需要的数据呢,为什么他搜索的速度如此之快,我们都知道是因为百度的搜索引擎,那么搜索引擎到底是个什么东西呢?可能有的程序员会想到es,但是并不能代表搜索引擎,它只是其中的...
  • 正文一:Full Text Search Engines vs. DBMS 发表于2009年 ...不知道大家有没有想过一个问题:数据库服务也支持全文搜索,但我们为什么要用全文搜索引擎! 如果说是全文搜索引擎更快或者性能更好,那为什么呢?我们

空空如也

1 2 3 4 5 ... 20
收藏数 2,725,095
精华内容 1,090,038
关键字:

搜索