VC实现结点间最短路径

路径最短问题一直是路径规划中的重要问题,应用到各个学科领域。最短路径的应用非常广泛,实现方式也多样化。动态规划是计算最短路径的一种有效的方式,有其独特的意义。本文主要研究利用VC++实现动态规划中的节点最短路径问题。     

基于"矩阵乘法"的网络最短路径算法

 网络最短路径问题可以作为许多实际应用问题的模型,但传统的求解算法其迭代过程复杂.本文描述了基于矩阵乘法的最短路算法,其时间复杂度与Dijkstra算法相同.在给定的一个网络图中,在不改变网络图中的最短路的条件下,删除"多余"的结点或边,可以达到简化网络图和提高求解速度的目的,从而降低计算复杂性.最后,研究了该方法在最短路径问题和旅行商问题中的应用.实例表明,这种算法与传统的动态规划技术相比,具有运算简便、易于理解的优点.     

基于单目标线性规划的穿越沙漠策略研究

单目标线性规划模型是在一组线性条件约束下,寻求某一单一目标的最优值,适用于极值问题的求解。弗洛伊德算法是一种通过动态规划的思想寻找给定的加权图中多源点间最短路径的算法。文章建立了基于背包问题的单目标线性规划模型,给出了在只有一名玩家,且事先已知游戏阶段天气状况下玩家的最优策略。通过弗洛伊德算法求解出了相应节点间的最短路径,得到了玩家的最终剩余资金。     

基于多准则遗传算法的航线规划

飞行航线规划是中小型飞机执行长途飞行任务时的重要工作。通过建立问题的多准则最短路径问题模型,提出一种多准则最短路径遗传算法求解优化飞行航线。通过理论分析证明了算法的收敛性。仿真实验验证了该算法的有效性。     

基于动态引力场的机器人路径规划研究

人工势场法对机器人进行路径规划时,存在障碍物使目标不可达、死锁和局部极小点等问题,容易导致路径规划失败,此外发现即使路径规划成功,由于斥力的存在,必定使得规划路径不是最短、最优的。针对上述问题提出一种动态引力场路径规划算法,该算法完全去掉斥力场,将引力场的大小及方向动态化,虚拟目标点动态化,不断交替寻找最优或次优方向进行避障,动态地修正路径,最后对路径进行平滑优化,规划出最短、最优的路径。该方法解决了人工势场法固有的缺陷,同时优化了规划路径的长度,仿真实验结果说明该算法具有实用性和有效性。     

基于遗传算法的驾驶员动态路径诱导研究

动态路径诱导的目的在于向道路行驶者提供基于实时交通信息的合理、高效的行驶路线,以保证车辆在路网上运行的总费用最小.将遗传算法应用于动态路径诱导,通过引入任意迪杰斯特拉算法解决了遗传算法应用于最短路径的初始种群的选择、交叉和变异问题,提出了运用遗传算法求解动态网络中最短路径问题的新方法.最后,以西安市电子地图为基础,验证了遗传算法在动态路径诱导中的有效性.该研究为交通管理控制、驾驶员出行提供了更加准确和有效的路径诱导决策辅助信息.     

机器人避障问题

研究了机器人行走的最短距路径和最短时路径的问题。最短距路径问题是采取线圆结构来求解,把复杂的路径分解求解,最后把可能短的路径通过穷举法列举出来,比较得出最短路径;最短时路径采取线圆结构通过优化,得出了最优解。     

基于热传导方程的快速路径规划算法

复杂环境中的路径规划问题一直以来在许多领域中扮演着十分重要的角色。本文将路径规划问题看做一个多目标的优化问题,基于路径的长度,能量损耗以及路径的平滑性来定义最优路径。利用热传导方程将复杂的路径规划问题转换成线性方程组的求解问题,从而可以快速地规划出一条最优路径。通过改变热传导方程的形式,本方法不仅适用于最短路径的规划,而且还适用于复杂场景中最低风险路径的规划。     

