数学建模笔记（十三）：离散模型（DP、图论） |
您所在的位置：网站首页 › 常见的数学建模有哪些 › 数学建模笔记（十三）：离散模型（DP、图论） |
数学建模笔记（十三）：离散模型（DP、图论）
|
文章目录
一、引论1.商人安全过河2.循环比赛名次3.数列问题4.通信网络设计5.多阶段最优生产计划6.最短路线问题
二、动态规划问题1.基本概念（一）阶段（二）状态（三）决策（四）策略（五）状态转移方程（六）指标函数和最优值函数
2.基本方程3.以最短路说明基本思想4.最短路径问题5.最长单调上升子序列6.最大连续子段和
三、图与网络1.图与网络的发展简史（一）七桥问题（二）随机图（三）小世界实验（六度理论）（四）弱连接的强度
2.图的基本概念（一）无向图和有向图（二）无权图和加权图（三）多重图和简单图（四）链、圈、路、回路（五）连通图（六）子图、支撑子图（七）树、支撑树
3.图的常用概念（一）节点的度（二）平均路径长度（三）最小支撑树（四）最短路（五）介数（影响力）（六）
K
−
s
h
e
l
l
K-shell
K−shell值（七）邻接矩阵
4.最小支撑数5.最短路的求法
四、实例分析1.商人过河（一）动态规划——问题转化（二）动态规划——图解法（三）最短路——问题转化
2.循环比赛的名次（一）问题背景（二）竞赛图定义与性质（三）双向连通图（得分向量定义与计算）（四）累积分数定义与计算（五）提出异议（修改邻接矩阵的值，依然采用累积分数计算）（六）网络中节点的影响力评价（介数）
3.通信网络的费用问题（一）问题背景（二）问题一——最小支撑树（三）问题二——删点加边（四）问题三——删边加边
4.多阶段最优生产计划（一）问题背景（二）动态规划求解（三）最短路求解
一、引论
1.商人安全过河
从前往后 从后往前
最短路径问题 5.最长单调上升子序列最长单调上升子序列 6.最大连续子段和最大连续子段和 三、图与网络 1.图与网络的发展简史 （一）七桥问题
任意两个点之间存在一个最短路径，总共有
n
(
n
−
1
)
2
\frac{n(n-1)}{2}
2n(n−1)种组合
最小支撑树 5.最短路的求法最短路径 四、实例分析 1.商人过河为满足船的往返，船上要有人驾船才能过河 （一）动态规划——问题转化
k
：
k：
k：阶段，船过河的次数，过去和返回各算一次，所以可以用奇偶说明往返情况；
s
k
=
(
x
k
,
y
k
)
s_k=(x_k,y_k)
sk=(xk,yk)：状态，船过河第
k
k
k次后，船出发岸的商人数和随从数，
x
k
x_k
xk为商人数，
y
k
y_k
yk为随从数；
u
k
=
(
u
x
k
,
u
y
k
)
u_k=(ux_k,uy_k)
uk=(uxk,uyk)：决策，船第
k
k
k次过河时船上的商人数和随从数，
u
x
k
ux_k
uxk商人数，
u
y
k
uy_k
uyk随从数； 状态转移方程： s k = s k − 1 + ( − 1 ) k u k s_k=s_{k-1}+(-1)^ku_k sk=sk−1+(−1)kuk 目标是令k最小，船使用的次数最少 （二）动态规划——图解法
x k , y k , 1 x_k,y_k,1 xk,yk,1表示船在出发岸上的商人数 x k x_k xk和随从数 y k y_k yk x k , y k , 0 x_k,y_k,0 xk,yk,0表示船在对岸上时出发岸上的商人数 x k x_k xk和随从数 y k y_k yk 共有20个点表示不同的状态，红线与绿线表示不同的方向，我们就将问题模型转化为了一个有向图 我们的目标就是找到从（3，3，1）到（0，0，0）的最短路 最短路问题就可以直接使用之前的内容 不过此时只可以判断是否有合法解以及输出一个合法解，却不能直接得知共有多少个合法解
连通图概念解释 强连通图：任意两个顶点之间都存在互达的路径
最小支撑树
自定义函数
这三个点都连接着不同的连通图，每个点我们都选择出它与它所连接的第二大的连通图所连接的点（70对应61，77对应71，51对应30），再将这三个连通集合用两条边连起来，那样无论删除三个点中的哪个都可以保证连通
与问题二思路一致，找边——加边 4.多阶段最优生产计划 （一）问题背景
需要注意的是不生产就没有生产成本
|
无后效性 
s
(
2
)
=
A
s
(
1
)
=
A
∗
A
∗
e
s^{(2)}=As^{(1)}=A*A*e
s(2)=As(1)=A∗A∗e 通过
A
e
Ae
Ae所得的结果就是之前的得分向量，此时已经出现了一定的排名，我们将
A
A
A与这个6行1列的矩阵再做一次矩阵乘法，不断重复这个过程。
有可能无法得到满足要求的结果，比如说之前选取中出现了问题，所以可能要返回重新计算
【本文地址】
今日新闻 |
推荐新闻 |