十七 一共十七划

WRITING

文章

题解-做菜顺序-排序,贪心,前缀和,一点点证明

Problem: 1402. 做菜顺序 思路 注意到没有要求顺序,先排序 朴素思想是将大的数越往后放越好,但对于负数,虽然也是越大越往后放越好,但其有可能增加答案,也有可能减少答案,需要一些证明 解题方法 注意到对于负数的选取一定是连续而非跳跃的:假设存在$[a_{i-1},a_i,a_{i+1}].a_i<a_{i+1},$数组,三者均小于0,假如一定要取两个元素,(这种假定的含义是我需要后面的正数有足够的倍数,期望前面提供倍数的负数(代价)最小),选取元素$a_{i-1},a_{i+1}$代价大于选取$a_i,a_{i+1}$ 推广可知我们会选取所有的正数和部分负数,且负数在排序后的数组中是连续的,并且和正数部分相连 实际上是求一个子数组的这个操作最大能多大,可以枚举每一次从哪选,结束一定是在最大的数结束 然后简化:注意到相关操作实际上是对于之前结果再加上一次已经遍历的数,所以可以将其转化为一遍扫描的方式 时间复杂度, $O(nlogn)$ Code class Solution: def maxSatisfaction(self, satisfaction: List[int]) -> int: satisfaction.sort(reverse=True) #方便操作 res=0 pre=0 now=0 for num in satisfaction: pre+=num now+=pre res=max(now,res) if now<0: break #之后一定小于0 return res

↗

题解-移动机器人-数组计算的三种思考方式方式(动态规划,贡献,前缀和)与相关证明

Problem: 2731. 移动机器人 前述条件 碰撞和1503. 所有蚂蚁掉下来前的最后一刻类似,注意到对于身份没有要求,所以可以直接认为两个机器人碰撞是交换了二者的身份,也可以认为是穿过去了 因此能够得到机器人的最终位置,为了方便计算,我们排序 数据量为$10^5$,暴力求解不现实 以下是三种常用的解决方法,这三种思路最开始的进入方式不同,但是都能得出正确结果 两种对于距离的计算方法 算法的时间复杂度均为$O(n)$ 动态规划 思考方式与证明 假设已经计算出来了$a[i]$之前所有的机器人两两之间距离之和为$s$ 增加一个元素$a[i]$,观察其和之前的所有机器人之间的距离之和,能够发现 实际上就是与之前的每个元素计算距离 $a[i]$与$a[0],a[1]….,a[i-1]$之间的距离实际上分别是是$a[i-1]$与$a[0]….,a[i-1]$之间的距离加上$a[i]$与$a[i-1]$之间的距离,共$i$个 上述结论可以推导: 设$distance[i]$表示$a[i]$和$a[0],a[1]….,a[i-1]$之间的距离之和,有 $$ distance[i]=i*a[i]+distance[i-1] \distance[0]=0 $$ 代码 可以看出来这个公式只与前一个状态有关,因此可以优化空间 class Solution: def sumDistance(self, nums: List[int], s: str, d: int) -> int: mod=1000000007 n=len(nums) for i,a in enumerate(s): nums[i]+=d if s[i]=='R' else -d nums.sort() res=0 distance=0 for i in range(1,n): distance+=i*(nums[i]-nums[i-1]) #这个方法对于只int的话4*(10**9)会超范围 distance%=mod res+=distance return res%mod 贡献距离法 思考方式 对于这种什么什么之和的问题可以考虑计算每个片段对结果的贡献 在这个题目之中片段就是每个元素之间的距离,我们需要计算的就是这段距离在结果中出现了多少次 为了方便理解将每次计算距离视为两点之间的连线,看片段上线的数目就知道这个片段的使用次数 从$a[0]-a[1]$这一的角度来看:从$a[0]$连出去了$n-1$条线,每条线都经过了$a[1]$,所以得出$a[0]-a[1]$段的贡献是$n-1$ 从$a[1]-a[2]$的角度来看,$a[1]$连出去的$n-2$也就是$(n-i-1)$条线覆盖了$a[1]-a[2]$ 但还不够,注意到$a[0]$发出去的线只有一条落在了$a[1]$上,剩下的线也覆盖了$a[2]$ 希望确切地知道此时到底有多少条线覆盖了这段距离 证明 设$f[i]$表示$a[i]$到$a[i+1]$这段距离对结果的贡献次数 同时可知$f[i]$也表示此时距离上面的线段数量 从a[i]发出的所有向右的线都会做贡献,这个次数为$n-i$ 发现$a[i]$之前的线段,也就是参与了$f[i-1]$计算的线段,有一部分落在了$a[i]$上,剩下的部分继续参与$f[i]$的计算 可知落在$a[i]$上的线段实际上是a[i]发出的指向左边的线段,其数量为$i$ 综上 $f[0]=n-i\f[i]=(f[i-1]-i+n)-i=f[i-1]-2*i+n$ $$\displaystyle res=\sum_{i=0}^{n-2}f[i]*(a[i+1]-a[i])$$ Code 可以看出只与前一个状态有关,进行空间优化 代码为了方便对于$f[i]$计算的是$a[i+1]$到$a[i]$ class Solution: def sumDistance(self, nums: List[int], s: str, d: int) -> int: mod=1000000007 n=len(nums) for i,a in enumerate(s): nums[i]+=d if s[i]=='R' else -d nums.sort() pre=0 res=0 for i in range(n-1): pre=(pre+n-2*i-1)%mod res=(res+(nums[i+1]-nums[i])*pre)%mod return res 前缀和的形式化证明 下面是灵神的证明方式,与上面的证明相比更加数学,如下 $ (a[i]−a[0])+(a[i]−a[1])+⋯+(a[i]−a[i−1])=i⋅a[i]−(a[0]+a[1]+⋯+a[i−1])\$ $(a[0]+a[1]+⋯+a[i−1])$可根据前缀和求 下面是灵神的代码

