2019-12-02 校内数模新手赛

调查地铁站的路径选择问题

摘要

对于一二线城市,地铁已成为民众不可或缺的出行方式,为了减少在上班上学路上消耗的时间,人们也可谓绞尽脑汁。这次,我们要帮助p同学,在他解决地铁"最佳门"问题时提供耗时最短的路线。

针对问题一,本文把庞大复杂的地铁网络化繁为简,最终简化成只有中转站和起始站互相以线段连接的平面图,求解此问题等价于找到从起始点出发,经过所有中转站,再回到出发点的耗时最短的路径。本文将中转站与起始站标号,采用 F l o y d Floyd Floyd 算法和蚁群算法,在计算机上求解此变形后的 T S P TSP TSP 问题。

针对问题二,类似解决问题一的思路,在对地铁站编号重整后,仍旧套用 F l o y d Floyd Floyd 进行预处理,化为传统的 M T S P MTSP MTSP 问题。最后采用遗传算法进行求解得到最佳方案。

针对问题三,根据第二问结果,第三问即简单的概率模型,由于舅舅与舅妈两人出现在中转站的概率相互独立,只需根据公式求解即可。

关键词:最短路径 F l o y d Floyd Floyd 算法 蚁群算法 遗传算法 旅行商问题( T S P TSP TSP) 多旅行商问题( M T S P MTSP MTSP) 期望分析

1.问题的重述

中大南校的p同学想要进行一项非常有趣的研究------在广州地铁的各条线路间中转,如何在上车时选择合适的"最佳门",使得下车时能尽快抢占先机,到达应转线路(例:乘坐8号线地铁时,若选择在16号门上车,则在下车时距离进入4号线站台的电梯最近)。p同学发现,搜索引擎并不能帮他找到地铁屏蔽门编号和线路切换所在电梯和门的具体相对位置。也就是说,p同学只能进行实地考察。

p同学不考虑从宿舍到达地铁站的时间,可以选择从中大站或鹭江站出发,返回时也可以选择回到中大站或鹭江站。对于 "自己怎么都不会去"的9,14,21,13号线相关中转站,p同学表示不感兴趣。地铁APM线与普通线路在地铁站内的换乘和出站模式接近,p同学认为不必调查。到达每个中转站进行调查时,p同学都需要走出地铁闸门,在站内进行观察,之后重新进入闸门(见附录1)。如果两次路过同一中转站,那么第二次可以不下地铁直接路过。

  1. p同学应如何选择线路,使得进行该调查的耗时最低。

  2. p同学认为集中时间调查完所有站点理论上太累。应如何选择线路,使得分5天进行该调查时耗时最低。

  3. p同学的舅舅与舅妈在广州地铁8号线沿线各中转站上班,若他们每人每天在每个中转站上班的概率视为相等,每天上班时间视为全天,根据你在2.中给出的方案,计算与他们单人相遇总次数、与他们相遇次数和的期望与方差。

2.问题的分析

本题主要探究遍历地铁中转站所用时间多少和相遇次数的问题。问题1、2要求从路线规划出发,设计出使p同学调查耗时最短的路线,主要用到图论的知识。问题3则要求根据第二问得出的方案来计算与舅舅舅妈相遇的期望与方差,属于概率类问题。

2.1对问题1的分析

在处理问题1时,先分析地铁线路图,将不需要的线路删去,然后把某些可以当作一个站的地铁站合并,之后画出简化后的线路图。分析后可以发现,这个问题可以等价成具有局部重复路径的旅行商问题( T S P TSP TSP),在4.1.2中我们证明了 F l o y d Floyd Floyd 算法对解决该问题的作用,将其转化为了传统的 T S P TSP TSP 问题,随后我们利用蚁群算法解决了这一问题,给出了最佳方案。

2.2对问题2的分析

在处理问题2时,类似对问题1的处理,对线路图进行简化。分析后发现该问题可转化为具有局部重复路径的多旅行商问题( M T S P MTSP MTSP),在4.1.2中证明了 F l o y d Floyd Floyd 算法对解决该问题的作用,将其转化为了传统的 M T S P MTSP MTSP 问题,随后我们利用遗传算法解决了这一问题,给出了最佳方案。

2.3对问题3的分析

第三问是一个典型的概率问题,直接根据第二问得到的方案进行解答即可。

3.模型的假设与符号说明

3.1模型的假设

  1. 假设p同学调查地铁站的整个过程中所有地铁正常运行。
  2. 假设p同学在所有的中转站换乘时的等车时间不计。
  3. 假设若p同学在规划的路径中将多次经过某一中转站的话,则其不一定在第一次到达该中转站时就进行考察。
  4. 假设地铁从上一个中转站运行至下一个中转站的时间为广州地铁官网上提供的时间。
  5. 假设当p同学转乘地铁时,舅舅舅妈在同一个中转站工作,则P同学与他们必定相遇。若经过中转站不下车换乘或调查,则p同学与舅舅舅妈不能相遇。

3.2符号说明

符号说明单位
a i a_i ai中转站编号/
D i s Dis Dis总路程/(总时间)/(min)
d i s i , j dis_{i,j} disi,j中转站 i , j i,j i,j 间距离(所需时间)/(min)
G G G连通图/
v i v_i vi顶点
D D D路径/
ρ \rho ρ信息素的挥发程度/
τ i j ( t ) \tau_{ij}(t) τij(t) t t t 时刻中转站 i i i 与中转站 j j j 连接路径上的信息素浓度/
Δ τ i j k \Delta\tau_{ij}^k Δτijk k k k 只蚂蚁在中转站 i i i 与中转站 j j j 连接路径上释放的信息素浓度/
P i , j k ( t ) P_{i,j}^k(t) Pi,jk(t)表示 t t t 时刻蚂蚁 k k k 从中转站 i i i 转移到中转站 j j j 的概率/
allow k \text{allow}_k allowk蚂蚁 k k k 待访问中转站的集合/
N N N遗传群体中的个体总数
f i f_i fi个体 i i i 的适应度/
P i P_i Pi个体 i i i 被选取的概率/
Q Q Q修正模型的常系数/
p p p舅舅/舅妈在四个中转站其一上班的概率/
n i n_i ni每条线路经过8号线中转站的次数
E 1 E_1 E1单人相遇次数的期望
E 2 E_2 E2与他们相遇次数和的期望
D 1 D_1 D1单人相遇次数的方差 次 2 次^2 2
D 2 D_2 D2与他们相遇次数和的方差 次 2 次^2 2

4.模型的建立

4.1问题1的模型建立与求解

4.1.1对地铁线路图的简化

通过查找数据,得到地铁在不同中转站之间运行所需时间。由于9,14,21,13号线相关的地铁中转站不在调查范围,我们先删去相关线路。之后,为观察方便,把两个中转站之间弯曲的线路变成连接两个站的线段,得到图1.1此时要遍历28个站。

图1.1

