为什么使用近似算法 无法找到一个NP难问题的多项式时间普适算法，因此我们思考牺牲算法的精确度，以在可计算时间内找到一个近似解。对于一个近似算法，满足： 在多项式时间内完成 具...
发简信
IP属地：四川
-
算法设计与分析笔记之近似算法 -
C++中几个输入函数的用法
1. cin 最基本最常用的方法，如接收一个数字或者字符串。 cin遇空格、tab、\n都结束。 2. cin.get() cin.get()或cin.get(字符变量名)接...
-
算法设计与分析笔记之NP完备性理论一. P、NP、NPC 三类问题都会涉及到多项式时间算法，我们先解决什么是多项式时间算法。 多项式时间的算法的形式化定义是，对于规模为n的输入，在最坏情况下的运行时间是...
-
最长公共子序列（LCS）——动态规划问题描述 子序列是指，从序列中选出一些子元素，需满足其前后关系与在原序列中相同；公共是指该序列同时是两个序列的子序列。如两个序列{4，2，1 ，6，5，8，13，18，9...
-
课程学习——有限自动机理论一、Chomsky对文法和语言对分类 Chomsky的分类依据是产生该语言的文法。 0型文法 所有一般的PSG（短语结构文法）及PSL（短语结构语言）。似乎对文法和语...
-
算法设计与分析笔记之最大流/最小割问题割（Cut） s-t cut：(A, B)，将图分为两部分A和B，源s∈A，终点t∈Bcut(A, B)的容量（capacity）：所有流出A的边的容量和，注意区分与流量（f...
-
最长上升子序列（LIS）——动态规划
问题描述 给定n个数字的序列，如11，3，6，9，13，14，18，12，15，2，16，20，8，19，问最长的上升序列长度是多少。 上升序列，分为严格单调递增序列和...
-
Latex数学公式 插入空格
公式中插入空格 公式中的数字符号间有时感觉太紧凑，或者想把几个公式同行显示，就需要在公式中/间插入空格。 两个m的大小 一个m的大小 1/3m的大小（大空格） 2/7m的大小...