1）BFS广度优先搜索：给定源节点s，生成广度优先搜索树广度优先搜索树中从节点s到节点v的简单路径对应的就是s到v的最短路径（边数最少的路径）广度优先：将已发现节点与未发现节点之间的边界（灰色节点），沿其广度方向向外扩张 1 #include<stack>2 #include<vector>3 #include<queue>4 #include<algorithm>5 6usingnamespace std;7#define INF 999999998#define NIL -19int n; 10int g[1000][1000]; 11struct Node 12{ 13int colo...
spfa：看了一下，感觉和bfs挺像的，不同的是bfs到达的点只添加一次，spfa算法就是只要能到且不在队列中的都重新添加进去，然后在进行松弛操作;Dijkstra：先确定一个要求的点，然后每次找到一个距离这点最近的点，通过这个最近的点来松弛其他和要求的点最近的路径；folyd：最好理解的，三次循环，最外层的循环是可以经过的中间的点，这个算法处理后，可以求出任意两点的最短路径； 原文：http://www.cnblogs.com/huangdao/p/7967227...
读完本文，你可以去力扣拿下如下题目：384.打乱数组-----------我知道大家会各种花式排序算法，但是如果叫你打乱一个数组，你是否能做到胸有成竹？即便你拍脑袋想出一个算法，怎么证明你的算法就是正确的呢？乱序算法不像排序算法，结果唯一可以很容易检验，因为「乱」可以有很多种，你怎么能证明你的算法是「真的乱」呢？所以我们面临两个问题：什么叫做「真的乱」？设计怎样的算法来打乱数组才能做到「真的乱」？这种算法称为「随...
这两天在做百度前端技术学院的题目，其中有涉及到寻路相关的，于是就找来相关博客进行阅读。看了Create Chen写的理解A*寻路算法具体过程之后，我理解A*算法的原理，不得不说作者写的很好，通熟易懂，图片也做的很好，可见作者在这上面是花了心思的。如果让我写，我是写不来这么好的。唯一的不足就是，因为我学的是js，因此最后给我的源码我是用不了的......因此才有自己写一篇的打算，方面学习js人的学习。然而前面的描述我就借用他...
Dijkstra算法1.定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余...
写代码会遇到整数除法需要上取整的情况。1. 整数除法的话，可以自己写^_^ 1 #!/bin/bash2 3 num=101 ##被除数4 pre=10 ##除数5 6##线上取整7 res=$[(num+pre-1)/pre]8echo $res910##整数除法默认是向下取整 11 res=$[num/pre] 12echo $res 2. 或者可以根据使用的语言提供的方法 比如c++ math.h头文件中有提供内置方法:1round 2floor 3 ceil 原文：http://www.cnblogs.com/xudong-bupt/p/7355842.html
二分查找 这些天深刻的体会到了巩固知识的重要性。对数据结构和算法的学习有一年的时间，然后搁置了一年，最后发现都忘记了。 不过还好不是失忆，看了之前做过的笔记，还是能回想起来的。 现在想在写一遍，算是对本子上的笔记做一个备份，更重要的是加深我的印象。 首先说一下二分查找的思想：假设数据是按升序排序的，对于给定值val，从序列的中间位置开始比较。 ...
#逻辑回归算法是一个二分类的算法，但是通过变形可以解决多分类的任务#逻辑回归将数据的特征转变为数据的发生概率，然后与阈值作比较，判断是0还是1，所以也可以叫做回归算法import numpy as npimport matplotlib.pyplot as plt#定义概率转换函数sigmoid函数def sigmoid(t): return 1/(1+np.exp(-t))x=np.linspace(-10,10,100)y=sigmoid(x)plt.figure()plt.plot(x,y,"r",label="Sigmoid")plt.legend(loc=2)plt.show()#定义逻辑...
2014.07.07 15:47简介： 给定N个矩阵，A1、A2、...、An，如果相邻矩阵的维度都满足相乘条件，如何组织这n-1次乘法的顺序，使得总共的乘法次数最少？描述： 根据矩阵乘法的定义，如果矩阵X的维度是aXb，矩阵Y的维度是bXc。那么XY相乘需要的乘法次数是aXbXc。 这道题目是典型的动态规划问题。从使用者的角度来看，动态规划问题通常的应用情景主要有两个特点： 1. 暴力搜索能够得出答案，但速度实在太慢。如果用空间换...
动态规划算法概述 动态规划（dynamic programming）1是一种与分治方法很像的方法，都是通过组合子问题的解来求解原问题。不同之处在于，动态规划用于子问题重叠的情况，比如我们学过的斐波那契数列。在斐波那契数列的求解问题中，我们经常要对一个公共子问题进行多次求解，而动态规划算法，则对每个子问题只求解一次，将其解保存在一个表格中，从而避免了大量的冗余计算量。 动态规划算法常用于寻找最优解问题（optimization pro...
从右上角开始搜索，当前的元素map[x][y]和要搜索的数n有如下可能：map[x][y]==n --> 返回truemap[x][y]>n --> 向左移动map[x][y]<n --> 向下移动 搜索过程例子： AC代码：import java.util.Scanner;publicclass Main {publicstaticvoid main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int k=sc.nextInt();int x[][]=newint[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){...
1 SAT问题描述命题逻辑中合取范式 (CNF) 的可满足性问题 (SAT)是当代理论计算机科学的核心问题, 是一典型的NP 完全问题.在定义可满足性问题SAT之前，先引进一些逻辑符号。 一个 SAT 问题是指: 对于给定的 CNF 是否存在一组关于命题变元的真值指派使A为真. 显然,如A为真,则CNF的每个子句中必有一个命题变元为1(真)。2 遗传算法遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法...
心血来潮把GA_TSP问题用C++封装起来搞了一遍，期间真是收益不小。主要是用STL中的vector和list，结构体赋值中遇到了一些难点，原谅我自己是一棵白菜。 选择方法：用种群前面最优的20%代替后面的20%进行淘汰(当然这个比例可以自己拟定，修改代码中得pm_即可)。变异方法：交换一个路径上随机产生的两个城市。交叉方法：三交换启发交叉(THGA)。 genticTsp.h 代码如下： 1#ifndef GENTIC_TSP_H_2#define GENTIC_TSP_H_3 #include <iost...
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stdio.h> #include<stdlib.h> usingnamespace std; #define N 500 int n1, n2, ans; int result[N]; bool state[N]; bool map[N][N];bool find(int x) {for (int i = 1; i <= n2; ++i){if (map[x][i] && !state[i]){state[i] = true;if (result[i] == 0 || find(result[i])){result[i] = x;returntrue;}}}returnfalse; } int hungary() {for (int i = 1; i <= n1; ++...
这篇我们继续扯淡一下鸡尾酒排序，为了知道为啥取名为鸡尾酒，特意看了下百科，见框框的话，也只能勉强这么说了。 要是文艺点的话，可以说是搅拌排序，通俗易懂点的话，就叫“双向冒泡排序”，我想作为码农的话，不可能不知道冒泡排序，冒泡是一个单向的从小到大或者从大到小的交换排序，而鸡尾酒排序是双向的，从一端进行从小到大排序，从另一端进行从大到小排序。从图中可以看到，第一次正向比较，我们找到了最大值9. ...