然后,为了便于计算,我们尝试再次简化图1.1:由于每个中转站都要调查,满足尽量减少时间的条件下,经过石壁与广州南站两个中转站的路径有且只有一条,将两站合并成一个地铁站不影响结果。此外,查询数据知,广州东站经1号线到体育西站的时间要多于经3号线到达的时间。在任何情况下,都可以选择3号线。所以,1号线此段线路可以删去而不影响结果。最终,我们得到的网络如图2.2所示。其中,编号1-27表示地铁站(图2.1),线段上的数字表示乘坐地铁经过此路段需要的时间(单位:min)。 (合并后,在石壁停留的调查时间增加至20min,即增加了广州南站的调查时间和往返时间)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YIs8UioF-1575883501493)(002.png)]

图2.1编号与地铁站的对应关系

在这里插入图片描述

图2.2

4.1.2模型的建立

  1. 首先明确:在4.1.1的条件下,我们需要求在遍历编号为1-27的地铁站的情况下,从1(或2)出发,回到2(或1)的最短时间。中间可以走"回头路",因此到达每一个地铁站的次数可能大于1次。

    为方便建模,经过每一段路线所经过的时间可以看作相对距离 d i s dis dis。考虑一个符合题意的方案中依次途径的中转站编号序列为 a 1 , a 2 , ⋯ , a m a_1,a_2,\cdots,a_m a1,a2,,am,总路程为 D i s = d i s a 1 , a 2 + d i s a 2 , a 3 + ⋯ + d i s a m − 1 , a m Dis=dis_{a_1,a_2}+dis_{a_2,a_3}+\cdots+dis_{a_{m-1},a_m} Dis=disa1,a2+disa2,a3++disam1,am
    目标是求 D i s m i n Dis_{min} Dismin

    经过分析后可以发现,由于1和2两点事实上可以合并考虑,该问题本质上就是具有局部重复路径的旅行商问题( T S P TSP TSP),接下来分成两部分对该问题进行求解。

  2. 预处理—— F l o y d Floyd Floyd 算法

    F l o y d Floyd Floyd 算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。在本题中,主要为了在后续的蚁群算法求解中能生成具有局部重复路径的解决方案。为详细说明该预处理作用,下给出一个定理及其证明。

    定理:连通图 G G G 中,在允许走重复路径的前提下,要使 T S P TSP TSP 回路的长度最短,则旅行商从顶点 v 1 v_1 v1 v 2 v_2 v2 时,所经过的通路必是 v 1 v_1 v1 v 2 v_2 v2 间的最短路径。

    证明:假设顶点 v 1 v_1 v1 v 2 v_2 v2 间存在多条道路(包括那些经过其他顶点的间接路径),若旅行商在从 v 1 v_1 v1 v 2 v_2 v2 时不经过 v 1 v_1 v1 v 2 v_2 v2 间的最短路径 D m i n D_{min} Dmin,而是经过路径 D D D,显然,使用 D m i n D_{min} Dmin 代替通路 D D D 能够获得更优的方案,得到的新的旅行路径必然就是图中两个顶点间最短路径组成。

    接下来阐述 F l o y d Floyd Floyd 算法的内容。从编号为 i i i 的地铁站出发,目的地为编号 j j j 的地铁站时( 1 ≤ i ≠ j ≤ 27 1\leq i\neq j\leq 27 1i=j27)若选择直接到达,则距离为 d i s i , j dis_{i,j} disi,j。考虑除 i , j i,j i,j 之外的站点中转,若存在站点 k k k,使得 i → k → j i\rightarrow k\rightarrow j ikj 的距离 d i s ′ = d i s i , k + d i s k , j < d i s i , j dis'=dis_{i,k}+dis_{k,j}<dis_{i,j} dis=disi,k+disk,j<disi,j

    则把 d i s ′ dis' dis 的值赋给 d i s i , j dis_{i,j} disi,j。 继续在 i , j i,j i,j 以外的其他中转站寻找这样的 k k k,直到确定 d i s i , j dis_{i,j} disi,j 的最小值。

    重复上述步骤,找到1-27号地铁站任意两站点之间的 d i s m i n dis_{min} dismin。站点之间的最小相对距离如下表。(第一行和第一列为中转站编号)

    站点123456789101112131415161718192021222324252627
    15922271521282631231825192529331461427263316221246
    254172210162331362823201420242819111730212811271742
    3941318612192840322416101620242315132617247312138
    4221713519253241534537292329333736282635261120443451
    5272218514202736484232241824283235333140311625493946
    61510619146132234281810410141821211932233013372732
    7211612252067162822124410141815232538293619322932
    82823193227137921231351116121816243245364326333029
    926312841362216912188142025212712202841445234282620
    10313640534834282112818263237333917253346496439182832
    1123283245422822231881018263235409172538415631102038
    121823243732181213818108162225304122033364826201828
    13252016292410451426188814172211192740334023282534
    14191410231844112032261686101419252336273417363128
    1525201629241010162537322214641025312942334023423722
    1629242033281414122133352517104628353346374427454118
    17332824373218181827394030221410633393750414831504524
    181419233635211516121794111925283381629324722191432
    19611152833212324202517121925313539882124391416640
    2014171326311925322833252027232933371681316316211148
    21273026354032384541463833403642465029211392419342461
    22262117263123293644494136332733374132241691510372755
    233328241116303643526456484034404448473931241525524262
    2416117202513192634393126231723273122146191025271745
    252227314449373233281810202836424550191621343752271048
    26121721343927293026282018253137414514611242742171046
    274642385146323229203238283428221824324048615562454846
    表3.1站点之间的最小相对距离
  3. 正式求解——蚁群算法

    ① 蚁群算法介绍:
    蚂蚁在寻找食物源时,会在其经过的路径上释放一种信息素,并能够感知其他蚂蚁释放的信息素。信息素的浓度大小表征路径的远近,信息素浓度越高,表示对应的路径距离越短。

    通常,蚂蚁会以较大的概率优先选择信息素浓度较高的路径,并释放一定量的信息素,以增强该条路径上的信息素浓度,这样会形成一个正反馈。最终,蚂蚁能够找到一条最佳路径,即最短距离。

    同时,路径上的信息素浓度会随着时间的推进而逐渐衰减。

    ② 蚁群算法解决 T S P TSP TSP 问题基本原理:

    不失一般性,设整个蚂蚁群体中蚂蚁的数量为 m m m,中转站的数量为 n n n,中转站 i i i 与中转站 j j j 之间的距离为 d i s i , j ( i , j = 1 , 2 , ⋯ , n ) dis_{i,j}(i,j=1,2,\cdots,n) disi,j(i,j=1,2,,n) t t t 时刻中转站 i i i 与中转站 j j j 连接路径上的信息素浓度为 τ i j ( t ) \tau_{i j}(t) τij(t)。初始时刻,各个中转站间连接路径上的信息素浓度相同,不妨设为 τ i , j ( 0 ) = τ 0 \tau_{i,j}(0)=\tau_0 τi,j(0)=τ0

    蚂蚁 k ( k = 1 , 2 , ⋯ , m ) k(k=1,2,\cdots,m) k(k=1,2,,m) 根据各个中转站间连接路径上的信息素浓度决定其下一个访问中转站,设 P i , j k ( t ) P_{i,j}^k(t) Pi,jk(t) 表示 t t t 时刻蚂蚁 k k k 从中转站 i i i 转移到中转站 j j j 的概率,其计算公式为
    P i j k = { [ τ i j ( t ) ] α ⋅ [ η i j ( t ) ] β ∑ s ∈ allow  k [ τ i s ( t ) ] α ⋅ [ η i s ( t ) ] β , s ∈ allow  k 0 , s ∉ allow  k P_{i j}^{k}=\left\{\begin{array}{ll}{\frac{\left[\tau_{i j}(t)\right]^{\alpha} \cdot\left[\eta_{i j}(t)\right]^{\beta}}{\sum_{s \in \text { allow }_{k}}\left[\tau_{i s}(t)\right]^{\alpha} \cdot\left[\eta_{i s}(t)\right]^{\beta}},} & {s \in \text { allow }_{k}} \\ {0,} & {s \notin \text { allow }_{k}}\end{array}\right. Pijk={s allow k[τis(t)]α[ηis(t)]β[τij(t)]α[ηij(t)]β,0,s allow ks/ allow k
    其中, η i j ( t ) \eta_{i j}(t) ηij(t) 为启发函数, η i j ( t ) = 1 d i , j \eta_{i j}(t)=\frac{1}{d_{i,j}} ηij(t)=di,j1,表示蚂蚁从中转站 i i i 转移到中转站 j j j 的期望程度; allow k ( k = 1 , 2 , ⋯ , m ) \text{allow}_k(k=1,2,\cdots,m) allowk(k=1,2,,m) 为蚂蚁 k k k 待访问中转站的集合,开始时, allow k \text{allow}_k allowk 中有 ( n − 1 ) (n-1) (n1) 个元素,即包括了除了蚂蚁 k k k 出发站点的其他所有站点,随着时间的推进, allow k \text{allow}_k allowk 中的元素不断减少,直至为空,即表示所有的中转站均访问完毕; α \alpha α 为信息素重要程度因子,其值越大,表示信息素的浓度在转移中起的作用越大; β \beta β 为启发函数重要程度因子,其值越大,表示启发函数在转移中的作用越大,即蚂蚁会以较大的概率转移到距离短的中转站。

    如前文所述,在蚂蚁释放信息素的同时,各个中转站间连接路径上的信息素逐渐消失,设参数 ρ ( 0 < ρ < 1 ) \rho(0<\rho<1) ρ(0<ρ<1) 表示信息素的挥发程度。因此,当所有蚂蚁完成一次循环后,各个城市间连接路径上的信息素浓度需进行实时更新,即
    { τ i j ( t + 1 ) = ( 1 − ρ ) τ i j ( t ) + Δ τ i j Δ τ i j = ∑ k = 1 n Δ τ i j k , 0 < ρ < 1 \left\{\begin{array}{l}{\tau_{ij}(t+1)=(1-\rho) \tau_{i j}(t)+\Delta \tau_{i j}} \\ {\Delta \tau_{i j}=\sum_{k=1}^{n} \Delta \tau_{i j}^{k}}\end{array}, \quad 0<\rho<1\right. {τij(t+1)=(1ρ)τij(t)+ΔτijΔτij=k=1nΔτijk,0<ρ<1
    其中, Δ τ i j k \Delta\tau_{ij}^k Δτijk 表示第 k k k 只蚂蚁在中转站 i i i 与中转站 j j j 连接路径上释放的信息素浓度; Δ τ i j \Delta\tau_{ij} Δτij 表示所有蚂蚁在中转站 i i i 与中转站 j j j 连接路径上释放的信息素浓度之和。

    针对蚂蚁释放信息素问题,本题中我们采用了 a n t c y c l e s y s t e m ant\ cycle\ system ant cycle system 模型,在该模型中, Δ τ i j k \Delta\tau_{ij}^k Δτijk 的计算公式为
    Δ τ i j k = { Q / L k , 第 k 只 蚂 蚁 从 中 转 站 i 访 问 中 转 站 j 0 , 其 他 \Delta \tau_{i j}^{k}=\left\{\begin{array}{l}{Q / L_{k}},&第k只蚂蚁从中转站\ i\ 访问中转站\ j\ \\ {0},&其他\end{array}\right. Δτijk={Q/Lk,0,k i 访 j 
    ③ 蚁群算法解决 T S P TSP TSP 问题基本步骤

    基于上述原理,将蚁群算法应用于解决 T S P TSP TSP 问题一般需要以下几个步骤,如图3.2所示。
    在这里插入图片描述

    图3.2蚁群算法解决 TSP 问题基本步骤

4.1.3模型的结果

在本题中,由于可以重复经过路径,所以先用 F l o y d Floyd Floyd 算法进行预处理,进而转化成了一般性的 T S P TSP TSP 问题。并且,由于在本问题中,每个地铁中转站只考察一次,因此在处理该问题时可以先不考虑考察时间,最后再加入答案中。将处理后的数据(表3.1)导入 MATLAB 中,应用蚁群算法。即可解得最优方案如下:
在这里插入图片描述
在这里插入图片描述

直观路线图如下图3.3:
在这里插入图片描述

图3.3模型结果

4.2问题2的模型建立与求解

4.2.1对地铁线路图的简化

类似4.1.1,在处理第二问的过程中,我们依旧是将每个中转站抽象成一个点。主要的改变是,在第二问中将1和2两个点进行合并。给各个地铁中转站的编号如下图4.1。另外,修改后得地铁中转站网络图如下图4.2,线段上的数字表示乘坐地铁经过此路段需要的时间(单位:min)。
在这里插入图片描述

图4.1编号与地铁站的对应关系

在这里插入图片描述

图4.2

4.2.2模型的建立

  1. 首先明确:在4.2.1的条件下,我们需要求在遍历编号为1-26的地铁站的情况下,从1出发,回到1的最短时间。中间可以走“回头路”因此到达每一个地铁站的次数可能大于1次。

    为方便建模,经过每一段路线所经过的时间可以看作相对距离 d i s dis dis。考虑一个符合题意的方案中,第 i i i 天的出行中,依次途径的中转站编号序列为 a i , 1 , a i , 2 , ⋯ , a i , m a_{i,1},a_{i,2},\cdots,a_{i,m} ai,1,ai,2,,ai,m,则五天出行的总路程为
    D i s = ∑ n = 1 5 ( d i s a i , 1 , a i , 2 + d i s a i , 2 , a i , 3 + ⋯ + d i s a i , m − 1 , a i , m ) Dis= \sum_{n=1}^5(dis_{a_{i,1},a_{i,2}}+dis_{a_{i,2},a_{i,3}}+\cdots+dis_{a_{i,m-1},a_{i,m}}) Dis=n=15(disai,1,ai,2+disai,2,ai,3++disai,m1,ai,m)
    目标是求 D i s m i n Dis_{min} Dismin

    经过分析后可以发现,与第一问类似,该问题本质上就是具有局部重复路径的多旅行商问题( M T S P MTSP MTSP),接下来分成两部分对该问题进行求解。

  2. 预处理—— F l o y d Floyd Floyd 算法

    在4.1.2中已经说明了该算法在生成具有局部重复路径的解决方案的过程中的作用,并且给出了对应的定理和证明,同时也已阐明了 F l o y d Floyd Floyd 算法的内容及应用,此处不再赘述。

    预处理后得到1-26号地铁站任意两站点之间的 d i s m i n dis_{min} dismin。站点之间的最小相对距离如下表。(第一行和第一列为中转站编号)

    站点1234567891011121314151617181920212223242526
    1417221016232631231820142024281461427212811221242
    241318612192835272216101620241810132617247261638
    31713519253241484035292329333731232635261120392951
    42218514202736484232241824283235283140311625443446
    510619146132234281810410141821161932233013322232
    61612252067162822124410141815222538293619322832
    723193227137921231351116121816243245364326333029
    8262841362216912188142025212712202841445234282620
    93135484834282112818263237333917253346495939182832
    10232740422822231881018263235409172538415131102038
    1118223532181213818108162225304122033364626201828
    122016292410451426188814172211192740334023282534
    131410231844112032261686101419202336273417362628
    14201629241010162537322214641025262942334023423222
    15242033281414122133352517104628303346374427453618
    162824373218181827394030221410633343750414831504024
    1714183135211516121794111925283381629324222191432
    186102328162224202517121920263034882124341416640
    19141326311925322833252027232933371681316316211148
    202726354032384541463833403642465029211392419342461
    212117263123293644494136332733374132241691510372755
    2228241116303643525951464034404448423431241525504062
    23117202513192634393126231723273122146191025271745
    2422263944323233281811202836424550191621343750271048
    251216293422283026282018252632364014611242740171046
    2642385146323229203238283428221824324048615562454846
    表4.3站点之间的最小相对距离
  3. 正式求解——遗传算法

    ① 遗传算法介绍:

    遗传算法是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。

    遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题,一定数量的候选解(称为个体)可抽象表示为染色体,使种群向更好的解进化。传统上,解用二进制表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个体的种群开始,之后一代一代发生。在每一代中评价整个种群的适应度,从当前种群中随机地选择多个个体(基于它们的适应度),通过自然选择和突变产生新的生命种群,该种群在算法的下一次迭代中成为当前种群。

    ② 遗传算法解决 M T S P MTSP MTSP 问题基本步骤:

    首先进行二进制编码,即每个个体的基因型都是一个二进制编码符号串。接下来是进行交配,“交配运算”是使用单点或者多点进行交叉的算子。首先用随机数产生一个或者多个交配点位置,然后两个个体在交配点位置互换部分基因码,形成两个子个体。

    例如,两条染色体 S 1 = 01001011 , S 2 = 10010101 S_1=01001011,S_2=10010101 S1=01001011,S2=10010101。交换其后4位基因,得 S 1 ′ = 01000101 , S 2 ′ = 10001011 S_1'=01000101,S_2'=10001011 S1=01000101,S2=10001011 可以被看做原染色体 S 1 S_1 S1 S 2 S_2 S2 的子代染色体。

    另外,这过程中还存在着变异现象,主要包括突变和倒位。对于突变,举个例子,对于 S 1 = 010110011 S_1=010110011 S1=010110011,第三位0突变成1,那么我们得到 S 1 ′ = 011110011 S_1'=011110011 S1=011110011。倒位是指一个染色体某区段正常排列顺序发生 18 0 ∘ 180^{\circ} 180 的颠倒,造成染色体内的 D N A DNA DNA 序列重新排列。例如对于 $S_1=$010100010110110101进行倒位时得到 $S_1’=$010101101000110101。

    然后还要进行适应度评估。遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体的机会。个体适应度大的个体更容易被遗传到下一代。在本题中,利用该个体得到的五天路径总长度作为评估个体适应度大小的函数,长度越小适应度越高,长度越大适应度越低。

    最后还有选择的步骤,选择运算时根据个体适应度大小决定其下代遗传的可能性。设种群中个体总数为 N N N,个体 i i i 的适应度为 f i f_i fi,则个体 i i i 被选取的概率为 P i = f i ∑ i = 1 N P_i=\frac{f_i}{\sum_{i=1}^N} Pi=i=1Nfi

    遗传算法的整个过程如下图4.4:
    在这里插入图片描述

    图4.4遗传算法过程

4.2.3模型的结果

在本题中,由于可以重复经过路径,所以先用 F l o y d Floyd Floyd 算法进行预处理。同时,结合实际生活经验,为了能够不让p同学太累,合理规划出行调研路径,我们假设p同学不一定第一次经过某中转站就进行考察。于是,类似第一问,我们同样先将考察时间分离出来,剩下的问题就是一个典型的 M T S P MTSP MTSP 问题。将处理后的数据(表4.3)导入 MATLAB 中,应用遗传算法。

其中不断修改参数min-tour(每天最少考察中转站数),得到了下列图4.5:
在这里插入图片描述

图4.5修改参数得到的结果
由图4.5可以看出,单次调查中转站数量越少,总时间就越少。但是这样会出现一次调查耗时巨大的情况。

由于题目中认为“集中所有时间调查站点太累”,那么我们给出一个单次调查时间上限180min,在满足该条件并尽量使每天调查时间均匀的情况下,筛选出一个最优方案。即可解得最优方案如下(编号对应的地铁站可参照图4.1):
在这里插入图片描述
在这里插入图片描述

图4.6模型的结果
最后基于这种方案得到最短总时间为544。

4.3问题3的模型建立与求解

首先由如下假设:当p同学转乘地铁时,舅舅舅妈在同一个中转站工作,则P同学与他们必定相遇。若经过中转站不下车换乘或调查,则p同学与舅舅舅妈不能相遇。

8号线只有四个中转站:25号沙园、18号昌岗、2号客村、3号万胜围。由于每天上班地点随机,在这四个站中,与舅舅或者舅妈中一个人相遇概率为 p = 0.25 p=0.25 p=0.25

方案中第一天——第五天的路线为上图4.6,设 n i ( i = 1 , 2 , 3 , 4 , 5 ) n_i(i=1,2,3,4,5) ni(i=1,2,3,4,5) 为经过中转站次数(下列编号的地铁站可参考图4.1)
在这里插入图片描述
单人相遇次数(5天总共) E 1 = p × ( n 1 + n 2 + n 3 + n 4 + n 5 ) = 2.75 E_1=p\times(n_1+n_2+n_3+n_4+n_5)=2.75 E1=p×(n1+n2+n3+n4+n5)=2.75
单人相遇方差 D 1 = 1 5 ∑ i = 1 5 ( p ⋅ n i − E 1 5 ) = 0.01 D_1=\frac{1}{5}\sum_{i=1}^5(p\cdot n_i-\frac{E_1}{5})=0.01 D1=51i=15(pni5E1)=0.01
与两人相遇总次数 E 2 = 2.75 × 2 = 5.5 E_2=2.75\times 2=5.5 E2=2.75×2=5.5
与两人相遇方差 D 2 = 4 × 0.01 = 0.04 D_2=4\times 0.01=0.04 D2=4×0.01=0.04

5.模型的推广与评价

本文为解决地铁站问题采用的算法可以应用在其他寻求最短路径以及类似的现实生活中的 T S P TSP TSP M T S P MTSP MTSP 问题中。为了使既定条件下计算机能够求解该模型,对模型的优化方法在解决其他问题时也可以借鉴。

当然,模型也有一些缺点。如在等车时间的设置上,各个中转站的等车时间与线路地铁班数、线路人流量都相关,模型中全部取了一固定值。第二次经过中转站时下车换乘的时间在构建模型时也予以忽略,只是在计算出最终路径以后加到总时间上。

附录

F l o y d Floyd Floyd 预处理代码:

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;const int maxn=110;
const int waitTime=0;
const int INF=1000010;int distances[maxn][maxn],n,times[maxn];
string paths[maxn][maxn];
string vertex[maxn]={"0","1","2","3","4","5","6","7","8","9","10","11","12",
"13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28"};int main()
{freopen("in.txt","r",stdin);freopen("input.txt","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&times[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){scanf("%d",&distances[i][j]);if(distances[i][j]>0)distances[i][j]=distances[i][j]+waitTime;else distances[i][j]=INF;paths[i][j]=vertex[i]+" --> "+vertex[j];}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(distances[i][k]<INF&&distances[k][j]<INF&&i!=j)if(distances[i][k]+distances[k][j]<distances[i][j]){distances[i][j]=distances[j][i]=distances[i][k]+distances[k][j];paths[i][j]=paths[i][k]+" --> "+vertex[j];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",distances[i][j]);printf("\n");}printf("\n");for(int i=1;i<=n;i++){cout<<"顶点"<<vertex[i]<<":"<<endl;for(int j=1;j<=n;j++)cout<<paths[i][j]<<"	"<<distances[i][j]<<endl;printf("\n");}return 0;
}

预处理后得到的第一问的 d a t a . t x t data.txt data.txt

1000010 5 9 22 27 15 21 28 26 31 23 18 25 19 25 29 33 14 6 14 27 26 33 16 22 12 46 
5 1000010 4 17 22 10 16 23 31 36 28 23 20 14 20 24 28 19 11 17 30 21 28 11 27 17 42 
9 4 1000010 13 18 6 12 19 28 40 32 24 16 10 16 20 24 23 15 13 26 17 24 7 31 21 38 
22 17 13 1000010 5 19 25 32 41 53 45 37 29 23 29 33 37 36 28 26 35 26 11 20 44 34 51 
27 22 18 5 1000010 14 20 27 36 48 42 32 24 18 24 28 32 35 33 31 40 31 16 25 49 39 46 
15 10 6 19 14 1000010 6 13 22 34 28 18 10 4 10 14 18 21 21 19 32 23 30 13 37 27 32 
21 16 12 25 20 6 1000010 7 16 28 22 12 4 4 10 14 18 15 23 25 38 29 36 19 32 29 32 
28 23 19 32 27 13 7 1000010 9 21 23 13 5 11 16 12 18 16 24 32 45 36 43 26 33 30 29 
26 31 28 41 36 22 16 9 1000010 12 18 8 14 20 25 21 27 12 20 28 41 44 52 34 28 26 20 
31 36 40 53 48 34 28 21 12 1000010 8 18 26 32 37 33 39 17 25 33 46 49 64 39 18 28 32 
23 28 32 45 42 28 22 23 18 8 1000010 10 18 26 32 35 40 9 17 25 38 41 56 31 10 20 38 
18 23 24 37 32 18 12 13 8 18 10 1000010 8 16 22 25 30 4 12 20 33 36 48 26 20 18 28 
25 20 16 29 24 10 4 5 14 26 18 8 1000010 8 14 17 22 11 19 27 40 33 40 23 28 25 34 
19 14 10 23 18 4 4 11 20 32 26 16 8 1000010 6 10 14 19 25 23 36 27 34 17 36 31 28 
25 20 16 29 24 10 10 16 25 37 32 22 14 6 1000010 4 10 25 31 29 42 33 40 23 42 37 22 
29 24 20 33 28 14 14 12 21 33 35 25 17 10 4 1000010 6 28 35 33 46 37 44 27 45 41 18 
33 28 24 37 32 18 18 18 27 39 40 30 22 14 10 6 1000010 33 39 37 50 41 48 31 50 45 24 
14 19 23 36 35 21 15 16 12 17 9 4 11 19 25 28 33 1000010 8 16 29 32 47 22 19 14 32 
6 11 15 28 33 21 23 24 20 25 17 12 19 25 31 35 39 8 1000010 8 21 24 39 14 16 6 40 
14 17 13 26 31 19 25 32 28 33 25 20 27 23 29 33 37 16 8 1000010 13 16 31 6 21 11 48 
27 30 26 35 40 32 38 45 41 46 38 33 40 36 42 46 50 29 21 13 1000010 9 24 19 34 24 61 
26 21 17 26 31 23 29 36 44 49 41 36 33 27 33 37 41 32 24 16 9 1000010 15 10 37 27 55 
33 28 24 11 16 30 36 43 52 64 56 48 40 34 40 44 48 47 39 31 24 15 1000010 25 52 42 62 
16 11 7 20 25 13 19 26 34 39 31 26 23 17 23 27 31 22 14 6 19 10 25 1000010 27 17 45 
22 27 31 44 49 37 32 33 28 18 10 20 28 36 42 45 50 19 16 21 34 37 52 27 1000010 10 48 
12 17 21 34 39 27 29 30 26 28 20 18 25 31 37 41 45 14 6 11 24 27 42 17 10 1000010 46 
46 42 38 51 46 32 32 29 20 32 38 28 34 28 22 18 24 32 40 48 61 55 62 45 48 46 1000010 

预处理后得到的第二问的 i n p u t . t x t input.txt input.txt

1000010 4 17 22 10 16 23 26 31 23 18 20 14 20 24 28 14 6 14 27 21 28 11 22 12 42 
4 1000010 13 18 6 12 19 28 35 27 22 16 10 16 20 24 18 10 13 26 17 24 7 26 16 38 
17 13 1000010 5 19 25 32 41 48 40 35 29 23 29 33 37 31 23 26 35 26 11 20 39 29 51 
22 18 5 1000010 14 20 27 36 48 42 32 24 18 24 28 32 35 28 31 40 31 16 25 44 34 46 
10 6 19 14 1000010 6 13 22 34 28 18 10 4 10 14 18 21 16 19 32 23 30 13 32 22 32 
16 12 25 20 6 1000010 7 16 28 22 12 4 4 10 14 18 15 22 25 38 29 36 19 32 28 32 
23 19 32 27 13 7 1000010 9 21 23 13 5 11 16 12 18 16 24 32 45 36 43 26 33 30 29 
26 28 41 36 22 16 9 1000010 12 18 8 14 20 25 21 27 12 20 28 41 44 52 34 28 26 20 
31 35 48 48 34 28 21 12 1000010 8 18 26 32 37 33 39 17 25 33 46 49 59 39 18 28 32 
23 27 40 42 28 22 23 18 8 1000010 10 18 26 32 35 40 9 17 25 38 41 51 31 10 20 38 
18 22 35 32 18 12 13 8 18 10 1000010 8 16 22 25 30 4 12 20 33 36 46 26 20 18 28 
20 16 29 24 10 4 5 14 26 18 8 1000010 8 14 17 22 11 19 27 40 33 40 23 28 25 34 
14 10 23 18 4 4 11 20 32 26 16 8 1000010 6 10 14 19 20 23 36 27 34 17 36 26 28 
20 16 29 24 10 10 16 25 37 32 22 14 6 1000010 4 10 25 26 29 42 33 40 23 42 32 22 
24 20 33 28 14 14 12 21 33 35 25 17 10 4 1000010 6 28 30 33 46 37 44 27 45 36 18 
28 24 37 32 18 18 18 27 39 40 30 22 14 10 6 1000010 33 34 37 50 41 48 31 50 40 24 
14 18 31 35 21 15 16 12 17 9 4 11 19 25 28 33 1000010 8 16 29 32 42 22 19 14 32 
6 10 23 28 16 22 24 20 25 17 12 19 20 26 30 34 8 1000010 8 21 24 34 14 16 6 40 
14 13 26 31 19 25 32 28 33 25 20 27 23 29 33 37 16 8 1000010 13 16 31 6 21 11 48 
27 26 35 40 32 38 45 41 46 38 33 40 36 42 46 50 29 21 13 1000010 9 24 19 34 24 61 
21 17 26 31 23 29 36 44 49 41 36 33 27 33 37 41 32 24 16 9 1000010 15 10 37 27 55 
28 24 11 16 30 36 43 52 59 51 46 40 34 40 44 48 42 34 31 24 15 1000010 25 50 40 62 
11 7 20 25 13 19 26 34 39 31 26 23 17 23 27 31 22 14 6 19 10 25 1000010 27 17 45 
22 26 39 44 32 32 33 28 18 11 20 28 36 42 45 50 19 16 21 34 37 50 27 1000010 10 48 
12 16 29 34 22 28 30 26 28 20 18 25 26 32 36 40 14 6 11 24 27 40 17 10 1000010 46 
42 38 51 46 32 32 29 20 32 38 28 34 28 22 18 24 32 40 48 61 55 62 45 48 46 1000010 

M A T L A B MATLAB MATLAB 蚁群算法代码:

%% 清空环境变量
clear all
clc%% 导入数据
load data.txt%% 计算城市间相互距离
n = size(data,1);
D = data;%% 初始化参数
m = 35;                              % 蚂蚁数量
alpha = 3;                           % 信息素重要程度因子
beta = 4;                            % 启发函数重要程度因子
rho = 0.2;                           % 信息素挥发因子
Q = 0.8;                               % 常系数
Eta = 1./D;                          % 启发函数
Tau = ones(n,n);                     % 信息素矩阵
Table = zeros(m,n);                  % 路径记录表
iter = 1;                            % 迭代次数初值
iter_max = 3500;                      % 最大迭代次数 
Route_best = zeros(iter_max,n);      % 各代最佳路径       
Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  %% 迭代寻找最佳路径
while iter <= iter_max% 随机产生各个蚂蚁的起点城市start = zeros(m,1);for i = 1:m% temp = 1;start(i) = 1;endTable(:,1) = start; % 构建解空间citys_index = 1:n;% 逐个蚂蚁路径选择for i = 1:m% 逐个城市路径选择for j = 2:ntabu = Table(i,1:(j - 1));           % 已访问的城市集合(禁忌表)allow_index = ~ismember(citys_index,tabu);allow = citys_index(allow_index);  % 待访问的城市集合P = allow;% 计算城市间转移概率for k = 1:length(allow)P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;endP = P/sum(P);% 轮盘赌法选择下一个访问城市Pc = cumsum(P);     target_index = find(Pc >= rand); target = allow(target_index(1));Table(i,j) = target;endend% 计算各个蚂蚁的路径距离Length = zeros(m,1);for i = 1:mRoute = Table(i,:);for j = 1:(n - 1)Length(i) = Length(i) + D(Route(j),Route(j + 1));endLength(i) = Length(i) + D(Route(n),Route(1));end% 计算最短路径距离及平均距离if iter == 1[min_Length,min_index] = min(Length);Length_best(iter) = min_Length;  Length_ave(iter) = mean(Length);Route_best(iter,:) = Table(min_index,:);else[min_Length,min_index] = min(Length);Length_best(iter) = min(Length_best(iter - 1),min_Length);Length_ave(iter) = mean(Length);if Length_best(iter) == min_LengthRoute_best(iter,:) = Table(min_index,:);elseRoute_best(iter,:) = Route_best((iter-1),:);endend% 更新信息素Delta_Tau = zeros(n,n);% 逐个蚂蚁计算for i = 1:m% 逐个城市计算for j = 1:(n - 1)Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);endDelta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);endTau = (1-rho) * Tau + Delta_Tau;% 迭代次数加1,清空路径记录表iter = iter + 1;Table = zeros(m,n);
end%% 结果显示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
disp(['最短距离:' num2str(Shortest_Length)]);
disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);

M A T L A B MATLAB MATLAB 遗传算法代码:

%% 
load input.txtn = 26;
xy = 10*rand(n,2);
salesmen = 5;
min_tour = 4;
pop_size = 160;
num_iter = 5e3;
a = meshgrid(1:n);
dmat = input;
[opt_rte,opt_brk,min_dist] = mtspf_ga(xy,dmat,salesmen,min_tour, ...
pop_size,num_iter,1,1);%% 
function varargout = mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)% Process Inputs and Initialize Defaults
% Verify Inputs
[N,dims] = size(xy);
[nr,nc] = size(dmat);
if N ~= nr || N ~= ncerror('Invalid XY or DMAT inputs!')
end
n = N - 1; % Separate Start/End City% Sanity Checks
salesmen = max(1,min(n,round(real(salesmen(1)))));
min_tour = max(1,min(floor(n/salesmen),round(real(min_tour(1)))));
pop_size = max(8,8*ceil(pop_size(1)/8));
num_iter = max(1,round(real(num_iter(1))));
show_prog = logical(show_prog(1));
show_res = logical(show_res(1));% Initializations for Route Break Point Selection
num_brks = salesmen-1;
dof = n - min_tour*salesmen;          % degrees of freedom
addto = ones(1,dof+1);
for k = 2:num_brksaddto = cumsum(addto);
end
cum_prob = cumsum(addto)/sum(addto);% Initialize the Populations
pop_rte = zeros(pop_size,n);          % population of routes
pop_brk = zeros(pop_size,num_brks);   % population of breaks
for k = 1:pop_sizepop_rte(k,:) = randperm(n)+1;pop_brk(k,:) = randbreaks();
end% Select the Colors for the Plotted Routes
clr = [1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0];
if salesmen > 5clr = hsv(salesmen);
end% Run the GA
global_min = Inf;
total_dist = zeros(1,pop_size);
dist_history = zeros(1,num_iter);
tmp_pop_rte = zeros(8,n);
tmp_pop_brk = zeros(8,num_brks);
new_pop_rte = zeros(pop_size,n);
new_pop_brk = zeros(pop_size,num_brks);
if show_progpfig = figure('Name','MTSPF_GA | Current Best Solution','Numbertitle','off');
end
for iter = 1:num_iter% Evaluate Members of the Populationfor p = 1:pop_sized = 0;p_rte = pop_rte(p,:);p_brk = pop_brk(p,:);rng = [[1 p_brk+1];[p_brk n]]';for s = 1:salesmend = d + dmat(1,p_rte(rng(s,1))); % Add Start Distancefor k = rng(s,1):rng(s,2)-1d = d + dmat(p_rte(k),p_rte(k+1));endd = d + dmat(p_rte(rng(s,2)),1); % Add End Distanceendtotal_dist(p) = d;end% Find the Best Route in the Population[min_dist,index] = min(total_dist);dist_history(iter) = min_dist;if min_dist < global_minglobal_min = min_dist;opt_rte = pop_rte(index,:);opt_brk = pop_brk(index,:);rng = [[1 opt_brk+1];[opt_brk n]]';if show_prog% Plot the Best Routefigure(pfig);for s = 1:salesmenrte = [1 opt_rte(rng(s,1):rng(s,2)) 1];if dims == 3, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:));else plot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:)); endtitle(sprintf('Total Distance = %1.4f, Iteration = %d',min_dist,iter));hold onendif dims == 3, plot3(xy(1,1),xy(1,2),xy(1,3),'ko');else plot(xy(1,1),xy(1,2),'ko'); endhold offendend% Genetic Algorithm Operatorsrand_grouping = randperm(pop_size);for p = 8:8:pop_sizertes = pop_rte(rand_grouping(p-7:p),:);brks = pop_brk(rand_grouping(p-7:p),:);dists = total_dist(rand_grouping(p-7:p));[ignore,idx] = min(dists);best_of_8_rte = rtes(idx,:);best_of_8_brk = brks(idx,:);rte_ins_pts = sort(ceil(n*rand(1,2)));I = rte_ins_pts(1);J = rte_ins_pts(2);for k = 1:8 % Generate New Solutionstmp_pop_rte(k,:) = best_of_8_rte;tmp_pop_brk(k,:) = best_of_8_brk;switch kcase 2 % Fliptmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J));case 3 % Swaptmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]);case 4 % Slidetmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]);case 5 % Modify Breakstmp_pop_brk(k,:) = randbreaks();case 6 % Flip, Modify Breakstmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J));tmp_pop_brk(k,:) = randbreaks();case 7 % Swap, Modify Breakstmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]);tmp_pop_brk(k,:) = randbreaks();case 8 % Slide, Modify Breakstmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]);tmp_pop_brk(k,:) = randbreaks();otherwise % Do Nothingendendnew_pop_rte(p-7:p,:) = tmp_pop_rte;new_pop_brk(p-7:p,:) = tmp_pop_brk;endpop_rte = new_pop_rte;pop_brk = new_pop_brk;
endif show_res% Plotsfigure('Name','MTSPF_GA | Results','Numbertitle','off');subplot(2,2,1);if dims == 3, plot3(xy(:,1),xy(:,2),xy(:,3),'k.');else plot(xy(:,1),xy(:,2),'k.'); endtitle(' Locations');subplot(2,2,2);imagesc(dmat([1 opt_rte],[1 opt_rte]));title('Distance Matrix');subplot(2,2,3);rng = [[1 opt_brk+1];[opt_brk n]]';for s = 1:salesmenrte = [1 opt_rte(rng(s,1):rng(s,2)) 1]if dims == 3, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:));else plot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:)); endtitle(sprintf('Total time = %1.4f',min_dist));hold on;endif dims == 3, plot3(xy(1,1),xy(1,2),xy(1,3),'ko');else plot(xy(1,1),xy(1,2),'ko'); endsubplot(2,2,4);
plot(dist_history,'b','LineWidth',2);title('Best Solution History');set(gca,'XLim',[0 num_iter+1],'YLim',[0 1.1*max([1 dist_history])]);
end% Return Outputs
if nargoutvarargout{1} = opt_rte;varargout{2} = opt_brk;varargout{3} = min_dist;
end% Return Outputs
if nargoutvarargout{1} = opt_rte;varargout{2} = opt_brk;varargout{3} = min_dist;
end% Generate Random Set of Break Pointsfunction breaks = randbreaks()if min_tour == 1 % No Constraints on Breakstmp_brks = randperm(n-1);breaks = sort(tmp_brks(1:num_brks));else % Force Breaks to be at Least the Minimum Tour Lengthnum_adjust = find(rand < cum_prob,1)-1;spaces = ceil(num_brks*rand(1,num_adjust));adjust = zeros(1,num_brks);for kk = 1:num_brksadjust(kk) = sum(spaces == kk);endbreaks = min_tour*(1:num_brks) + cumsum(adjust);endend
end

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/22744.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2021年MathorCup高校数学建模挑战赛——大数据竞赛赛道A -思路分享

