优化基础3——最短路径算法和蚁群算法

时间：2023-07-18 22:22:26浏览次数：60

标签：知乎蚁群路径最短算法 zhihu com

1. 复习了一下迪杰斯特拉和弗洛伊德算法

具体参考[最短路径问题]—Dijkstra 算法最详解 - 知乎 (zhihu.com)

Floyd算法详解通俗易懂 - 知乎 (zhihu.com)

迪杰斯特拉解决不了负边权问题，假如确定了一个点2，将他加入了visited集合

此时有一个点3到点2的边是负边权，实际权重更小了，但是该算法已经无法更新点2

参考chatgpt复现了c++版本的两个算法，关于有向图，无向图的存储方式进一步掌握

2. 学习蚁群算法，感觉关键在于信息素这一概念，信息素是如何影响下一步的选择，以及信息素如何在所有ants走完一遍后更新

蚁群算法（Ant Colony Optimization） - 知乎 (zhihu.com)

一文搞懂什么是蚁群优化算法(Ant Colony Optimization, ACO)【附应用举例】 - 知乎 (zhihu.com)

蚁群算法（ACO）：C++实现TSP问题 - 知乎 (zhihu.com)

标签：知乎,蚁群,路径,最短,算法,zhihu,com
From： https://www.cnblogs.com/sun-secretbase/p/17564295.html

2023-07-18：给你一个正整数数组 nums，请你移除最短子数组（可以为空），使得剩余元素的和
2023-07-18：给你一个正整数数组nums，请你移除最短子数组（可以为空），使得剩余元素的和能被p整除。不允许将整个数组都移除。请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回-1。子数组定义为原数组中连续的一组元素。输入：nums=[3,1,4,2],p=6。输......
文心一言 VS 讯飞星火 VS chatgpt （62）-- 算法导论6.5 1题
文心一言VS讯飞星火VSchatgpt（62）--算法导论6.51题一、试说明HEAP-EXTRACT-MAX在堆A=(15，13，9，5，12，8，7，4，0，6，2，1)上的操作过程。文心一言：HEAP-EXTRACT-MAX是堆排序算法中的一部分，用于从堆中提取最大值并保持堆的性质。下面是在堆A=(15,13,9,5,12,8,7,4,0,6,2,1)上执......
数据结构与算法：图有哪些关键核心知识点
图是一种复杂的数据结构，它由顶点和边组成，可以表示任意两个数据元素之间的关系。图有以下一些基本概念和术语：图可以分为无向图和有向图，根据边是否有方向。图可以分为简单图和多重图，根据边是否重复或自环。图可以分为完全图和非完全图，根据任意两个顶点之间是否存在边或弧。图......
判环算法01
判环算法01检验链表是否有环//判断环publicbooleanhasCycle(ListNodehead){ListNodep1=head;//乌龟ListNodep2=head;//兔子while(p2!=null&&p2.next!=null){p1=p1.next;p2=p2.next.next;......
RAW算法处理之BLC(Black level Correction黑电平校正)
BL产生的原因暗电流暗电流（darkcurrent），也称无照电流，指在没有光照射的状态下,在太阳电池、光敏二极管、光导电元件、光电管等的受光元件中流动的电流，一般由于载流子的扩散或者器件内部缺陷造成。目前常用的CMOS就是光电器件，所以也会有暗电流，导致光照为0的时候也有电压输出。如......
LCA 离线tarjan算法
tarjan算法是离线算法，它必须先将所有的要查询的点对存起来，然后在搜的时候输出结果。tarjan算法很经典，因为算法的思想很巧妙，利用了并查集思想，在dfs下，将查询一步一步的搜出来。伪代码如下：可以看到，对于我们已经保存好的查询，假设为(u,v)，u为此时已经搜完的子树的根节点，v的位置就只有两种......
牛客网-游戏地图路径
1.题目读题游戏中心的运营小伙伴最近接到一款新游戏的上架申请，为了保障用户体验，运营同学将按运营流程和规范对其做出分析评估。经过初步了解后分析得知，该游戏的地图可以用一个大小为n*n的矩阵表示，每个元素可以视为一个格子，根据游戏剧情设定其中某些格子是不可达的(比如建......
同余最短路的转圈法
学习自Alex_Wei的博客。同余最短路模板题：[国家集训队]墨墨的等式。已知长为\(n\)的序列\(a\)。对于不定方程\(\sum\limits_{i=1}^na_ix_i=b\;(x_i\ge0)\)，问有多少\(b\in[l,r]\)可以使得方程有解。\(n\le12\)，\(a_i\le5\times10^5\)，\(l,r\le10^{12}\)。本文默认取模......
算法练习-day20
二叉树669.修剪二叉搜索树题意：给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low,high]中。修剪树不应该改变保留在树中的元素的相对结构(即如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案 ......
Multi Paxos 、Raft 、ZAB 算法
参考：凤凰架构：https://icyfenix.cn/distribution/consensus/raft.html 一、将共识问题分解为三个问题1.选主《https://www.cnblogs.com/suBlog/p/17554677.html》BasicPaxos的活锁问题，两个提案节点互不相让地争相提出自己的提案，抢占同一个值的修改权限，导致整个系统在持续......

优化基础3——最短路径算法和蚁群算法

相关文章

赞助商

阅读排行