My Blogs
Posts tagged with "算法"
朴素贝叶斯从放弃到入门
Published 2017年09月10日 23:00 by james
理论基础
联合概率
联合概率表示两个事件共同发生的概率。A与B的联合概率表示为$P(AB)$，$P(A,B)$或者$P(A \bigcap B)$。
联合概率可以推广到任意又穷多个事件出现的情况，设（$A_1,A_2,\cdots,A_n$）为任意n个事件（$n\ge2$），事件$A_1,A_2,\cdots,A_n$共同发生的概率记为$P(A_1A_2 \dots A_n)$，$P(A_1,A_2,\dots,A_n)$或者$P(A_1 \bigcap A_2 \bigcap \dots \bigcap A_n)$
条件概率
设A，B 是两个事件，且$P(A) > 0$，则称$P(B|A) = \frac{P(AB)}{P(A)}$为在事件A发生的条件下，事件B发生的条件概率。一般地，$P(B|A) \not= P(B)$ ，且它满足以下三条件：（1）非负性；（2）规范性；（3）可列可加性。
设E为随机试验，Ω为样本空间，A，B为任意两个事件，设$P(A)>0$，称$P(B|A) = \frac{P(AB)}{P(A)}$为在事件A发生的条件下事件B的条件概率。
上述乘法公式可推广到任意有穷多个事件时的情况。 设（$A_1,A_2,\cdots,A_n$）为任意n个事件（$n\ge2$）且$P(A_1,A_2,\cdots,A_n)>0$，则$P(A_1A_2 \cdots …
回溯算法Clojure实现
Published 2014年05月29日 15:10 by james
什么是回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法实现
算法准备
准备一个默认的打印函数，把数组a中的数组转换成字母打印出来。
(defn display [c]
(println (map #(char (+ 65 %)) c)))
实现方式，在这里，我们设计回溯法的实现需要接受是个参数，分别是n, m, …
回溯算法Ruby实现
Published 2011年02月14日 10:52 by james
什么是回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法实现
算法准备
准备一个默认的打印函数，把数组a中的数组转换成字母打印出来。
ALPHABET = Array('A'..'Z')
DISPLAY = lambda {|a| p a.map{|i …回溯算法Python实现
Published 2010年01月01日 19:52 by james
什么是回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法实现
算法准备
准备一个默认的打印函数，把数组a中的数组转换成字母打印出来。
def display(a):
l = ['A', 'B', 'C', 'D', 'E', 'F', 'G', …归并排序(C语言描述)
Published 2009年10月10日 16:52 by james
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序算法以O（nlogn）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。但它的一个显著问题就是需要额外的存储空间来辅助排序，空间复杂度是O(n)的，与quicksort和heapsort相比就逊色了不少，不过也可以实现空间复杂度为O（1）的归并排序，这将增加比较操作和交换操作的次数。归并排序可以使用在外部排序上：一般两路的外部排序是从源文件里读出内存大小的一块，然后在内存中排序，在放回文件里，这样生成若干文件。然后在从其中两个文件中读数据，按照merge的方式写到另一个文件中去。这一步根本用不到辅助空间。唯一可能用到辅助空间的地方是前面的一步，即将一块数据在内存中排序。
归并操作
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
归并操作的工作原理如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
归并排序
归并排序具体工作原理如下（假设序列共有n个元素）:
- 将序列每相邻两个数字进行归并操作（merge），形成floor(n / 2)个序列，排序后每个序列包含两个元素
- 将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素
- 重复步骤2，直到所有元素排序完毕
算法演示1 （非递归版本）:
#include<stdio.h>
#include<stdlib.h>
void merge( …