4.8号公布了复赛获奖名单&#xff0c;比赛正式告一段落&#xff0c;为什么现在才开始写呢&#xff1f;其实一是最近一直很忙&#xff0c;二是感觉自己做的不咋地&#xff0c;趁今天有空就写写吧&#xff0c;时间一长就又不想写了。 好了胡扯到此结束&#xff0c;言归正传&#…

第五届“传智杯”全国大学生计算机大赛(练习赛)传智杯 #5 练习赛] 平等的交易

[传智杯 #5 练习赛] 平等的交易 题目描述 你有 n n n 件道具可以买&#xff0c;其中第 i i i 件的价格为 a i a_i ai​。 你有 w w w 元钱。你仅能用钱购买其中的一件商道具。当然&#xff0c;你可以拿你手中的道具换取其他的道具&#xff0c;只是这些商道具的价值之和&…

数学建模相关比赛汇总(含各赛事官方网站链接)

前言 官网可以进行资料下载&#xff0c;历年的建模题等可在官网下载&#xff1b; 注册、报名、缴费、选题、显示论文收到与否、最新Summary论文模板的下载、查询获奖结果。 按含金量笔者分为四个梯队&#xff0c;如有不妥&#xff0c;请发私信联系楼主。 第一梯队&#xff1a;…

MathorCup高校数学建模挑战赛——大数据竞赛 赛道A 移动通信基站流量预测baseline

文章目录 前言一、简单分析二、具体程序1.引入库2.读入数据3.数据处理4.模型训练和预测5.结果文件输出 总结 前言 本文给出2020年MathorCup高校数学建模挑战赛——大数据竞赛中的赛道A移动通信基站流量预测的baseline&#xff0c;这个题目的具体描述和数据集请见链接。 整个程…

2022年第三届MathorCup高校数学建模挑战赛——大数据竞赛 赛道B 北京移动用户体验影响因素研究 问题一建模方案及代码实现详解

【BetterBench原创】2022年第三届MathorCup高校数学建模挑战赛——大数据竞赛 赛道B 北京移动用户体验影响因素研究 建模方案及代码实现&#xff08;更新中&#xff09; 更新进展 2022年12月21日 12:20 发布问题一、二思路及问题一的python代码实现 2022年12月22日 15:00 发…

鬼畜提问变身指南:ChatGPT十个打破常规的提问公式

Chatgpt的恐怖之处不在于它有多么的准确&#xff0c;很多时候它的回答甚至充满常识性错误&#xff0c;比如你问美国为什么轰炸珍珠岛它都能一本正经的回答你&#xff08;这当然也有中文语料数据投喂不足和中文本身就复杂而难以理解的原因&#xff0c;听说用英文提问的准确性会提…

ChatGPT怎么用?30句提问公式,一定有你的行业能用到的一句

在使用ChatGPT过程中&#xff0c;总感觉用ChatGPT的效果没有那么好。经过多次使用和摸索&#xff0c;终于发现了问题&#xff0c;原来不是ChatGPT不好用&#xff0c;效果不好&#xff0c;而是因为我之前不会提问。 话不多说&#xff0c;给大家准备了30句ChatGPT提问公式&#…

pdfGPT|无需阅读,让 PDF 和自己对话

目前 ChatGPT 无法直接与外部数据进行交互。如果我们能将自己的数据投喂给它&#xff0c;并且让它根据数据与我们对话&#xff0c;那么我们就能将 ChatGPT 变成自己的知识库。这种方法将使 ChatGPT 更加智能化和可定制化&#xff0c;更好地满足用户的需求。 因 OpenAI gpt-3.5…

学生作业形同虚设!ChatGPT作弊成风!OpenAI:正在自研审核工具

本文来源 机器之心 编辑&#xff1a;泽南、蛋酱 「对学生有负面影响」&#xff0c;这么大责任 OpenAI 可担不起。 语言生成模型来了&#xff0c;学校的作业会不会从此变得形同虚设&#xff1f;近日&#xff0c;纽约市教育官员宣布禁止学生在公立学校使用 ChatGPT 的事件引发了…

聚观早报|马斯克将TruthGPT挑战ChatGPT;腾讯披露自研芯片新进展

今日要闻&#xff1a;马斯克将TruthGPT挑战ChatGPT&#xff1b;苹果在印度年销售额近60亿美元&#xff1b;腾讯披露自研芯片沧海最新进展&#xff1b;特斯拉中国工厂普通工人月薪约1万元&#xff1b;飞猪将直接向阿里CEO张勇汇报 马斯克将TruthGPT挑战ChatGPT 4 月 18 日消息&…

微信公众号(一)每日推送详细教程(含实时定位,天气预报,每日英语,纪念日等,可快速自定义消息模板并指定订阅者类型发送)

微信公众号&#xff08;一&#xff09;每日推送&#xff0c;天气推送 &#xff08;含实时定位&#xff0c;天气预报&#xff0c;每日英语&#xff0c;纪念日等&#xff0c;可快速自定义消息模板并指定订阅者类型发送&#xff09;&#xff0c;另有小白网页版配置 版本介绍1. 相关…

《花雕学AI》用AI创造清晨的美好:ChatGPT+DALL-E 2 生成“早上好”的场景图

早晨是一天中最美好的时刻&#xff0c;也是最适合与AI对话的时刻。想象一下&#xff0c;当你醒来&#xff0c;打开手机&#xff0c;就能看到一个AI为你生成的“早上好”的场景图&#xff0c;是不是很温馨&#xff1f;这就是ChatGPTDALL-E 2&#xff08;新Bing&#xff09; 的魅…

我踩过的那些坑,浅谈一下如何更优雅地使用 Linux

前言 相信很多尝鲜过桌面 Linux 系统的朋友&#xff0c;对它一个很深刻的印象就是稳定性差&#xff1a;不知道怎么就把系统搞崩了&#xff0c;又找不到问题的具体原因和解决方法&#xff0c;只能尝试重装&#xff0c;直到心力交瘁地回到了 Windows 或 macOS。但另一方面&#…

李开复筹组 AI 2.0 全新平台,“零一万物”重磅上线!

「如同 Windows 带动了 PC 普及&#xff0c;Android 催生了移动互联网的生态&#xff0c;AI 2.0 将诞生比移动互联网大十倍的平台机会&#xff0c;将把既有的软件、使用界面和应用重写一次&#xff0c;也将诞生新一批 AI-first 的应用&#xff0c;并催生由 AI 主导的商业模式」…

AIGC领域最大收购:Databricks 13亿美元收购MosaicML,成立仅2年员工60人

Databricks CEO表示&#xff1a;“该交易旨在将企业数据与服务连接起来&#xff0c;帮助它们构建自己更便宜的语言模型。” 整理 | 梦依丹 出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09; 大数据巨头 Databricks 宣布以 13 亿美元收购人工智能初创公司 MosaicML。…

2022年智源社区年度热点推荐丨新春集锦

本文为2022年最受智源社区小伙伴喜爱的文章&#xff0c;根据文章质量和热门程度等维度计算得出。还有AI大佬的全年总结盘点总结&#xff0c;也一并推荐给你。虎年除旧&#xff0c;兔年迎新&#xff0c;藉此机会、智源编辑组全员谨祝大家新春快乐&#xff01; 2022 智源社区20篇…

估值超 80 亿独角兽爆雷!靠“吹牛”骗取 10 亿融资,2000 万月活中 95% 是“机器人”...

整理 | 郑丽媛 出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09; “一家初创型企业&#xff0c;想要获得 10 亿融资&#xff0c;需要具备什么&#xff1f;” 对于这个问题&#xff0c;曾放话对标 Facebook 的即时通讯应用 IRL&#xff08;IN REAL LIFE&#xff09;来…

AIGC大记事【2023-0625】【第五期】:《时代》专访ChatGPT之父:人工智能影响经济还需要很多年

大咖观点&#xff1a; 《时代》专访ChatGPT之父&#xff1a;人工智能影响经济还需要很多年孙正义&#xff1a;我每天和ChatGPT聊天&#xff0c;一场巨大革命即将到来&#xff0c;软银“终将统治世界&#xff01;”刘慈欣谈 ChatGPT&#xff1a;人类的无能反而是人类最后的屏障A…

GPT4结对编程实战,鹅厂一线研发真实使用感受

ChatGPT4相比ChatGPT3.5在逻辑推理能力上有很大的进步&#xff0c;其代码生成能力颇为优越。因此作者尝试在工作中某些不涉密的基础工作上&#xff0c;应用ChatGPT4来提升研发效率&#xff0c;简单尝试之后发现其在不少场景是有效的。本文将向大家展示如何充分利用 ChatGPT-4 结…

借助ChatGPT提高编程效率指南

一、借助ChatGPT提高编程效率指南 随着计算机技术的飞速发展&#xff0c;编程已经成为了现代社会中一个非常重要的技能。对于许多人来说&#xff0c;编程不仅是一项工作技能&#xff0c;而且是一种生活方式。然而&#xff0c;即使是最有经验的程序员&#xff0c;也会在编写代码…