Dijkstra算法

Dijkstra算法使用了广度优先搜索解决赋权有向图(或无向图)的单源最短路径问题。 输入 该算法的输入包含了一个有权重的图G,以及G中的一个起点S,V是途中所有顶点的集合,E是图中所有顶点的集合。图中的边是两个顶点所形成的元素对,(u,v)表示顶点u到顶点v的边,w(u,v)表示这条边的权重。 输出 该算法能够在一个图中,找到从起点到任何其他顶点的最低权重路径(最短路径)。 流程 这个算法是通过为每个顶点v保留当前为… 阅读全文

在LaTeX环境下使用BibTeX进行文献引用(MiKTeX软件)

手动管理参考文献总是令人抓狂,参考文献的样式需要小心编排,还需要按照引用顺序对参考文献进行排序和编号,以致添加、删除或者修改引用文献后都需要进行大量的修改,耗费大量的时间和精力。 使用BibTeX进行文献管理可以有效地提高这项工作的效率,下面以MiKTeX软件为例进行说明。 使用BibTex的好处是: 自动调整参考文献样式。 在正文中直接对参考文献别称进行引用,不需要在正文中来回修改引用号。 自动按照引用顺… 阅读全文

感知器基础

假设集 一般算法 口袋算法 MATLAB 程序 function [w, update_times] = my_perceptron(x, y, eta) % 基本的感知器算法,在没有错分样本时停止 % x 输入 x向量 % y 输入 y向量 % eta 输入 w <- w + eta*yt*xt % w 输出 权重 % update_times 输出 w更新次数 % 初始化参数和变量 [dataSetSize, xSize] = size(x); w = zeros(xSize,… 阅读全文

机器学习的类别

监督学习 从训练资料中学到或者建立一个模式,并依此模式推测新的实例。训练资料是由输入数据和预期输出数据组成。模式的输出可以是一个连续的值(称为回归分析)或者分类标签(称为分类)。 非监督学习 没有给定事先标记过的训练示例,自动对输入的数据进行分类或分群。 强化学习 智能体以“试错”的方式进行学习,通过与环境进行交互获得的奖赏指导行为,目标… 阅读全文

调度的三种类型

活动调度 在活动调度基础上通过更改机器上的加工顺序,使至少一个工序可以提前加工,必然导致其他工序完成时间推迟。也就是说,在活动调度中,在保留可行性的前提下,没有任何工序可以插入加工时间表前面的空隙中。 半活动调度 在半活动调度基础上更改机器上的加工顺序,使至少一个工序可以提前加工。 无延迟调度 存在一个工件等待加工时,不存在可用的处于空闲的机器。注意,最优解一般不在无延迟调度内。… 阅读全文

基于POX交叉的遗传算法求解流水车间调度(J-Shop)问题一

对于流水车间调度问题,n个工件在m台设备上加工,已知每个工件每个工序使用的机器和每个工件每个工序所用时间,通过决策每个机器上工件的加工顺序和每个工序的开始时间,使完成所有工序所用时间(makespan)最小。具有下列约束: 不同工件的工序之间没有顺序约束。 某个工序一旦开始加工就不能中断。 每个机器在某一时刻只能加工一个工序。 机器不发生故障。 本文使用基于工序的编码方式,轮盘赌选择… 阅读全文

单纯形法:格式与迭代

格式 目标函最大化 所有约束都是等式(变量的非负限制除外),并且具有非负右端项。 所有的变量都是非负的。 将不等式转化成带有非负右端项的等式约束 为了把(≤)不等式约束转换成等式约束,在约束的左端添加非负的松弛变量。为了把(≥)不等式约束转换成等式约束,在约束的右端添加非负的剩余变量。 e.g. 将约束6x_1+4x_2≤24转换成6x_1+4x_2+s_1=24,s_1≥0,其中s_1 是松弛变量。 将约束x_1+x_2≥800转换成x_1+x_2−s_2… 阅读全文

什么是机器学习?

什么是机器学习? 假设用P来评估计算机程序在某任务类T上的性能,若一个程序通过利用经验E在T任务上获得了性能改善,则我们就说关于T和P,程序对E进行了学习。 上图中,数据是经验E的来源,能力表示在任务T上的性能改善,机器学习利用从数据中计算得来的经验E来改善任务T上的性能(由P评估)。 什么时候使用机器学习(机器学习的要素)? 存在一些可被学习的模式 模式无法通过编程定义 存在足够的关于这个模式的数据… 阅读全文