一、前言        旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界法、线性规划法、动态规划法等。但是,随着问题规模的…

2021年5月5日 0条评论 3点热度 阅读全文

转载http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 字符串匹配的KMP算法 作者: 阮一峰 日期: 2013年5月 1日 字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是…

2021年5月4日 0条评论 3点热度 阅读全文

传统的字符串匹配 1.思路: 重头开始,依次将主串与次串相比较。如果相同则比较主串与次串的下一个字符;如果不同,则回溯至之前主串比较的后一个字符,再与次串进行一对一比较,直至主串比完。 2.代码实现: #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int main() { char name1[100] = {"ababa…

2021年5月4日 0条评论 1点热度 阅读全文

关于理解计算失配函数的一点小心得。 首先,感谢Jake Boxer的文章给我的帮助。 在jake的文章里面,说的,前缀和后缀是理解的关键。请先阅读以下jake的文章(不然可能不好理解)。 正题:假设字符串 P 的长度是 m。我们给定 P 的失配函数为 failure[m],failure[0] = 0。 假设 0<= j < m ,如果我们知道了由 failure[j-1] 推导出 failure[j] 的公式的话,我们就很容易求出失配函数了。 关于 failure[j-1] 与failure[j]的关…

2021年5月4日 0条评论 1点热度 阅读全文

1. KMP算法基本思想 问题:在字符串ABABABACA中寻找字符串ABABACA,并返回第一次出现的位置。 下面分析匹配过程 ABABABACA ABABACA |此处出现不匹配 若此时按照朴素字符串匹配算法进行匹配,模式字符串在不匹配的时候右移一位,重新从第一个字符进行匹配,情况如下 ABABABACA ABABACA |右移一位,重新从第一个字符进行匹配,很明显不匹配,无效偏移 ABABABACA ABABACA |再次右移一位,重新从第一个字符进行匹配,一直到模式串末尾,匹配成功 能否避免无效偏移和每次都…

2021年5月4日 0条评论 0点热度 阅读全文

本人小白,如果有写的不恰当的地方,还请大家指出,共同进步学习。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------…

2021年5月4日 0条评论 2点热度 阅读全文

在做pat的时候,用dfs写了一道题的解超时,看别人的解法时,发现别人用了Dijkstra算法,瞬间自己就混乱了,因为之前也看过Dijkstra,bfs算法,但是当时居然都傻傻分不清楚了,所以决定写一篇总结一下。 一:广度优先算法(BFS)         先搜索邻居,搜完邻居再搜邻居的邻居。 其中俩个思想:1.双端队列不为空则循环                     &n…

2021年5月4日 0条评论 1点热度 阅读全文

前言 : 因为之前刚写过最小生成树算法,刚开始看到Dijkstra算法的时候,因为要求各点到源点的最短距离,会想着直接从最小生成树的也是每找到最短的距离点加进来,但是后面仔细想了下,又翻了下定义,得到 最短路径是一个图中2个点的最短距离。 最小生成树是连接所有的点的路径最短,但是不一定是任意两点的距离最小,例如:     最小生成树是:A->B->C AC距离是2+2=4 但是AC的最短距离是3 一 最短路径问题 最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组…

2021年5月4日 0条评论 1点热度 阅读全文

题目描述:                 给定n个矩阵{A1,A2,…,An},其中,Ai与Ai+1是可乘的,(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的次数最小。 例如:                   A1是A(5*10)的方阵; …

2021年5月4日 0条评论 1点热度 阅读全文

问题 1分2分5分的硬币三种,组合成1角,共有多少种组合? 有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,有多少中组合可以组成n分钱? 一个人上台阶可以一次上1个,2个,或者3个,问这个人上n层的台阶,总共有几种走法? 问法不一样,但是本质一样! 解析 不难发现,此题就是完全背包问题。同时也是Fibonacci的动态规划解法,所有有必要进行深入理解。 动态规划: dp[i][sum] = 用前i种硬币构成sum 的所有组合数。 状态转移方程: dp[i][sum] = dp[i-1][sum -…

2021年5月4日 0条评论 1点热度 阅读全文