第３３卷第１期 ２００７年１月 阜师 范 ｏｆ Ｑｕｆｕ Ｖｏ１．３３ ＮＯ．１ Ｊａｎ．２００７
基于网络限制的最短路模型
黄奇成①， 王丽君②， 苏 醒①
（①曲阜师范大学运筹与管理学院Ｉ②曲阜师范大学信息与传播学院，２７６８２６，山东省日照市）
摘要：带限制的网络是一类特殊的网络，如具有禁止通行限制信息的交通路网．由于此类网络的最短路 径的求解是有后效性的，因此经典的Ｄｉｊｋｓｔｒａ算法等就无法用来解决此类问题．提出了一种路网带限制的交 通网络最短路径建模方法．该方法将具有禁行限制的特殊网络转化成一个一般的网络模型・从而可用任一传
统高效的算法完成对其最短路径的求解． 关键词：路网限制Ｉ最短路径ｆ交通路网ｆ模型 中图分类号：Ｏ１５７．６ 文献标识码：Ａ 文章编号：ｉ００１ ５３３７（２００７）０１ ００５１ ０３
ｌ 引 言
伴随社会的发展、城市人口的增多，城市交通问 题越来越成为一个重要问题．作为一个复杂的系统，
城市交通中更多的包含了如交通信号的合理配置，
单行、禁行等限制的情况，如交通信号的合理配置，
单行、禁行等限制可使交通流合理分流，从而提高交 通安全和效率 ］．而作为图论中的点与线构成的
各种图能完整地表示交通系统中的各种情况，因而
我们考虑引入图的概念对带约束的城市交通系统中
的情况进行分析 ］．
在图论中对一般情况下最短路径问题的求解已
有了较为成熟的算法．对车辆诱导系统而言，现实的
交通情况中许多经典算法不能直接应用［６］，因为在
实际道路条件下，为了使得交通畅通，交通管理部门 制定了许多规则，其中包括路段单行、路口禁止左、
右转行等等情况，这样就使得表面上连通的道路网
络实际上可能并不连通ｌ＿７ ］．因此本文考虑设计算
法将这种含有交通限制的路网转化为不含禁行的一
般路网，然后再利用图论中的有效经典算法完成最
终的最优路径求解．
最短路径的网络模型
２，１ 问题的数学表述
第５３卷第３期 ２０１５年５月 吉林大学学报（理学版） Ｊｏｕｒｎａｌ ｏｆ Ｊｉｌｉｎ Ｕｎｉｖｅｒｓｉｔｙ（Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） ＶｏＩ．５３ ＮＯ．３ Ｍａｙ ２０１５
带有模糊约束最短路问题的数学模型及算法
孙 小 军
（宝鸡文理学院数学与信息科学学院，陕西宝鸡７２１０１３）
摘要：针对带有模糊约束的最短路问题，在其模糊线性规划模型的基础上，利用容差法和罚 函数法对该模型进行转化，得到了与原模型具有相同最优解与最优值的转化模型，并提出一
种修正的萤火虫算法求解转化模型．数值算例结果表明，该模型与算法对求解带有模糊约束
的最短路问题有效． 关键词：模糊约束；最短路问题；萤火虫算法；修正算法
中图分类号：ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１６７１—５４８９（２０１５）０３—０４７８—０５
Ｍａｔｈｅｍａｔｉｃａｌ Ｍｏｄｅｌ ａｎｄ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Ｓｈｏｒｔｅｓｔ
Ｐａｔｈ Ｐｒｏｂｌｅｍ ｗｉｔｈ Ｆｕｚｚｙ Ｃｏｎｓｔｒａｉｎｔｓ
ＳＵＮ Ｘｉａｏｊｕｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ，Ｂａｏｊｉ Ｕｎｉｖｅｒｓｉｔｙ ｏ．ｆ Ａｒｔｓ ａｎｄ Ｓｃｉｅｎｃｅｓ， Ｂａｏｊｉ ７２１０１３，Ｓｈａａｎｘｉ Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｒｏｂｌｅｍ ｗｉｔｈ ｆｕｚｚｙ ｃｏｎｓｔｒａｉｎｔ，ｂａｓｅｄ ｏｎ ｔｈｅ ｆｕｚｚｙ ｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌ，ｔｏｌｅｒａｎｃｅ ｍｅｔｈｏｄ ａｎｄ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ ｍｅｔｈｏｄ ｗｅｒｅ ａｄｏｐｔｅｄ ｔｏ ｃｏｎｖｅｒｔ ｔｈｅ ｏｒｉｇｉｎａｌ ｍｏｄｅｌ ｔｏ ｏｂｔａｉｎ ａ ｔｒａｎｓｆｏｒｍｅｄ ｍｏｄｅｌ ｗｉｔｈ ｔｈｅ ｓａｍｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ａｎｄ ｏｐｔｉｍａｌ ｖａｌｕｅ ａｓ ｔｈｏｓｅ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｍｏｄｅ１．Ｔｈｅｎ，ａ ｍｏｄｉｆｉｅｄ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ ｗａｓ ｐｒｏｐｏｓｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｔｒａｎｓｆｏｒｍｅｄ
第卷第期
乞刃吕年月白城师范学院学
报
例回间试越
卜司伪也
,公
刀,场
】即,伽旧
用动态规
划模型求解最短路问
题的研究
王丽颖
白城师范学院
数学系,
吉林白
城砚】】
摘要动态规划法是求解具有多阶段的最短路径的算法,
本文以动态规划理论为指
导,
研究了铺设管
道最短路
问题实
例,采用顺序递推
法和逆
序递推
法两种解决方
法,
并
用
刀‘
口软件编程得到结果
关幼词动态规划最短路径口刊宕口程序
中圈分类号文献标识码文章绷号一
加肠切供
在交通运输、
道路铺设等实
际工作中,
最短路问题应用得非常
广泛,求
最短路
的算
法有多种,
如
丙算法,
矩阵
算法,动
态规划方法等
枷算
法可
用于
计算网络图中某一
点到各点的最短距
离,
但实际问题中有时需要求网络中所有各点之间的最短距离,
如果仍采用加算法分别计算,
效率
很低矩阵算
法可用于
计算
所有节点之间的最短路
径,但计
算量较大,
适于
用计
算机计
算动态规
划方法主要是研究与解决
多阶段决策
过程的最优化问题,
是求
最短路问题的好算
法,动
态规划方
法是
将求
解分
成多阶段进行,求
出的不但
是全过程的解,而
且包括后部
子过程的一族
解,
在某
些情
况下,
实
际问题需要族解时,
更显其优越性
动
态规划所处理的问题是一个多阶段决策
间题,
一般由初始状态开始,
通过对中间阶段决策
的选
择,
达到结束
状态,
这些决
策形成了一个决策序列,
同时确定
了完成整个过程的一条活动路线
通常
是求
最优的活动路
线,
如图
所示,
动态规划的设计都
有着一定的模式,
一般要
经历以下
几不步骤
初始状态
一
画一
画一
一
画一结束
、
用于
衡量
所选决策优劣的数
量指标称为指标函数,人‘
为最优指标函数,
最短路
线问题中的
最优指标函
数是最短距离,
叭为无阶段的距离,
在每一阶段的决策
中有一个赖以决策的策略
或目标,
这种策略或目标是由问题的性质和
特点
所确
定,
通常
以函数
的形式表示
并具有递推
关系,
称为动
态规
划函数,
动态规划的基本方程为
娇,
凡,。
乓人气乓,
二,,
…,,
。二,
式中为阶段变量
为阶段数,
。
分别为第阶段的状
态变量
和决策变量
动态规划可
分为正
向思维法和逆
向思维法,
各种图论模型及其解答
摘要：
本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。
符号约定：
Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。
一、引言
图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下：
原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解
整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况：
①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图
②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图
如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。
综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。
例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友
M：点表示人，连线表示当且仅当该两个人是朋友
A：问题转化为任何一个图一定存在两个顶点的度相等
二、图论模型
接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。
2.1 偶图模型 凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。