↗

翻译:Efficient parallel branch-and-bound approaches for exact graph edit distance problem

是一个作业,但是是自己第一次这么看论文,所以发一下 来自链接 摘要 图编辑算法(Graph Edit Distance ,GED)是一种在图匹配领域广泛使用的方法.它通过计算将一个图转化成另一个图的最小编辑成本来衡量两个图的相似性或差异性.这个过程看起来很简单,但是是NP难问题并且非常耗时,因为它的搜索空间是指数级增加的.一个解决这个问题的最优算法是分支限界法(Branch and Bound，B&B),通过对搜索空间进行隐式枚举而不是而不是基于剪枝技术的全部枚举,来减少探索整个搜索空间的实践.然而当处理大型问题实例的时候,B&B算法探索整个搜索空间所需要的时间仍然太长了,它在此时依然是不够有效的.为了解决这个问题,在本文中我们提出了三种基于共享内存的B&B并行方法来利用多核CPU处理器.第一种是一种工作窃取的方法,多个B&B实例并发搜索单个搜索树,比顺序版本最多快24倍.其次是一种基于树的方法,由独立的B&B实例同时搜索搜索树的多个部分,能够提速28倍,最后,由于GED问题的不规则特性,提出了两种负载均衡策略来保证并行进程之间的负载均衡,达到了令人惊叹的300倍,所有的实验都在知名的数据集上进行过了. 1. 介绍 图编辑算法(Graph Edit Distance ,GED)是一种在图匹配领域广泛使用的方法来计算两个图之间的最小距离.GED算法的目的是计算两个图之间的不相似的总和.换句话说,它代表将一个图编辑成另一个图所需要的最优操作集的成本1.允许的操作包括插入,删除和增加,这三种操作可以运用在顶点或者边上.这个问题由于其NP难特性而被认为是非常具有挑战性的2,这意味着计算两个图之间最小距离的时间复杂度随着顶点数量的增加呈指数级增长.GED的重要性来自于它的多种使用用例.它可以用于精确匹配也可以用于能容忍一定错误的非精确匹配.并且,GED可以用于多种领域3,特别是在与模式识别相关的领域,比如手写识别456,个人识别和认证(例如指纹识别)7,文档分析589,和图数据库搜索10.它也可以被用于机器学习,最近邻居分类和数据挖掘领域.5 为了计算两个图之间的最佳编辑距离,蚊香3经常使用的基于A*11的搜索算法.然而,这种方法需要大量内存资源,这使得其不能被用于处理大型的图.分支限界法(B&B)是一种广为人知的技术,它通过智能枚举搜索空间来解决最优化问题.这个方法用两个组件,分支(branching)和界限(bounding),将搜索空间建模成一棵树.分支是一个递归的过程,它将一个给定问题的搜索空间划分成多个更小的子问题,并对这些子问题用同样的方式处理,知道找到解决方法.在分支过程结束后,界限操作符评估每一个生成的子问题是否可能包含好的解决方案.B&B算法使用多种技术(消除和选择)来避免探索没有最优解可能的子问题(分支)并家扩搜索过程.由于GED问题的复杂性,它对于一般图来说是NP难问题2,B&B算法需要很长的实践去找到最优解,特别是在解决大型图问题的时候.为了客服这个缺点,我们认为并行计算是一个减少这类问题的运行时间的有趣的方法. 在这片论文之中,我们研究了利用单台计算机的计算资源所带来的影响和可能的收益.事实上,现在的的大部分计算机从硬件上来看都是并行的,能够提供可观的计算能力,尽管在大部分情况下都没能被利用.因此.也为了评估使用并行方法可能得到的收益,我们提出了几种B&B算法.这里的目的是评估每一个并行方法在减少执行时间和有效探索整个搜索空间的影响和行为.我们给出的方法可以归类成高级并行化,其中多个B&B算法的实例同时探索搜索空间. 本文提出了两个并行算法,第一种是基于工作窃取策略,用以在不额外增加内存使用的条件下加快对搜索树的顺序搜索.因此,我们用多个B&B实例同时探索同一颗存储在共享内存空间中的搜索树,所有并行的B&B实例都可以对这个搜索树进行读/写操作.在参考数据集上使用16核CPU的实验显示,相对于顺序版本,速度提升24倍.为了更有效地探索这个搜索空间,也为了研究多样化的影响,我们提出了第二个B&B算法.后者用基于树的方法表示,用多个独立的B&B实例并行地探索整个搜索树的多个部分.因此,更新上界(UB),这最终能够改善一定复杂度.这个算法基于主从策略(Master-Worker),主节点将搜索树分成多个B&B实例,也就是工作者(Workers),在这之后,每一个工作者在自己的内存空间之中构建自己独有的搜索树,进程间唯一共享的信息就是更新的上界的值,这在每一次一个更优路径被发现的时候更新.这个算法得到的结果显示多样化探索过程对性能产生了积极的影响,相比于顺序B&B实例,提速了约28倍.然而,因为搜索树中的子问题的负载不均衡,许多工作者很快地结束了工作(空闲),然而其他会需要运行很长的时间.解决GED问题的负载平衡策略的影响在Abu-Aisheh等人的研究12，13中没有得到很好的研究.因此,我们提出了两种原创的负载均衡策略来避免工作者的共线.我们的第一种负载均衡策略包括将主节点当做负载均衡器,听过改变它的搜索策略来保证子问题的大量可用性.这个避免空闲的想法就是给所有的并行工作者读写权限来让它们在自己的工作池为空的时候从负载均衡器的工作池之中选取一个子问题.第二种保证工作者之间的负载平衡的方法是将前两个并行算法结合起来.这里的想法是允许工作者在本地进行$k$次迭代,接着将它们自己本地工作池整合进一个共享的全局工作池.用参看数据集刨出来的结果显示了将多样性和负载均衡结合起来带来的好的影响,并且,增加负载均衡算法能够将基于树的并行算法提升高达11倍. 本文余下的内容总结如下.在第二节提出了一些基础的有关GED的符号和定义,在第三节中,我们讨论相关的工作.在第四节描述了串行B&B算法和它的组成,在第五节我们详细介绍我们提出的并行B&B算法和负载均衡策略.在第六节报告计算结果,最终,在第七节提出了结论和展望. 2.问题定义 在接下来的部分,我们首先定义了一些基本的概念接下来去正式地定义GED问题 2.1图(Graph) 一个图是一个用于建模对象之间的成对关系的结构.14,它包含了一组由一组边连接起来顶点, 正式定义中,一个带标签的图可被表示为$G=(V,E,\alpha,\beta)$,在其中 $V={v_1,v_2,….,v_n}$,表示包含n个顶点的集合 $E={e_1,e_2,…,e_m}$.表示包含个边的集合$(E\subseteq V \times V)$ $\alpha$是顶点的标记函数，也就是将每个顶点映射到一个标记的函数，表示为:$\alpha : V \to L_V$ $\beta$是边的标记函数，也就是将每个边映射到一个标记的函数，表示为:$\beta:V\to L_E$. $L_V$和$L_E$被限制为可以由一组整数描述的标签,向量空间$R^n$或者符号标签 在这篇论文之中,我们考虑简单的无向无环标记图. 2.2 GED操作 在GED问题之中,一个将图$g_1$转换成图$g_2$的编辑路径由一组图的编辑操作组成.每一个编辑操作对顶点,边或者顶点和边执行一次操作.在本文之中,我们采用一种以顶点为中心的方法,其变形都是在顶点上进行的,而其中隐含了对边的操作.因此,只有一下三种基本备案及操作是被允许的:插入($insertion$),删除($deletion$)和替换($substitution$) 我们描述一个顶点$v_i \in V_1$来自于图$g_1$,以及领一个顶点$u_j \in V_2$来自于图$g_2$,我们表示为 $v_i\to u_j:$将顶点$v_i$替换为$u_j$ $v_i\to \epsilon:$,顶点$v_i$从$g_1$之中删除 $\epsilon \to u_j:$顶点$u_j$加入到$g_2$之中 2.2.1隐含的边操作 在以顶点为中心的算法之中,对于边的编辑操作是隐含的,事实上,一个边的替换,删除或者增加取决于它的相关顶点的编辑操作5.让我们考虑图$g_1$之中的两个顶点$v,v’$,和另外两个顶点$u,u’$在图$g_2$之中.如果我们在顶点$v$和$v’$进行如下的两个编辑操作${v\to u}$和${v’\to u’}$.可以分别区分出三种边的隐含操作: 如果在$g_1$中$v$和$v’$之间存在一个边$e_1=(v,v’)$,$g_2$也存在一个边$e_2=(u,u’)$连接$u$和$u’$,那么$e_1$就被$e_2$替换掉,表示为$e_1 \to e_2$ 如果在$g_1$中$v$和$v’$之间存在一个边$e_1=(v,v’)$,而$g_2$之中没有连接$u$和$u’$的边,那么$e_1$就在$g_1$之中删除,表示为$e_1 \to \epsilon$ 如果如果在$g_1$中$v$和$v’$之间不存在边而$g_2$存在一个边$e_2=(u,u’)$,那么$e_2$就被加入到了$g_1$之中,表示为$\epsilon \to e_2$ 注意当一个顶点从$g_1$之中删除的时候,与它相连的所有边都被自动删除,类似地,吐过一个顶点被插入进$g_1$所有在$g_2$之中预期相连的边会被插入,如果这个边的另一个端点已经存在于$g_1$之中 2.3成本函数 在GED之中,成本函数是一个重要的组成部分.成本函数为每一个对于边或者顶点的操作分配一个值(成本).因此,图编辑的成本分配影响着最优编辑路径.成本函数提供了一个将与对象相似性有关的领域信息融入进来的有效方法.对于一个特定操作$o$的成本$c(o)$实在底层标签字母表的层面定义的,三种编辑操作的成本给出如下 $c(u\to\epsilon)=\theta$ $c(\epsilon\to v)=\theta$ $c(v \to u)=c(u\to v)=\beta$ 我们应该注意如果这两个顶点或者边的拥有相同便签的时候,其替换成本为0. 2.4图编辑距离 让$g_1=(V_1,E_1,\alpha_1,\beta_1)$和$g_2=(V_2,E_2,\alpha_2,\beta_2)$为源图和目标图,分别地,$g_1$和$g_2$之间的图编辑距离由$d(g_1,g_2)$表示,代表着两个图之间的差异程度.换句话说,它代表着一组将$g_1$转换成$g_2$的最优编辑集合${e_1,e_2,…,e_k}$(在成本角度上) 最终,$g_1$和$g_2$之间的图编辑距离(GED)定义为 $$\displaystyle (g_1,g_2)=min_{{e_1,e_2,…,e_k}\in\gamma(g_1,g_2)}\sum_{i=1}^k(e_i)$$ 其中$\gamma(g_1,g_2)$表示为所有的将$g_1$转化成$g_2$的编辑路径的集合.每一个路径都包含着一组编辑操作$\lambda {e_1,e_2,…,e_k}$,并且$c(e_i)$表示编辑操作$e_i$的成本5 2.5举例 我们将源$g_1$和目的图$g_2$表示在在图1之中,我们让删除和插入的操作成本为2,替换的成本为1,那么将图$g_1$编辑成图$g_2$的最优路径可以由操作四个顶点的替换得到,这意味着要替换三条边,并且删除其他的两条,完整编辑路径如下 $$\lambda(g_1,g_2)={(v_1{B}\to u_1{B}}, {(v_2{A}\to u_1{A}}, ((v_2,v_1)\to \epsilon),\ (v_3{A}}\to u_3{B}),((v_3,v_2)\to (u_3,u_2)),\ (v_4{A}\to u_4{A}),((v_4,v_1)\to (u_4,u_1)),\ ((v_4,v_2)\to \epsilon ),((v_4,v_3)\to (u_4,u_3))}$$

↗