·1.2.1_当一切充满不可知的时候，我们都是盲目的。

      尽管一切皆不可知，但我们并不能丧失面对未知的勇气，所以让我们勇敢且骄傲地探索这未知的一切吧。

---

1，2，3这三个数的全排列是显而易得的：123，132，213，231，312，321

即使是在程序中也是如此，我们只需要用三个for循环嵌套就能完成此全排列。

但如果是9个数的全排列呢？

我猜有一些读者或许会想到，那用9个for循环嵌套就可以辣~。

诶，虽然您是对的，但我不敢苟同，毕竟这太蠢了。

而且，如果是N个数的全排列就没辙了啊，毕竟您不能N个for循环嵌套。

（此处忽略一些奇奇怪怪的方法！这是正经的算法入门教程啊！！！亲）

所以，我们要用一个方法，叫盲目搜索法。它到底有多盲目呢？就像明知道是错的，仍然去爱的爱情那么盲目吧，这只是举例子哇。

盲目搜索法旗下有很多方法，但此文中会也仅会提到两种。

        ①深度优先搜索。简称dfs。

啊哈算法这本书中是这样形容的，不撞南墙不回头。嗯，这很盲目，很像爱情，或者梦想。这个东西通常用递归或者栈来实现。

        ②广度优先搜索。简称bfs。

这个算法符合就近原则，大概是一只吃窝边草的兔子吧。实现的话，通常得借助队列。

盲目搜索可以让程序对前途未卜的情况下，去进行搜索，他会把所有可能情况都枚举一遍。

·1.2.2_关于递归。

       无论各位学过或者没学过递归，我都建议认真看一次。因为这很简洁，除了我个人的经验积累，没有其他任何东西。

---

      什么是递归？在程序当中，递归通常指函数或者方法在函数体内调用其自身。

      在写递归时，你必须思考的是什么？

                     ①确定递归状态转移。

                     ②确定递归边界。

例子，

void recursion(Object object){

    if( isBoundary(object) ){   //判断是否为递归边界。

             //do something 

     }else{

           //递归状态转移

          object = transfer_state_function(object);

          recursion(object);

    }

}

引申：深度优先搜索能通过栈来实现的原因是，高级语言中，递归是通过函数栈来实现的，我们能通过栈来模拟函数栈的行为从而实现递归，对此有兴趣的读者可以自行尝试。

---

·1.2.3_深度优先搜索。

之前提到了深度优先搜索是由递归实现的，那我们该如何借助递归去搜索呢？

在有一颗二叉树，深度优先搜索可以类比为后序遍历。

即，遍历顺序4，7，8，5，2，6，9，10，3，1

此时，边界为 是否拥有子节点。状态转移为不同节点的转移。

实现例子：  假设Node为树中的节点，haveSon()能判断是否具有子节点，haveLeftSon()是否具有左节点，haveRightSon()同理。

void dfs(Node node){

       if( !node.haveSon() ){ //搜索边界

       }else{    //节点转移。偏好为 先选左子树

               if( node.haveLeftSon() ) dfs(node.leftSon);

               if( node.haveRightSon() ) dfs(node.rightSon);

      }

}

也例如我们要实现N个元素的全排列，且N个元素分别为1，2，3，4，……N-1，N。

先选一个，然后有N种选法，再选一个，有N-1种选法，如此类推，则可得所有可能的情况为 N! 种。

设第一种为 123456.....N，（即假设该算法的偏好为先选较小）

则代码实现：

假设 

一，存在数组choice 且下标为 i 时记录了当前第i个元素的选择的数。如第一种被输出时，数组为 [1,2,3,4,5,6,....,N]

二，存在数组 is_arr_beChoiced 且下标为 i 时记录了当前数 i 是否被选择。

void dfs(int index){

      if(index == N){

              //输出 choice数组中选择的数。

      }else{//搜索状态转移

            for(int i = 1 ; i<=N ; i++){

               if( !is_arr_beChoiced[i] ){

                   is_arr_beChoiced[i] = true;choice[index] = i;

                   dfs(index+1);

                    is_arr_beChoiced[i] = false;

              }

          }

     }

}

如果你看懂了上面的两个例子，那我们来总结一下深度优先搜索的特点。

①无论如何，总需要有一个初始状态。开始搜索的时候的状态成为搜索状态，例如，第一个例子的根节点时的状态。

②搜索的过程中伴随着状态的转换。

③一定有搜索边界。

④他坚持着某种偏好。这或许就是他的梦想了吧。

....关于深度优先搜索还未完，诸君晚安，以后见。2017.1.17.4:42..