时延PCNN及其用于求解最短路径

本文在脉冲耦合神经网络(PCNN-Pulse Coupled Neural Network)的基础上,提出了时延脉冲耦合神经网络(DPCNN-Delay PCNN),并将其成功地用于求解最短路径,同时给出了基于DPCNN的最短路径求解算法.Caulfield与Kinser提出了用PCNN求解迷宫问题的方法,虽然他们的方法也可用于求解最短路径,但所需神经元的数量巨大,而本文的方法所需的神经元的数量远小于他们的方法.同时,本文的方法充分利用了DPCNN脉冲快速并行传播的特点,可迅速地求出最短路径,其所需的计算量仅正比于最短路径的长度,与路径图的复杂程度及路径图中的通路总数无关.计算机仿真结果表明,采用本文的方法,用少量的神经元就可迅速地求出最短路径.     

一种车辆路径规划的新型蚁群算法研究

通过引入变异机制和3种不同策略对蚁群算法进行了改进来提高收敛速度和寻找更优解,以满足对车辆路径规划的求解,其目标是实现车辆的路径规划,使得汽车总的行驶路程最短和所需汽车的数量最少。仿真实验表明,引入变异机制的蚁群算法能够有效地解决带有容量限制的车辆路径规划问题,提高了物流配送效率。     

Routing framework for all-optical DWDM metro and long-haul transport networks with sparse wavelength conversion capabilities

In this paper, we propose a novel routing framework for all-optical dense wavelength-division-multiplexing transport networks with sparse wavelength conversion capabilities. The routing framework includes an integer linear programming formulation to handle the static lightpath establishment problem and a novel open shortest path first protocol extension that advertises the availability of wavelength usage and wavelength conversion resources. Our routing framework addresses the limitations of the extensions presented in the literature because it also includes: 1) an efficient flooding protocol that is suitable for the dynamic nature of these networks and 2) an efficient route and wavelength computation engine that minimizes connection costs without hindering the blocking probability.     

A recursive approach for enumerating minimal cutsets in a network

This paper presents a new recursive labelling algorithm for determining all minimal cutsets in a directed network, using an approach adapted from dynamic programming algorithms for the classical shortest route problem. The algorithm produces all minimal cutsets, and uses comparison logic to eliminate any redundant cutsets. Computational experience shows that: (1) the time per cutset varies linearly with the number of nodes but decreases exponentially with the density of the graph; and (2) whereas the algorithm's performance with regard to `change in the time per cutset vs. the number of nodes' is similar to other algorithms, it appears to exhibit superior performance where the time/cutset is compared to the density of the graph     

面向高动态高空平台网络的路由协议研究

提出了一种面向高动态高空平台网络的路由协议,该协议通过按需查找方式确定高动态用户所属的高空平台,根据最短延时路由表在高空平台之间转发数据,并通过用户切换策略保证数据传输的连续性。仿真结果表明,该协议能够适应用户高速移动和频繁切换的高动态环境,具有可靠性高、延时小、路由开销小、抗毁性强等特点,为高动态高空平台网络的数据转发提供了一种可行的解决方法。     

Application of the surrogate constraints algorithm to optimal reliability design of systems

This paper presents a solution method for the reliability optimization problem of series-parallel systems which is formulated as a mixed integer nonlinear programming problem with multiple constraints. In the solution method, the optimal solution is obtained by solving the surrogate dual problem. Surrogate problems with only one constraint which appear in the optimization process are solved by a technique using dynamic programming. Some computational experiences are shown along with the comparison with an existing approach.     

A multilayer solution for path provisioning in new-generation optical/MPLS networks

