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

    万次阅读 多人点赞 2017-12-28 14:44:38
    搜索入门:深度优先搜索(记忆化、剪枝、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.找寻定点 专业的搜索源

    展开全文
  • 搜索引擎推荐

    千次阅读 2019-04-20 23:58:51
    ​关于搜索,日常使用的非常多,今天来推荐几个搜索引擎。 分为两类,一类是比较小众的搜索引擎,但是用起来也很给力,第二类是谷歌镜像,第三类是搜索引擎导航,有很多搜索引擎,可以快速切换,用起来很方便。 ...

    ​关于搜索,日常使用的非常多,今天来推荐几个搜索引擎。

    分为两类,一类是比较小众的搜索引擎,但是用起来也很给力,第二类是谷歌镜像,第三类是搜索引擎导航,有很多搜索引擎,可以快速切换,用起来很方便。

    小众的搜索引擎

    虽说是小众的搜索引擎,但是用起来也很不错。每一个我都用过一段时间,搜索结果应该都比百度好一些吧。

    1.小众搜索引擎 http://www.caup.cn/[1]

     

    对的,这个搜索引擎就叫小众搜索引擎。这个搜索结果和谷歌很类似,不完全一样,做了一些整合。如果你是做技术的,但是又不能访问谷歌,或者有时候没有条件,或者懒得折腾,可以用这款搜索引擎,因为这个搜索引擎有一个特性,就是技术类的他会在stackoverflow搜索出结果,然后放在外面,不用点进去链接,直接得到结果。

    举个例子,可能不是很恰当:

     

    22.

    https://www.ecosia.org/[2]

    不知道叫什么名字。总之用着还不错,没有深入研究过。

    33.

    MEZW搜索 https://so.mezw.com/[3]

     

     

     

    搜索导航

    搜索导航类的网站,其实也挺多。但是这里只分享一个,足以碾压其他的导航类,因为种类齐全,而且还体验还不错。

    •虫部落导航 https://search.chongbuluo.com/[4]

     

     

    镜像类搜索

    1.

    全渠道搜索 http://dir.scmor.com/[5]

    推荐这个是因为这个是很稳定的镜像,准确的来说是一个镜像组,一个不行,就另一个,还是比较好用的。后台是有五六个镜像的。

    2 2.

    谷歌搜索镜像 http://ac.scmor.com/[6]

    3 3.

    hiqq搜索 http://nav.hiqq.com.cn/twy/[7]

     

     

     

    其实还有几个图书类和网盘类的搜索引擎,但是估计用的人比较少,就不分享了,如果有人需要,留言说明,下次分享。

    References

    [1]http://www.caup.cn/
    [2]https://www.ecosia.org/
    [3]https://so.mezw.com/
    [4]https://search.chongbuluo.com/
    [5]http://dir.scmor.com/
    [6]http://ac.scmor.com/
    [7]http://nav.hiqq.com.cn/twy/

     

    如果觉得写得不错,欢迎关注我的微信公众号

    展开全文
  • 各种搜索引擎

    万次阅读 2018-07-23 16:41:17
    https://sg.search.yahoo.com/ (雅虎) https://www.bing.com/(必应... ... https://bird.so/ (小众搜索) https://search.avira.com/#/ https://suche.gmx.net/web  (德国) https://r0.ru/ (俄国) https...
  • 商品搜索引擎---推荐系统设计

    万次阅读 多人点赞 2016-04-11 10:59:16
    一、前言结合目前已存在的商品推荐设计(如淘宝、京东等),推荐系统主要包含系统推荐和个性化推荐两个模块。系统推荐: 根据大众行为的推荐引擎,对每个用户都给出同样的推荐,这些推荐可以是静态的由系统管理员...
  • 前沿 文章目录前沿开源地址[算法学习资料: AI_Tutorial](https://github.com/cbamls/AI_Tutorial)开源相关LuceneSolrElasticLucidWorks中文...算法学习资料: AI_Tutorial 人工智能、AI架构、搜索系统、推荐系统...
  • 为什么80%的码农都做不了架构师?>>> ...
  • 在回答这个问题的时候, 想到了近几年在做搜索推荐系统的过程中, 学术界和工业界的一些区别。 正好最近正在做技术规划, 于是写偏文章说下工业界完整推荐系统的设计。结论是:&amp;nbsp;没有某种算法能够完全...
  • 几款磁力搜索引擎,找资料更方便

    万次阅读 2019-06-26 15:54:54
    一款强大的磁力搜索引擎网站,这款网站包含有7万多个磁力链接,提供提供网盘形式和磁力形式的储存,有很多你想要的东西。如果是音频和视频的话支持在线观看。 Bt977 磁力搜索引擎,支持网盘播放,磁力下载。 ...
  • Google的一个代理网站: 仅限技术搜索,不要输入账户密码https://www.osjapan.nethttps://ipv6.google-api.ac.cn 转载于:https://blog.51cto.com/moerjinrong/2365704
  • 制作“搜索页面”

    2020-09-17 14:42:00
    制作“搜索页面”part11. 打开VSCode,在自己的文件夹中新建网页文件,文件名05baidu.html,输入 "!",按Tab键自动生成H5网页框架标签。2. 将title标签内容改为“搜索页面”,在内添加文字素材,分别设置标签和...
  • 几个好用搜索福利网站

    万次阅读 2020-01-26 19:03:34
    1.http://www.w3school.com.cn/ w3school,很好的在线web学习网站,免费 2.... sklearn文档,虽然是文档,但能学到很多很多具体的机器学习例子和知识 ... 菜鸟教程,也是在线学习网站,免费 ...
  • 超级搜索(Super search)

    万次阅读 2016-03-14 16:18:23
    现在的搜索引擎会极大的帮助用户搜索到想要的搜索的内容,我们常用的搜索引擎包括百度、搜狗、360搜索等等,今天就为大家推荐一个超级搜索的插件。超级搜索基于浏览器的全面搜索。智能识别搜索关键字,集成收藏夹...
  • Eclipse全局搜索

    万次阅读 多人点赞 2014-08-20 17:33:41
    Eclipse中全局搜索和更替  Eclipse全局搜索步骤  使用快捷键“ctrl+H”打开文件搜索对话框,选择“File Search”标签,在Containing text中输入你需要搜索的字符串,在Scope中,选择你要搜索...
  • 今天突然出现的问题,在状态栏左下角的搜索搜索OneNote没有任何反应,对,就是这个地方。 最后在另一篇博客上找到了答案,那篇博客也是在知乎找到的答案,虽然是用被人的方法解决了问题,但我还是打算记下来; 1...
  • Win10搜索的快捷键: win+Q 空格键左边的键+Q
  • 使用Google搜索引擎的10个搜索技巧

    万次阅读 多人点赞 2018-02-11 20:51:36
    有很多时候,在使用搜索引擎的时候, 搜索结果并不如人意, 下边我介绍几个搜索的小技巧 准确搜索 简单有效的方法就是在关键词上加上双引号, 这样搜索引擎只会返回和关键词完全吻合的搜索结果. 在不加双引号的...
  • 推荐一些非常好用的网盘搜索神器

    万次阅读 2018-09-12 11:35:59
    而今天推荐的就是一些网盘搜索引擎,它可以使我们快速搜搜索到自己想要的资源,从而提高了整体的搜索效率。下面将介绍一些搜索引擎,可以根据自己的情况选择适合自己的搜索神器。 盘多多 ...
  • 一个简单的站内搜索引擎的实现

    万次阅读 多人点赞 2020-06-17 09:00:22
    这学期的信息检索课程的实验要求做一个简单的站内搜索引擎,用来搜索山东大学新闻网(http://www.view.sdu.edu.cn/)的新闻内容。具体要求如下: 今天终于考完了这学期的最后一门计算机图形学的考试,现在有时间...
1 2 3 4 5 ... 20
收藏数 2,614,818
精华内容 1,045,927
关键字:

搜索