Asynchronous dynamic programming (ASYNCHDP) 算法求最短路径

本文代码点击这里下载。 动态规划方法 如果节点x位于s到t的最短路径上,那么x到t的路径也必须是x和t之间的最短路径。这种“分而治之”(devide-and-conquer)的思想,被称为动态规划(dynamic programming)。 异步动态规划方法(ASYNCHDP) 记节点i到目标节点t的最短路径为h^* (i)。从i到t的经过j(是i的邻居)的最短路径可通过f^* (i,j)=w(i,j)+h^*… 阅读全文

使用ABT(The asynchronous backtracking algorithm)算法求解四皇后(4-queens)问题

本文代码点击这里下载。 将4个皇后放入4×4的棋盘中,修改4个皇后的位置,使他们不能“立即”攻击对方。这里我们假设4个皇后被放置在不同的行中,仅能修改4个皇后的列的位置。 假设我们4个皇后的id依次是A1,A2,A3和A4,它们的优先级依次是1,2,3和4,它们的位置依次是(1,1),(2,1),(3,1)和(4,1)。算法仅能修改它们所在的列。最终使它们无法一步攻击彼此。 循环1. A1发Ok?信号给A2,A3和A4,A2发Ok?信号… 阅读全文

柔性作业车间调度问题介绍 (Flexible Job-shop Scheduling Problem, FJSP)

调度问题是制造流程规划和管理中最关键的问题之一。 这个领域最困难的问题之一是作业车间调度问题(Job-shop Scheduling Problem, JSP),该问题中,一组机器需处理一组工件,每个工件由一系列具有先后顺序约束的工序形成,每个工序只需要一台机器,机器一直可用,可以一次处理一个操作而不会中断。决策内容包括如何对机器上的工序进行排序,已优化给定的性能指标。 JSP的典型性能指标是完工时间 (makespan),即完成… 阅读全文

数组和关联数组 – Linux Shell 脚本

数组借助索引将多个独立的数据存储为一个集合。普通数组只能使用整数作为数组索引。关联数组可以使用字符串作为数组索引。 下面是一个普通数组和关联数组的示例: #!/bin/bash array_var=(apple grape banana); # 定义普通数组 echo ${array_var[0]}; # 取出索引为0的元素 echo ${array_var[*]}; # 取出所有元素 array_var[3]=peach; #… 阅读全文

Voronoi图路径规划 (许松清, 2005)

本文学习了以下文章中的方法: 许松清,吴海彬,林宜,高洪张,陈天炎. 基于Voronoi图法的移动机器人路径规划[J]. 中国工程机械学报,2005,(03):336-340. 在Voronoi路径规划代码下载本文代码。 维诺图 用X表示一个距离函数为d的空间。令K为一个指示集合,(P_k ),k∈K为空间X的一个非空子集的有序元组。对应于P_k 的R_k,称为沃洛诺伊元胞… 阅读全文