This paper proposes an offline solution for global path provisioning in new-generation optical networks based on the generalized multiprotocol label switching (GMPLS) paradigm. This solution is based on a multilayer approach, which involves both the optical and the electrical layers and optimizes the network configuration and traffic routing. The proposed global provisioning solution can be easily combined with dynamic routing solutions, providing the network with the possibility of reacting promptly to traffic changes. Data flows are assumed to be structured into label switched paths (LSPs), which represent the connection in a GMPLS-based network, at any hierarchical level. The global provisioning issue is a difficult optimization problem. As a solution, we propose a new heuristic algorithm based on the shortest path computation and a mathematical programming approach, which makes use of the optimization solver CPLEX. A large computational study shows the effectiveness of the former, in terms of quality of the solutions. The advantages of the multilayer provisioning strategy are analyzed in a relevant case study by evaluating the network congestion.     

“背包问题”算法设计及分析

“背包问题”是一个典型问题．其求解也是算法设计及验证的一个热点。在此分别采用优先策略、动态规划及递归三种不同方法对“背包问题”进行求解、算法设计及验证。实践证明了三种算法的正确性。在复杂度分析中．优先策略算法的空间及时间复杂度最低,而动态规划法具有明显的优势。     

Pursuit evasion: the herding noncooperative dynamic game - thestochastic model

This article proposes a solution to the herding problem, a class of pursuit evasion problem in a stochastic framework. The problem involves a "pursuer" agent trying to herd a stochastically moving "evader" agent into a pen. The problem is stated in terms of allowable sequential actions of the two agents. The solution is obtained by applying the principles of stochastic dynamic programming. Three algorithms for solution are presented with their accompanying results     

Optimal Routing in Gossip Networks

In this paper, we introduce the Gossip Network model where travelers can obtain information about the state of dynamic networks by gossiping with peer travelers using ad hoc communication. Travelers then use the gossip information to recourse their path and find the shortest path to their destination. We study optimal routing in stochastic, time-independent gossip networks, and demonstrate that an optimal routing policy may direct travelers to make detours to gather information. A dynamic programming equation that produces the optimal policy for routing in gossip networks is presented. In general, the dynamic programming algorithm is intractable; however, for two special cases a polynomial optimal solution is presented. We show that ordinarily gossiping helps travelers decrease their expected path cost. However, in some scenarios, depending on the network parameters, gossiping could increase the expected path cost. The parameters that determine the effect of gossiping on the path costs are identified and their influence is analyzed. This dependency is fairly complex and was confirmed numerically on grid networks.     

基于点火耦合神经网络的多约束QoS路由选择算法

本文针对多约束QoS路由选择问题，将其转化为一个多约束的赋权图最短路问题，并建立点火耦合神经网络，通过在其上所具有的自动波生成和传播特性，并在自动波的传播过程中随时监督约束的满足情况，及时取消不满足约束的自动波，从而最先到达目的节点的自动波所走过的路径即为多约束QoS的最优路径。该算法具有高度的并行性，并总是获得全局最优解，所需的迭代次数相对其他算法而言也是最少的。最后本文给出了实验结果及与其他算法的比较。     

RDMSR: A reactive defragmentation with minimum spectrum route strategy for mixed grid optical network

In this paper, we propose a reactive defragmentation with minimum spectrum route (RDMSR) for the problem of route, spectrum, and modulation-format allocation (RSMA) in mixed grid optical network. In mixed grid network, spectrum redundancy and its assignment problem increase due to the spectrum continuity and contiguity constrains. In the proposed RDMSR strategy, process of defragmentation initiates after the termination of the existing connections. In addition, the route that needs minimum spectrum is given priority over the other available routes. The performance of the proposed strategy is compared with the two existing strategies: shortest path first (SPF) and mixed grid aware dynamic resources allocation (MDRA). Simulations are performed on NSFNET and ARPANET topologies. The existing and proposed strategies are evaluated on the metrics of bandwidth blocking probability (BBP), network capacity (NC), and average hops (AH) at three different combinations of the network traffic. Results show the proposed strategy outperforms than the other existing state of art strategies.