精华内容
下载资源
问答
  • ACM常用算法

    2018-04-29 10:09:20
    ACM主要算法ACM主要算法介绍初期篇一、基本算法(1)枚举(poj1753, poj2965)(2)贪心(poj1328, poj2109, poj2586)(3)递归和分治法(4)递推(5)构造法(poj3295)(6)模拟法(poj1068, poj2632, poj1573, poj2993, poj2996)二...

    ACM主要算法


    ACM主要算法介绍

    初期篇

    一、基本算法
    (1)枚举(poj1753, poj2965)
    (2)贪心(poj1328, poj2109, poj2586)
    (3)递归和分治法
    (4)递推
    (5)构造法(poj3295)
    (6)模拟法(poj1068, poj2632, poj1573, poj2993, poj2996)
    二、图算法
    (1)图的深度优先遍历和广度优先遍历
    (2)最短路径算法(dijkstra, bellman-ford, floyd, heap+dijkstra)(poj1860, poj3259, poj1062, poj2253, poj1125, poj2240)
    (3)最小生成树算法(prim, kruskal)(poj1789, poj2485, poj1258, poj3026)
    (4)拓扑排序(poj1094)
    (5)二分图的最大匹配(匈牙利算法)(poj3041, poj3020)
    (6)最大流的增广路算法(KM算法)(poj1459, poj3436)
    三、数据结构
    (1)串(poj1035, poj3080, poj1936)
    (2)排序(快排、归并排(与逆序数有关)、堆排)(poj2388, poj2299)
    (3)简单并查集的应用
    (4)哈希表和二分查找等高效查找法(数的Hash, 串的Hash)(poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503)
    (5)哈夫曼树(poj3253)
    (6)堆
    (7)trie树(静态建树、动态建树)(poj2513)
    四、简单搜索
    (1)深度优先搜索(poj2488, poj3083, poj3009, poj1321, poj2251)
    (2)广度优先搜索(poj3278, poj1426, poj3126, poj3087, poj3414)
    (3)简单搜索技巧和剪枝(poj2531, poj1416, poj2676, 1129)
    五、动态规划
    (1)背包问题(poj1837, poj1276)
    (2)型如下表的简单DP(可参考lrj的书page149):
    1.E[j]=opt{D+w(i,j)} (poj3267, poj1836, poj1260, poj2533)
    2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176, poj1080, poj1159)
    3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]} (最优二分检索树问题)
    六、数学
    (1)组合数学
    1.加法原理和乘法原理
    2.排列组合
    3.递推关系(poj3252, poj1850, poj1019, poj1942)
    (2)数论
    1.素数与整除问题
    2.进制位
    3.同余模运算(poj2635, poj3292, poj1845, poj2115)
    (3)计算方法
    1.二分法求解单调函数相关知识(poj3273, poj3258, poj1905, poj3122)
    七、计算几何学
    (1)几何公式
    (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等)(poj2031, poj1039)
    (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408, poj1584)
    (4)凸包(poj2187, poj1113)

    中级篇
    一、基本算法
    (1)C++的标准模版库的应用(poj3096, poj3007)
    (2)较为复杂的模拟题的训练(poj3393, poj1472, poj3371, poj1027, poj2706)
    二、图算法
    (1)差分约束系统的建立和求解(poj1201, poj2983)
    (2)最小费用最大流(poj2516, poj2195)
    (3)双连通分量(poj2942)
    (4)强连通分支及其缩点(poj2186)
    (5)图的割边和割点(poj3352)
    (6)最小割模型、网络流规约(poj3308)
    三、数据结构
    (1)线段树(poj2528, poj2828, poj2777, poj2886, poj2750)
    (2)静态二叉检索树(poj2482, poj2352)
    (3)树状树组(poj1195, poj3321)
    (4)RMQ(poj3264, poj3368)
    (5)并查集的高级应用(poj1703, 2492)
    (6)KMP算法(poj1961, poj2406)
    四、搜索
    (1)最优化剪枝和可行性剪枝
    (2)搜索的技巧和优化(poj3411, poj1724)
    (3)记忆化搜索(poj3373, poj1691)
    五、动态规划
    (1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034)
    (2)记录状态的动态规划(poj3254, poj2411, poj1185)
    (3)树型动态规划(poj2057, poj1947, poj2486, poj3140)
    六、数学
    (1)组合数学
    1.容斥原理
    2.抽屉原理
    3.置换群与Polya定理(poj1286, poj2409, poj3270, poj1026)
    4.递推关系和母函数
    (2)数学
    1.高斯消元法(poj2947, poj1487, poj2065, poj1166, poj1222)
    2.概率问题(poj3071, poj3440)
    3.GCD、扩展的欧几里德(中国剩余定理)(poj3101)
    (3)计算方法
    1.0/1分数规划(poj2976)
    2.三分法求解单峰(单谷)的极值
    3.矩阵法(poj3150, poj3422, poj3070)
    4.迭代逼近(poj3301)
    (4)随机化算法(poj3318, poj2454)
    (5)杂题(poj1870, poj3296, poj3286, poj1095)
    七、计算几何学
    (1)坐标离散化
    (2)扫描线算法(例如求矩形的面积和周长,并常和线段树或堆一起使用)(poj1765, poj1177, poj1151, poj3277, poj2280, poj3004)
    (3)多边形的内核(半平面交)(poj3130, poj3335)
    (4)几何工具的综合应用(poj1819, poj1066, poj2043, poj3227, poj2165, poj3429)


    高级篇

    一、基本算法要求
    (1)代码快速写成,精简但不失风格(poj2525, poj1684, poj1421, poj1048, poj2050, poj3306)
    (2)保证正确性和高效性(poj3434)
    二、图算法
    (1)度限制最小生成树和第K最短路(poj1639)
    (2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155,  poj2112, poj1966, poj3281, poj1087, poj2289, poj3216, poj2446)
    (3)最优比率生成树(poj2728)
    (4)最小树形图(poj3164)
    (5)次小生成树
    (6)无向图、有向图的最小环
    三、数据结构
    (1)trie图的建立和应用(poj2778)
    (2)LCA和RMQ问题(LCA(最近公共祖先问题),有离线算法(并查集+dfs)和在线算法(RMQ+dfs))(poj1330)
    (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的)(poj2823)
    (4)左偏树(可合并堆)
    (5)后缀树(非常有用的数据结构,也是赛区考题的热点)(poj3415,poj3294)
    四、搜索
    (1)较麻烦的搜索题目训练(poj1069, poj3322, poj1475, poj1924, poj2049, poj3426)
    (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法(poj1768, poj1184, poj1872, poj1324, poj2046, poj1482)
    (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法(poj3131, poj2870, poj2286)
    五、动态规划
    (1)需要用数据结构优化的动态规划(poj2754, poj3378, poj3017)
    (2)四边形不等式理论
    (3)较难的状态DP(poj3133)
    六、数学
    (1)组合数学
    1.MoBius反演(poj2888, poj2154)
    2.偏序关系理论
    (2)博奕论
    1.极大极小过程(poj3317, poj1085)
    2.Nim问题
    七、计算几何学
    (1)半平面求交(poj3384, poj2540)
    (2)可视图的建立(poj2966)
    (3)点集最小圆覆盖
    (4)对踵点(poj2079)

    八、综合题(poj3109, poj1478, poj1462, poj2729, poj2048, poj3336, poj3315, poj2148, poj1263)

    附录:

    POJ是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran等多种语言。“北京大学程序在线评测系统”是一个免费的公益性网上程序设计题库,网址为http://poj.grids.cn/及 http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计竞赛,很多题目就反映工作和生活中的实际问题。用户可以针对某个题目编写程序并提交,让POJ自动判定程序的对错,几秒之内即可知道对还是错。


    ACM算法列表

    ACM所有算法

    数据结构
    • 栈,队列,链表
    • 哈希表,哈希数组
    • 堆,优先队列
      双端队列
      可并堆
      左偏堆
    • 二叉查找树
      Treap
      伸展树
    • 并查集
      集合计数问题
      二分图的识别
    • 平衡二叉树
    • 二叉排序树
    • 线段树
      一维线段树
      二维线段树
    • 树状数组
      一维树状数组
      N维树状数组
    • 字典树
    • 后缀数组,后缀树
    • 块状链表
    • 哈夫曼树
    • 桶,跳跃表
    • Trie树(静态建树、动态建树)
    • AC自动机
    • LCA和RMQ问题
    • KMP算法
    图论
    • 基本图算法图
      广度优先遍历
      深度优先遍历
      拓扑排序
      割边割点
      强连通分量
      Tarjan算法
      双连通分量
      强连通分支及其缩点
      图的割边和割点
      最小割模型、网络流规约
      2-SAT问题
      欧拉回路
      哈密顿回路
    • 最小生成树
      Prim算法
      Kruskal算法(稀疏图)
      Sollin算法
      次小生成树
      第k小生成树
      最优比例生成树
      最小树形图
      最小度限制生成树
      平面点的欧几里德最小生成树
      平面点的曼哈顿最小生成树
      最小平衡生成树
    • 最短路径
      有向无环图的最短路径->拓扑排序
      非负权值加权图的最短路径->Dijkstra算法(可使用二叉堆优化)
      含负权值加权图的最短路径->Bellmanford算法
      含负权值加权图的最短路径->Spfa算法
      (稠密带负权图中SPFA的效率并不如Bellman-Ford高)
      全源最短路弗洛伊德算法Floyd
      全源最短路Johnson算法
      次短路径
      第k短路径
      差分约束系统
      平面点对的最短路径(优化)
      双标准限制最短路径
    • 最大流
      增广路->Ford-Fulkerson算法
      预推流
      Dinic算法
      有上下界限制的最大流
      节点有限制的网络流
      无向图最小割->Stoer-Wagner算法
      有向图和无向图的边不交路径
      Ford-Fulkerson迭加算法
      含负费用的最小费用最大流
    • 匹配
      Hungary算法
      最小点覆盖
      最小路径覆盖
      最大独立集问题
      二分图最优完备匹配Kuhn-Munkras算法
      不带权二分匹配:匈牙利算法
      带权二分匹配:KM算法
      一般图的最大基数匹配
      一般图的赋权匹配问题
    • 拓扑排序
    • 弦图
    • 稳定婚姻问题
    搜索
    • 广搜的状态优化
      利用M进制数存储状态
      转化为串用hash表判重
      按位压缩存储状态
      双向广搜
      A*算法
    • 深搜的优化
      位运算
      剪枝
      函数参数尽可能少
      层数不易过大
      双向搜索或者是轮换搜索
      IDA*算法
    • 记忆化搜索
    动态规划
    • 四边形不等式理论
    • 不完全状态记录
      青蛙过河问题
      利用区间dp
    • 背包类问题
      0-1背包,经典问题
      无限背包,经典问题
      判定性背包问题
      带附属关系的背包问题
      + -1背包问题
      双背包求最优值
      构造三角形问题
      带上下界限制的背包问题(012背包)
    • 线性的动态规划问题
      积木游戏问题
      决斗(判定性问题)
      圆的最大多边形问题
      统计单词个数问题
      棋盘分割
      日程安排问题
      最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
      方块消除游戏(某区间可以连续消去求最大效益)
      资源分配问题
      数字三角形问题
      漂亮的打印
      邮局问题与构造答案
      最高积木问题
      两段连续和最大
      2次幂和问题
      N个数的最大M段子段和
      交叉最大数问题
    • 判定性问题的dp(如判定整除、判定可达性等)
      模K问题的dp
      特殊的模K问题,求最大(最小)模K的数
      变换数问题
    • 单调性优化的动态规划
      1-SUM问题
      2-SUM问题
      序列划分问题(单调队列优化)
    • 剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
      凸多边形的三角剖分问题
      乘积最大问题
      多边形游戏(多边形边上是操作符,顶点有权值)
      石子合并(N^3/N^2/NLogN各种优化)
    • 贪心的动态规划
      最优装载问题
      部分背包问题
      乘船问题
      贪心策略
      双机调度问题Johnson算法
    • 状态dp
      牛仔射击问题(博弈类)
      哈密顿路径的状态dp
      两支点天平平衡问题
      一个有向图的最接近二部图
    • 树型dp
      完美服务器问题(每个节点有3种状态)
      小胖守皇宫问题
      网络收费问题
      树中漫游问题
      树上的博弈
      树的最大独立集问题
      树的最大平衡值问题
      构造树的最小环

    数学

    数论
    • 中国剩余定理
    • 欧拉函数
    • 欧几里得定理
    • 欧几里德辗转相除法求GCD(最大公约数)
    • 扩展欧几里得
    • 大数分解与素数判定
    • 佩尔方程
    • 同余定理(大数求余)
    • 素数测试
      一千万以内:筛选法
      一千万以外:米勒测试法
    • 连分数逼近
    • 因式分解
    • 循环群生成元
    • 素数与整除问题
    • 进制位.
    • 同余模运算
    组合
    数学
    • 排列组合
    • 容斥原理
    • 递推关系和生成函数
    • Polya计数法
      Polya计数公式
      Burnside定理
    • N皇后构造解
    • 幻方的构造
    • 满足一定条件的hamilton圈的构造
    • Catalan数
    • Stirling数
    • 斐波拉契数
    • 调和数
    • 连分数
    • MoBius反演
    • 偏序关系理论
    • 加法原理和乘法原理
    计算
    几何
    • 基本公式
      叉乘
      点乘
      常见形状的面积、周长、体积公式
      坐标离散化
    • 线段
      判断两线段(一直线、一线段)是否相交
      求两线段的交点
    • 多边形
      判定凸多边形,顶点按顺时针或逆时针给出,(不)允许相邻边共线
      判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出
      判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0
      判点在任意多边形内,顶点按顺时针或逆时针给出
      判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1
      多边形重心
      多边形切割(半平面交)
      扫描线算法
      多边形的内核
    • 三角形
      内心
      外心
      重心
      垂心
      费马点

    • 判直线和圆相交,包括相切
      判线段和圆相交,包括端点和相切
      判圆和圆相交,包括相切
      计算圆上到点p最近点,如p与圆心重合,返回p本身
      计算直线与圆的交点,保证直线与圆有交点
      计算线段与圆的交点可用这个函数后判点是否在线段上
      计算圆与圆的交点,保证圆与圆有交点,圆心不重合
      计算两圆的内外公切线
      计算线段到圆的切点
      点集最小圆覆盖
    • 可视图的建立
    • 对踵点
    • 经典问题
      平面凸包
      三维凸包
      Delaunay剖分和Voronoi图
    计算
    方法
    • 二分法
      二分法求解单调函数相关知识
      用矩阵加速的计算
    • 迭代法
    • 三分法
    • 解线性方程组
      LUP分解
      高斯消元
    • 解模线性方程组
    • 定积分计算
    • 多项式求根
    • 周期性方程
    • 线性规划
    • 快速傅立叶变换
    • 随机算法
    • 0/1分数规划
    • 三分法求解单峰(单谷)的极值
    • 迭代逼近
    • 矩阵法
    博弈论
    • 极大极小过程
    • Nim问题
    展开全文
  • ACM主要算法

    2018-04-10 19:31:43
    ACM主要算法ACM主要算法介绍初期篇一、基本算法(1)枚举(poj1753, poj2965)(2)贪心(poj1328, poj2109, poj2586)(3)递归和分治法(4)递推(5)构造法(poj3295)(6)模拟法(poj1068, poj2632, poj1573, poj2993, poj2996)二...

    ACM主要算法


    ACM主要算法介绍

    初期篇

    一、基本算法
    (1)枚举(poj1753, poj2965)
    (2)贪心(poj1328, poj2109, poj2586)
    (3)递归和分治法
    (4)递推
    (5)构造法(poj3295)
    (6)模拟法(poj1068, poj2632, poj1573, poj2993, poj2996)
    二、图算法
    (1)图的深度优先遍历和广度优先遍历
    (2)最短路径算法(dijkstra, bellman-ford, floyd, heap+dijkstra)(poj1860, poj3259, poj1062, poj2253, poj1125, poj2240)
    (3)最小生成树算法(prim, kruskal)(poj1789, poj2485, poj1258, poj3026)
    (4)拓扑排序(poj1094)
    (5)二分图的最大匹配(匈牙利算法)(poj3041, poj3020)
    (6)最大流的增广路算法(KM算法)(poj1459, poj3436)
    三、数据结构
    (1)串(poj1035, poj3080, poj1936)
    (2)排序(快排、归并排(与逆序数有关)、堆排)(poj2388, poj2299)
    (3)简单并查集的应用
    (4)哈希表和二分查找等高效查找法(数的Hash, 串的Hash)(poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503)
    (5)哈夫曼树(poj3253)
    (6)堆
    (7)trie树(静态建树、动态建树)(poj2513)
    四、简单搜索
    (1)深度优先搜索(poj2488, poj3083, poj3009, poj1321, poj2251)
    (2)广度优先搜索(poj3278, poj1426, poj3126, poj3087, poj3414)
    (3)简单搜索技巧和剪枝(poj2531, poj1416, poj2676, 1129)
    五、动态规划
    (1)背包问题(poj1837, poj1276)
    (2)型如下表的简单DP(可参考lrj的书page149):
    1.E[j]=opt{D+w(i,j)} (poj3267, poj1836, poj1260, poj2533)
    2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176, poj1080, poj1159)
    3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]} (最优二分检索树问题)
    六、数学
    (1)组合数学
    1.加法原理和乘法原理
    2.排列组合
    3.递推关系(poj3252, poj1850, poj1019, poj1942)
    (2)数论
    1.素数与整除问题
    2.进制位
    3.同余模运算(poj2635, poj3292, poj1845, poj2115)
    (3)计算方法
    1.二分法求解单调函数相关知识(poj3273, poj3258, poj1905, poj3122)
    七、计算几何学
    (1)几何公式
    (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等)(poj2031, poj1039)
    (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408, poj1584)
    (4)凸包(poj2187, poj1113)

    中级篇
    一、基本算法
    (1)C++的标准模版库的应用(poj3096, poj3007)
    (2)较为复杂的模拟题的训练(poj3393, poj1472, poj3371, poj1027, poj2706)
    二、图算法
    (1)差分约束系统的建立和求解(poj1201, poj2983)
    (2)最小费用最大流(poj2516, poj2195)
    (3)双连通分量(poj2942)
    (4)强连通分支及其缩点(poj2186)
    (5)图的割边和割点(poj3352)
    (6)最小割模型、网络流规约(poj3308)
    三、数据结构
    (1)线段树(poj2528, poj2828, poj2777, poj2886, poj2750)
    (2)静态二叉检索树(poj2482, poj2352)
    (3)树状树组(poj1195, poj3321)
    (4)RMQ(poj3264, poj3368)
    (5)并查集的高级应用(poj1703, 2492)
    (6)KMP算法(poj1961, poj2406)
    四、搜索
    (1)最优化剪枝和可行性剪枝
    (2)搜索的技巧和优化(poj3411, poj1724)
    (3)记忆化搜索(poj3373, poj1691)
    五、动态规划
    (1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034)
    (2)记录状态的动态规划(poj3254, poj2411, poj1185)
    (3)树型动态规划(poj2057, poj1947, poj2486, poj3140)
    六、数学
    (1)组合数学
    1.容斥原理
    2.抽屉原理
    3.置换群与Polya定理(poj1286, poj2409, poj3270, poj1026)
    4.递推关系和母函数
    (2)数学
    1.高斯消元法(poj2947, poj1487, poj2065, poj1166, poj1222)
    2.概率问题(poj3071, poj3440)
    3.GCD、扩展的欧几里德(中国剩余定理)(poj3101)
    (3)计算方法
    1.0/1分数规划(poj2976)
    2.三分法求解单峰(单谷)的极值
    3.矩阵法(poj3150, poj3422, poj3070)
    4.迭代逼近(poj3301)
    (4)随机化算法(poj3318, poj2454)
    (5)杂题(poj1870, poj3296, poj3286, poj1095)
    七、计算几何学
    (1)坐标离散化
    (2)扫描线算法(例如求矩形的面积和周长,并常和线段树或堆一起使用)(poj1765, poj1177, poj1151, poj3277, poj2280, poj3004)
    (3)多边形的内核(半平面交)(poj3130, poj3335)
    (4)几何工具的综合应用(poj1819, poj1066, poj2043, poj3227, poj2165, poj3429)


    高级篇

    一、基本算法要求
    (1)代码快速写成,精简但不失风格(poj2525, poj1684, poj1421, poj1048, poj2050, poj3306)
    (2)保证正确性和高效性(poj3434)
    二、图算法
    (1)度限制最小生成树和第K最短路(poj1639)
    (2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155,  poj2112, poj1966, poj3281, poj1087, poj2289, poj3216, poj2446)
    (3)最优比率生成树(poj2728)
    (4)最小树形图(poj3164)
    (5)次小生成树
    (6)无向图、有向图的最小环
    三、数据结构
    (1)trie图的建立和应用(poj2778)
    (2)LCA和RMQ问题(LCA(最近公共祖先问题),有离线算法(并查集+dfs)和在线算法(RMQ+dfs))(poj1330)
    (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的)(poj2823)
    (4)左偏树(可合并堆)
    (5)后缀树(非常有用的数据结构,也是赛区考题的热点)(poj3415,poj3294)
    四、搜索
    (1)较麻烦的搜索题目训练(poj1069, poj3322, poj1475, poj1924, poj2049, poj3426)
    (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法(poj1768, poj1184, poj1872, poj1324, poj2046, poj1482)
    (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法(poj3131, poj2870, poj2286)
    五、动态规划
    (1)需要用数据结构优化的动态规划(poj2754, poj3378, poj3017)
    (2)四边形不等式理论
    (3)较难的状态DP(poj3133)
    六、数学
    (1)组合数学
    1.MoBius反演(poj2888, poj2154)
    2.偏序关系理论
    (2)博奕论
    1.极大极小过程(poj3317, poj1085)
    2.Nim问题
    七、计算几何学
    (1)半平面求交(poj3384, poj2540)
    (2)可视图的建立(poj2966)
    (3)点集最小圆覆盖
    (4)对踵点(poj2079)

    八、综合题(poj3109, poj1478, poj1462, poj2729, poj2048, poj3336, poj3315, poj2148, poj1263)

    附录:

    POJ是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran等多种语言。“北京大学程序在线评测系统”是一个免费的公益性网上程序设计题库,网址为http://poj.grids.cn/及 http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计竞赛,很多题目就反映工作和生活中的实际问题。用户可以针对某个题目编写程序并提交,让POJ自动判定程序的对错,几秒之内即可知道对还是错。


    ACM算法列表

    ACM所有算法

    数据结构
    • 栈,队列,链表
    • 哈希表,哈希数组
    • 堆,优先队列
      双端队列
      可并堆
      左偏堆
    • 二叉查找树
      Treap
      伸展树
    • 并查集
      集合计数问题
      二分图的识别
    • 平衡二叉树
    • 二叉排序树
    • 线段树
      一维线段树
      二维线段树
    • 树状数组
      一维树状数组
      N维树状数组
    • 字典树
    • 后缀数组,后缀树
    • 块状链表
    • 哈夫曼树
    • 桶,跳跃表
    • Trie树(静态建树、动态建树)
    • AC自动机
    • LCA和RMQ问题
    • KMP算法
    图论
    • 基本图算法图
      广度优先遍历
      深度优先遍历
      拓扑排序
      割边割点
      强连通分量
      Tarjan算法
      双连通分量
      强连通分支及其缩点
      图的割边和割点
      最小割模型、网络流规约
      2-SAT问题
      欧拉回路
      哈密顿回路
    • 最小生成树
      Prim算法
      Kruskal算法(稀疏图)
      Sollin算法
      次小生成树
      第k小生成树
      最优比例生成树
      最小树形图
      最小度限制生成树
      平面点的欧几里德最小生成树
      平面点的曼哈顿最小生成树
      最小平衡生成树
    • 最短路径
      有向无环图的最短路径->拓扑排序
      非负权值加权图的最短路径->Dijkstra算法(可使用二叉堆优化)
      含负权值加权图的最短路径->Bellmanford算法
      含负权值加权图的最短路径->Spfa算法
      (稠密带负权图中SPFA的效率并不如Bellman-Ford高)
      全源最短路弗洛伊德算法Floyd
      全源最短路Johnson算法
      次短路径
      第k短路径
      差分约束系统
      平面点对的最短路径(优化)
      双标准限制最短路径
    • 最大流
      增广路->Ford-Fulkerson算法
      预推流
      Dinic算法
      有上下界限制的最大流
      节点有限制的网络流
      无向图最小割->Stoer-Wagner算法
      有向图和无向图的边不交路径
      Ford-Fulkerson迭加算法
      含负费用的最小费用最大流
    • 匹配
      Hungary算法
      最小点覆盖
      最小路径覆盖
      最大独立集问题
      二分图最优完备匹配Kuhn-Munkras算法
      不带权二分匹配:匈牙利算法
      带权二分匹配:KM算法
      一般图的最大基数匹配
      一般图的赋权匹配问题
    • 拓扑排序
    • 弦图
    • 稳定婚姻问题
    搜索
    • 广搜的状态优化
      利用M进制数存储状态
      转化为串用hash表判重
      按位压缩存储状态
      双向广搜
      A*算法
    • 深搜的优化
      位运算
      剪枝
      函数参数尽可能少
      层数不易过大
      双向搜索或者是轮换搜索
      IDA*算法
    • 记忆化搜索
    动态规划
    • 四边形不等式理论
    • 不完全状态记录
      青蛙过河问题
      利用区间dp
    • 背包类问题
      0-1背包,经典问题
      无限背包,经典问题
      判定性背包问题
      带附属关系的背包问题
      + -1背包问题
      双背包求最优值
      构造三角形问题
      带上下界限制的背包问题(012背包)
    • 线性的动态规划问题
      积木游戏问题
      决斗(判定性问题)
      圆的最大多边形问题
      统计单词个数问题
      棋盘分割
      日程安排问题
      最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
      方块消除游戏(某区间可以连续消去求最大效益)
      资源分配问题
      数字三角形问题
      漂亮的打印
      邮局问题与构造答案
      最高积木问题
      两段连续和最大
      2次幂和问题
      N个数的最大M段子段和
      交叉最大数问题
    • 判定性问题的dp(如判定整除、判定可达性等)
      模K问题的dp
      特殊的模K问题,求最大(最小)模K的数
      变换数问题
    • 单调性优化的动态规划
      1-SUM问题
      2-SUM问题
      序列划分问题(单调队列优化)
    • 剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
      凸多边形的三角剖分问题
      乘积最大问题
      多边形游戏(多边形边上是操作符,顶点有权值)
      石子合并(N^3/N^2/NLogN各种优化)
    • 贪心的动态规划
      最优装载问题
      部分背包问题
      乘船问题
      贪心策略
      双机调度问题Johnson算法
    • 状态dp
      牛仔射击问题(博弈类)
      哈密顿路径的状态dp
      两支点天平平衡问题
      一个有向图的最接近二部图
    • 树型dp
      完美服务器问题(每个节点有3种状态)
      小胖守皇宫问题
      网络收费问题
      树中漫游问题
      树上的博弈
      树的最大独立集问题
      树的最大平衡值问题
      构造树的最小环

    数学

    数论
    • 中国剩余定理
    • 欧拉函数
    • 欧几里得定理
    • 欧几里德辗转相除法求GCD(最大公约数)
    • 扩展欧几里得
    • 大数分解与素数判定
    • 佩尔方程
    • 同余定理(大数求余)
    • 素数测试
      一千万以内:筛选法
      一千万以外:米勒测试法
    • 连分数逼近
    • 因式分解
    • 循环群生成元
    • 素数与整除问题
    • 进制位.
    • 同余模运算
    组合
    数学
    • 排列组合
    • 容斥原理
    • 递推关系和生成函数
    • Polya计数法
      Polya计数公式
      Burnside定理
    • N皇后构造解
    • 幻方的构造
    • 满足一定条件的hamilton圈的构造
    • Catalan数
    • Stirling数
    • 斐波拉契数
    • 调和数
    • 连分数
    • MoBius反演
    • 偏序关系理论
    • 加法原理和乘法原理
    计算
    几何
    • 基本公式
      叉乘
      点乘
      常见形状的面积、周长、体积公式
      坐标离散化
    • 线段
      判断两线段(一直线、一线段)是否相交
      求两线段的交点
    • 多边形
      判定凸多边形,顶点按顺时针或逆时针给出,(不)允许相邻边共线
      判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出
      判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0
      判点在任意多边形内,顶点按顺时针或逆时针给出
      判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1
      多边形重心
      多边形切割(半平面交)
      扫描线算法
      多边形的内核
    • 三角形
      内心
      外心
      重心
      垂心
      费马点

    • 判直线和圆相交,包括相切
      判线段和圆相交,包括端点和相切
      判圆和圆相交,包括相切
      计算圆上到点p最近点,如p与圆心重合,返回p本身
      计算直线与圆的交点,保证直线与圆有交点
      计算线段与圆的交点可用这个函数后判点是否在线段上
      计算圆与圆的交点,保证圆与圆有交点,圆心不重合
      计算两圆的内外公切线
      计算线段到圆的切点
      点集最小圆覆盖
    • 可视图的建立
    • 对踵点
    • 经典问题
      平面凸包
      三维凸包
      Delaunay剖分和Voronoi图
    计算
    方法
    • 二分法
      二分法求解单调函数相关知识
      用矩阵加速的计算
    • 迭代法
    • 三分法
    • 解线性方程组
      LUP分解
      高斯消元
    • 解模线性方程组
    • 定积分计算
    • 多项式求根
    • 周期性方程
    • 线性规划
    • 快速傅立叶变换
    • 随机算法
    • 0/1分数规划
    • 三分法求解单峰(单谷)的极值
    • 迭代逼近
    • 矩阵法
    博弈论
    • 极大极小过程
    • Nim问题
    展开全文
  • ACM算法分类

    2019-08-22 11:59:42
    来源: ACM算法分类 发信人: namespace (dev c++), 信区: ACM_ICPC 标 题: ACM算法分类 发信站: 北邮人论坛 (Tue Nov 20 19:34:48 2007), 站内 经过我初步的整理,一个比较完整的归类已经完成,现在发布给大家,...

    来源: ACM的算法分类

    发信人: namespace (dev c++), 信区: ACM_ICPC
    标 题: ACM的算法分类
    发信站: 北邮人论坛 (Tue Nov 20 19:34:48 2007), 站内

    经过我初步的整理,一个比较完整的归类已经完成,现在发布给大家,希望可以方便大家练习,如有不足,还请大家见谅,这个可能会随时有更新,请大家注意.如果有什么要求或补充的可以跟贴提出,勿水!!!

    OJ上的一些水题(可用来练手和增加自信)
    (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

    初期:

    一.基本算法:

    ​ (1)枚举. ( poj1753, poj2965 )
    ​ (2)贪心( poj1328, poj2109, poj2586 )
    ​ (3)递归和分治法.
    ​ (4)递推.
    ​ (5)构造法.( poj3295 )
    ​ (6)模拟法.( poj1068, poj2632, poj1573,poj2993,poj2996)

    二.图算法:

    ​ (1)图的深度优先遍历和广度优先遍历.
    ​ (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
    ​ (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
    ​ (3)最小生成树算法(prim,kruskal)
    ​ (poj1789,poj2485,poj1258,poj3026)
    ​ (4)拓扑排序 (poj1094)
    ​ (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
    ​ (6)最大流的增广路算法(KM算法). (poj1459,poj3436)

    三.数据结构.

    ​ (1)串 ( poj1035,poj3080,poj1936)
    ​ (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
    ​ (3)简单并查集的应用.
    ​ (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
    ​ (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
    ​ (5)哈夫曼树(poj3253)
    ​ (6)堆
    ​ (7)trie树(静态建树、动态建树) (poj2513)

    四.简单搜索

    ​ (1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
    ​ (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
    ​ (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

    五.动态规划

    ​ (1)背包问题. (poj1837,poj1276)
    ​ (2)型如下表的简单DP(可参考lrj的书 page149):
    ​ 1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
    ​ 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
    ​ (poj3176,poj1080,poj1159)
    ​ 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)

    六.数学

    ​ (1)组合数学:
    ​ 1.加法原理和乘法原理.
    ​ 2.排列组合.
    ​ 3.递推关系.
    ​ (POJ3252,poj1850,poj1019,poj1942)
    ​ (2)数论.
    ​ 1.素数与整除问题
    ​ 2.进制位.
    ​ 3.同余模运算.
    ​ (poj2635, poj3292,poj1845,poj2115)
    ​ (3)计算方法.
    ​ 1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)

    七.计算几何学.

    ​ (1)几何公式.
    ​ (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
    ​ (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
    ​ (poj1408,poj1584)
    ​ (4)凸包. (poj2187,poj1113)

    中级:

    一.基本算法:

    ​ (1)C++的标准模版库的应用. (poj3096,poj3007)
    ​ (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

    二.图算法:

    ​ (1)差分约束系统的建立和求解. (poj1201,poj2983)
    ​ (2)最小费用最大流(poj2516,poj2516,poj2195)
    ​ (3)双连通分量(poj2942)
    ​ (4)强连通分支及其缩点.(poj2186)
    ​ (5)图的割边和割点(poj3352)
    ​ (6)最小割模型、网络流规约(poj3308, )

    三.数据结构.

    ​ (1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
    ​ (2)静态二叉检索树. (poj2482,poj2352)
    ​ (3)树状树组(poj1195,poj3321)
    ​ (4)RMQ. (poj3264,poj3368)
    ​ (5)并查集的高级应用. (poj1703,2492)
    ​ (6)KMP算法. (poj1961,poj2406)

    四.搜索

    ​ (1)最优化剪枝和可行性剪枝
    ​ (2)搜索的技巧和优化 (poj3411,poj1724)
    ​ (3)记忆化搜索(poj3373,poj1691)

    五.动态规划

    ​ (1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
    ​ (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
    ​ (2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
    ​ (3)树型动态规划(poj2057,poj1947,poj2486,poj3140)

    六.数学

    ​ (1)组合数学:
    ​ 1.容斥原理.
    ​ 2.抽屉原理.
    ​ 3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
    ​ 4.递推关系和母函数.

    ​ (2)数学.
    ​ 1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
    ​ 2.概率问题. (poj3071,poj3440)
    ​ 3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
    ​ (3)计算方法.
    ​ 1.0/1分数规划. (poj2976)
    ​ 2.三分法求解单峰(单谷)的极值.
    ​ 3.矩阵法(poj3150,poj3422,poj3070)
    ​ 4.迭代逼近(poj3301)
    ​ (4)随机化算法(poj3318,poj2454)
    ​ (5)杂题.
    ​ (poj1870,poj3296,poj3286,poj1095)

    七.计算几何学.

    ​ (1)坐标离散化.
    ​ (2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
    ​ (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
    ​ (3)多边形的内核(半平面交)(poj3130,poj3335)
    ​ (4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

    高级:

    一.基本算法要求:

    ​ (1)代码快速写成,精简但不失风格
    ​ (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
    ​ (2)保证正确性和高效性. poj3434

    二.图算法:

    ​ (1)度限制最小生成树和第K最短路. (poj1639)
    ​ (2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
    ​ (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
    ​ (3)最优比率生成树. (poj2728)
    ​ (4)最小树形图(poj3164)
    ​ (5)次小生成树.
    ​ (6)无向图、有向图的最小环

    三.数据结构.

    ​ (1)trie图的建立和应用. (poj2778)
    ​ (2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
    ​ (RMQ+dfs)).(poj1330)
    ​ (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
    ​ 目的). (poj2823)
    ​ (4)左偏树(可合并堆).
    ​ (5)后缀树(非常有用的数据结构,也是赛区考题的热点).
    ​ (poj3415,poj3294)

    四.搜索

    ​ (1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
    ​ (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
    ​ (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA
    算法. (poj3131,poj2870,poj2286)

    五.动态规划

    ​ (1)需要用数据结构优化的动态规划.
    ​ (poj2754,poj3378,poj3017)
    ​ (2)四边形不等式理论.
    ​ (3)较难的状态DP(poj3133)

    六.数学

    ​ (1)组合数学.
    ​ 1.MoBius反演(poj2888,poj2154)
    ​ 2.偏序关系理论.
    ​ (2)博奕论.
    ​ 1.极大极小过程(poj3317,poj1085)
    ​ 2.Nim问题.

    七.计算几何学.

    ​ (1)半平面求交(poj3384,poj2540)
    ​ (2)可视图的建立(poj2966)
    ​ (3)点集最小圆覆盖.
    ​ (4)对踵点(poj2079)

    八.综合题.

    ​ (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

    展开全文
  • ACM搜索算法总结

    2018-03-19 21:59:56
    转自:http://blog.csdn.net/shenmen123456/article/details/6695499 在此感谢~搜索是ACM竞赛中的常见算法,本文的主要内容就是分析它的 特点,以及在实际问题中如何合理的选择搜索方法,提高效率。文章的第一部分...

    转自:http://blog.csdn.net/shenmen123456/article/details/6695499 在此感谢~

    搜索是ACM竞赛中的常见算法,本文的主要内容就是分析它的 特点,以及在实际问题中如何合理的选择搜索方法,提高效率。文章的第一部分首先分析了各种基本的搜索及其各自的特点。第二部分在基本搜索方法的基础上提出 一些更高级的搜索,提高搜索的效率。第三部分将搜索和动态规划结合,高效地解决实际问题,体现搜索的广泛应用性。第四部分总结全文。


    文章在分析各种搜索的同时,分析了我们在解题中应该怎样合理利用它,理论结合实际,对我们的解题实践有一定的指导意义。

    【 Abstract 】 Search is a algorithm which is often seen in ACM/ICPC .The main idea of this article is to analysis its specially characterist and how to choose search method reasonably for the increasing efficiency in practical problems.

    The first section analysis every basic search method and each specially characterist. The second section bring up some advanced search methods to increase the efficiency.The third section is to combine the search method and dynamic programing method to solve practical problem efficiencily indicating that search methods have weed applicability.The fourth section is to sum up the article and prospect the development of search.

    提起搜索,大家都不会陌生。它的应用是十分广泛的,比如目前internet上的搜索引擎,WINDOWS XP操作系统中的文件搜索。同时,搜索是编程解题的一种重要的手段,在竞赛中,我们有时会碰到一些题目,它们既不能通过建立数学模型解决,又没有现成算法 可以套用,或者非遍历所有状况才可以得出正确结果。这时,我们就必须采用搜索算法来解决问题。几乎每次ACM竞赛都要考察到这方面的内容。因此,如何更深 入地了解搜索,从而更为有效地运用这个解题的有力武器,是一个值得深入研究的问题。要掌握搜索的应用技巧,就要了解它的分类及其各方面的特点。

    第一部分 基本的搜索算法
    一、回溯算法
    回溯算法是所有搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”思想作为其控制结构,其相当于采用了先根遍历的方法来构造解答树,可用于找解或所有解以及最优解。

    评价:回溯算法对空间的消耗较少,当其与分枝定界法一起使用时,对于所求解在解答树中层较深的问题 有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用,以免产生循环。

    二、深度搜索与广度搜索
    深度搜索与广度搜索的控制结构和产生系统很相似,唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点,所以在产生后继节点时可以去掉一部分重复 的节点,从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点,而不同的是,深度搜索下一次扩展的是本次扩展出来的子节点中的一个,而广度搜索 扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构.

    评价:广度搜索是求解最优解的一种较好的方法,在后面将会对其进行进一步的优化。而深度搜索多用于只要求解,并且解答树中的重复节点较多并且重复较难判断时使用,但往往可以用A*或回溯算法代替。

    第二部分 搜索算法的优化(一)
    一、双向广度搜索
    广度搜索虽然可以得到最优解,但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索,理想情况下可以减少二分之一的搜索量,从而提高搜索速度。

    二、分支定界
    分支定界实际上是A*算法的一种雏形,其对于每个扩展出来的节点给出一个预期值,如果这个预期值不如当前已经搜索出来的结果好的话,则将这个节点(包括其子节点)从解答树中删去,从而达到加快搜索速度的目的。

    三、A*算法
    A*算法中更一般的引入了一个估价函数f,其定义为f=g+h。其中g为到达当前节点的耗费,而h表示对从当前节点到达目标节点的耗费的估计。其必须满足两个条件:

    1. h必须小于等于实际的从当前节点到达目标节点的最小耗费h*。
    2. f必须保持单调递增。

    A*算法的控制结构与广度搜索的十分类似,只是每次扩展的都是当前待扩展节点中f值最小的一个,如果扩展出来的节点与已扩展的节点重复,则删去这个节点。如果与待扩展节点重复,如果这个节点的估价函数值较小,则用其代替原待扩展节点。

    对A*算法的改进--分阶段A*. 当A*算法出现数据溢出时,从待扩展节点中取出若干个估价函数值较小的节点,然后放弃其余的待扩展节点,从而可以使搜索进一步的进行下去。

    四、A*算法与回溯的结合(IDA*)
    这是A*算法的一个变形,很好综合了A*算法的人工智能性和回溯法对空间的消耗较少的优点,在一些规模很大的搜索问题中会起意想不到的效果。它的具体名称 是 Iterative Deepening A*, 1985年由Korf提出。该算法的最初目的是为了利用深度搜索的优势解决广度A*的空间问题,其代价是会产生重复搜索。归纳一下,IDA*的基本思路 是:首先将初始状态结点的H值设为阈值maxH,然后进行深度优先搜索,搜索过程中忽略所有H值大于maxH的结点;如果没有找到解,则加大阈值 maxH,再重复上述搜索,直到找到一个解。在保证H值的计算满足A*算法的要求下,可以证明找到的这个解一定是最优解。在程序实现上,IDA* 要比 A* 方便,因为不需要保存结点,不需要判重复,也不需要根据 H值对结点排序,占用空间小。

    下面,以一个具体的实例来分析比较上述几种搜索算法的效率等问题。

    在scu online judge(http://cs.scu.edu.cn/acm)上有这么一道题目:这就是古老而又经典的15数码难题:在4*4的棋盘上,摆有15个棋 子,每个棋子分别标有1-15的某一个数字。棋盘中有一个空格,空格周围的棋子可以移到空格中。现给出初始状态和目标状态,要求找到一种移动步骤最少的方 法。

    看到这个题目,会发觉几乎每个搜索算法都可以解这个问题。而事实确实如此。

    首先考虑深度优先搜索,它会遍历这棵解答树。这棵解答树最多可达16!个节点,深度优先搜索必须全部遍历后,才能从所有解中选出最小的一个做为答案,其代价是非常巨大的。

    其次考虑广度深度优先搜索,这不失为一个好办法。因为广度优先搜索的层次遍历解答树的特点,一旦搜索到一个目标节点,那么这时的深度一定是最优解,而不必 象深度优先搜索那样继续搜索目标节点,最后比较才能得出最优解。该搜索方法在这道题目上会遇见致命的问题:广度深度优先搜索是一种盲目的搜索,深度比较大 的测试数据会产生大量的无用的节点,同时消耗很多时间在重复节点的判断上。

    为了减少重复的节点,加入人工智能性,马上可以想到用A*算法。经过分析发现,该方法对避免产生大量的无用的节点起到了一定的效果,但是会花97%以上的 时间去判断新产生节点是否与已扩展的和待扩展的节点重复。看来如何提高判重的速度成为该题目的关键。解决这个问题有很多办法,比如引入哈希表,对已扩展的 和待扩展的节点采用哈希表存储,减少判重的代价,或者对已扩展的和待扩展的节点采用桶排序,也可以减少判重的代价。我们现在来尝试一下用 IDA*算法。该算法有个值得注意的地方:对估计函数的选取。如果选用当前状态每个位置上与目标状态每个位置上相同节点的数目加当前状态的深度作为估计函 数,由于当前状态每个位置上与目标状态每个位置上相同节点的数目这个值一般较小,不能明显显示各个状态之间的差别,运行过程中会产生大量的无用的节点,同 样会使效率很低,不能在60s以内完成计算。比较优化的一个办法是选用由于当前状态每个位置上的数字偏离目标节点该数字的位置的距离加当前状态的深度作为 估计函数。这个估计函数的选取没有统一的标准,找到合适的该函数并不容易,但是可以大致按照这个原则:在一定范围内加大各个状态启发函数值的差别。

    实践证明,该方法用广泛的通用性,在很多情况下可以替换一般的深度优先搜索和广度优先搜索。

    第三部分 搜索算法的优化(二)
    该部分将谈到搜索与其他算法的结合。再看scu online judge的一道题目: 给定一个8 * 8的国际象棋棋盘。给出棋盘上任意两个位置的坐标,问马最少几步可以从一个位置跳到另外一个位置。(POJ1915类似)

    该题目同样是求最优解,如果用一般的深度优先搜索是很容易超时的。如果用广度优先搜索,会消耗大量的内存,而且效率是很低的。这里,我们将尝试用深度优先搜索加动态规划的算法解决该问题。

    将该棋盘做为存储状态的矩阵。每个矩阵元素的值是该位置到初始位置最少需要的步数。初始位置的元素值为0。其他位置的元素初始化为一个很大的正整数。首先 从初始位置开始深度优先搜索,例如某次从(i1,j1)到达位置(i2,j2),如果(i2,j2)处的值大于(i1,j1)的值加1,则(i2,j2) 处的值更新为(i1,j1)+ 1,表示从(i1,j1) 跳到(i2,j2)比从其他地方跳到(i2,j2)更优,不断的进行这个过程,直到不能进行下去位置,那么最后的目标位置的值就是解。这就是一个动态规划 的思想,每个位置的最优解都是由其他能够一次跳到这个位置的位置的值决定的,而且是它们中的最小值。同时,该动态规划又借助深度优先搜索这个工具,完成对 每个位置的值的刷新,可以算是一个比较经典的深度优先搜索和动态规划的结合。该问题还需要注意一个剪枝的问题,从起始位置到目标位置的最大步数是多少?经 过计算,最大值是6。所以一旦某个位置的值是6了,就不必再将它去刷新另外的位置,从而剪去了对很多不必要子树的搜索,大大提高了效率。

    第四部分结语
    本文的主要的篇幅讲的都是理论,但是根本的目的还是指导实践。搜索,据我认为,是当今ACM竞赛中最常规、也最能体现解题者水平的一类解题方法。 “纸上得来终觉浅,绝知此事要躬行。”要想真正领悟、理解各种搜索的思想,掌握搜索的解题技巧,还需要在实践中不断地挖掘、探索。实践得多了,也就能体会 到渐入佳境之妙了。算法的优化是无穷尽的。
    展开全文
  • acm常用算法

    千次阅读 2010-07-22 01:10:00
    <br />在网上看到的,准备按着这个一项一项练习~~ 第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至...
  • ACM必备算法

    千次阅读 2013-04-30 10:07:17
    第一阶段:练经典常用算法 1.最短路(Floyd、Dijstra,BellmanFord) 2.最小生成树(先写个prim,kruscal要用并查集,不好写) 3.大数(高精度)加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写...
  • acm常见算法及例题

    2015-04-19 15:48:00
    1 acm常见算法及例题 2 3 初期: 4 一.基本算法: 5 (1)枚举. (poj1753,poj2965) 6 (2)贪心(poj1328,poj2109,poj2586) 7 (3)递归和分治法. 8 (4)递推. 9 (5)构造法.(poj3295) ...
  • ACM算法训练

    千次阅读 多人点赞 2019-09-14 13:36:57
    一位高手对我的建议:一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的 ,主要时间是花在思考算法上,不是花在写程序与debug上。 下面给个计划你练练:第一阶段: 练经典常用算法...
  • ACM必备算法列表

    2015-03-02 10:04:10
    第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Floyd、Dijstra,...
  • ACM常用算法汇总

    2016-03-20 18:13:01
    转自: 点击打开链接 简单列了一点 1.1 基本数据结构 1. 数组 2. 链表,双向链表 3. 队列,单调队列,双端队列 4. 栈,单调栈 ...1.3 高级数据结构 1. 树状数组 2.
  • ACM算法知识点

    2016-03-03 10:38:06
    POJ上的一些水题(可用来...(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094) 初级:一、基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4
  • ACM常见算法分类

    2015-12-05 09:12:39
  • ACM算法指南

    2017-04-28 20:37:20
    ACM主要算法 ACM主要算法介绍 初期篇 一、基本算法 (1)枚举(poj1753, poj2965) (2)贪心(poj1328, poj2109, poj2586) (3)递归和分治法 (4)递推 (5)构造法(poj3295) (6)模拟法(poj1068, poj2632, poj
  • 转:ACM搜索算法总结

    2014-09-02 18:53:01
    搜索是ACM竞赛中的常见算法,本文的主要内容就是分析它的 特点,以及在实际问题中如何合理的选择搜索方法,提高效率。文章的第一部分首先分析了各种基本的搜索及其各自的特点。第二部分在基本搜索方法的基础上提出 ...
  • ACM算法分类(poj)

    2014-09-22 12:27:56
    article/ACM_ICPC/11777 OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094) 初期: 一.基本算法:   (1)枚举. (poj1753,poj2965)  
  • ACM参考算法

    2013-05-15 18:37:40
    经典训练参照,不解释了,很好~  1.图论  2.数据结构  3.搜索  4.动态规划  ...=========================...基本算法:  (1)枚举. (poj1753,poj2965)  (2)贪心(poj1328,poj2109,po
  • 搜索是ACM竞赛中的常见算法,本文的主要内容就是分析它的 特点,以及在实际问题中如何合理的选择搜索方法,提高效率。文章的第一部分首先分析了各种基本的搜索及其各自的特点。第二部分在基本搜索方法的基础上提出 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,371
精华内容 4,148
关键字:

acm高级算法