关 键 词：

2015 上海 大学生 数模 竞赛 培训

资源描述：

2015上海大学生数模竞赛培训,2015,上海,大学生,数模,竞赛,培训

内容简介：

数模竞赛中的图论问题 上海海事大学丁颂康skding 一 图上的问题 案例一钢管的订购和运输 CMCM00 B 1 问题的提出 铁路运价 万元 单位 1000 以上每增加1 100 运价增加5万元公路运价1单位钢管每 0 1万元 不足1 部分按1 计算 2 分析和建模 购运费用 最短路问题 shortestpath Dijkstra算法和Floyd Warshell算法 标号法和矩阵运算法 解决实际问题的局限性方案选择 线性规划 二次规划 略 案例二扫雪车 SnowPlowingMCM1990 B 1 问题的提出 上图是WicomicoCounty StateofMaryland 的公路图 一场大雪以后 需要出动扫雪车进行清扫 如果道路两边需要来回各清扫一遍 并且出动两辆扫雪车 应该如何安排任务 2 分析和建模 Eulertour和Euler迹的Fleury算法除非没有别的选择 不走剩下图的割边 中国邮递路线问题 管梅谷1960 ChinesePostmanProblem Euler问题和边的行遍性 七桥问题 3 原问题的求解 单车单程 等同于邮路问题 单车双程 有向Euler图 双车双程 边的分配 单车双程 简化 原图中去掉尽可能大的Euler子图 案例三通讯网络的最小Steiner树 MCM1991 B 一 问题的提出9个通讯站位于以下坐标点处 要设计一个连接这9个通讯站的局部网络 使总费用最省 假定连线费用与距离成正比 二 问题的分析和建模最小连接问题 树 连通无圈图 树的性质 1 任意两点间存在唯一的路 2 边数等于点数减1 3 任意去掉一条边 树就变得不连通 4 任意去掉一个非悬挂点 树就变得不连通 5 任意添加一条边 就可得到唯一的圈 注 3 4两条性质说明 就连通的意义而言 树具有极小性 子图 生成子图 生成树最小生成树最小生成树的Kruskal算法和管梅谷算法 避圈和破圈三角形中到三个顶点距离之和最小的点 Steiner点推广 Steiner树直角距离 竞赛中的其它图论问题 灾情巡视路线 1998CMCM B 点的行遍性乘公交 看奥运 2007CMCM B 最短路算法交巡警服务平台的设置与调度 2011 B 最短路算法 二 可以用图论方法讨论的问题 案例四锁具装箱 CMCM1994 B 1 问题的提出一种弹子锁的钥匙有5个槽 每个槽的高度可以用1 6中的某个数表示 工艺及其它原因 5个槽的高度还有两个限制 1 至少有3个不同的数 2 相邻两槽的高度差不能为5 满足以上条件的不同锁具称为一批 两把锁能够互开的条件是 5个槽的高度有4个相同另一个槽的高度差1 问题是 1 每一批锁共有多少把 2 如何尽可能避免同一顾客买到的锁具互开 3 图论中的相关结果二分图二分图完美对集的存在性 Hall定理最大独立集 Konig定理 1931 Inabipartitegraph thenumberofedgesinamaximummatchingisequaretothenumberofverticesinaminimumcovering 2 分析与建模一批锁具的数量 组合计数 略 互开的条件 案例五足球队排名次 SMCM1993 B 1 问题的提出 竞赛图 tournament 邻接矩阵 adjecencymatrix 当且仅当有弧从 指向 2 分析与建模 得分向量逐级得分向量可以证明 其中是全1向量 的第i j个元素是的长度为k的有向路的条数 定理1假设A是点数不小于5的双向连通竞赛图D的邻接矩阵 那么 其中 d是D的有向直径 定理2 Perron Frobenius定理 本原矩阵A的最大特征根r是一个正的实数 进而有其中 s是A对应于r的正特征向量 上例中 点数小于5或非双向连通的情况 谢谢 2015 9 4 1 常微分方程模型选讲 兼简谈差分方程建模 2 方程模型主要适用的对象 动态系统 动态系统 与时间 or and空间 有关的系统建立动态模型的目的描述对象随时间 or and空间 的演变过程分析对象的变化规律预报对象的未来性态研究控制对象的方法等 3 常见的动态模型 确定性模型 微分方程常微分方程偏微分方程差分方程随机性模型 随机过程 4 动态 变化与数学工具 连续对象 函数 函数的变化率 导数 微分方程离散对象 数列 差分 差分方程两者互相转化 基础概念 两类变化率概念 变化率设自变量t有微小改变量 t时 因变量W的改变量 W W对t的变化率有单位相对变化率相对数 6 实践中的变化率 速度 增长率 速率 衰变率 边际 弹性 利率 出生率 等 7 本次讲座内容 传染病模型建模方法参数选择解模与模型研究灵敏度讨论鱼雷击舰问题人口问题和生态问题常微分方程建模步骤 8 例一 传染病模型 按照传染病传播规律 特点建立适当的数学模型描述传染病的传播过程 分析病人数的变化规律 预报传染病传播高潮到来的时刻研究用隔离 药物治疗 注射疫苗等措施后对传染病蔓延的影响帮助寻找控制传染病的有效方法 问题和目标 9 传染病模型I 假设 单位时间新增病人数与现有病人数成正比 比例系数为 日传染率 平均一个病人一天传染给几个健康人得病 记号 t时刻的病人数为i t 函数 建模 指数增长模型 10 问题1 模型中的l如何确定 11 如何利用实际数据确定l 按上述公式选择适当的t 采用部分数据确定l采用全部数据按统计方法确定l先确定解的形式 再用函数拟合方法求出其中参数选取l的效果可用模型计算解 理论值 和实际数据之间的误差予以检验 12 13 区分人口中的病人和健康人 问题2 问题 人口总数有限 传染机制 通过病人与健康人的接触使病人数增加 健康人减少 14 传染病模型II 假设 总人口数N不变 病人i 健康人 N i新增病人数与现有病人数成正比 其比例系数记为k k与健康人占总人口比例成正比 即k l N i N OR新增病人数与两种人数的乘积成正比 建模 Logistic模型 15 数学模型简化 无量纲化 16 解模 17 解的图像 18 利用Matlab求积分 int 1 k u 1 u 1 k log u 1 k log 1 u solve t 1 k log u 1 k log 1 u 1 1 exp t k exp t k solve t 1 k log u 1 k log 1 u 1 k log a 1 k log 1 a a exp t k 1 a exp t k 19 选择参数利用Matlab画图 ezplot 1 1 exp 0 2 t 1 0 1 0 1 0 40 20 利用Matlab直接求微分方程解 dsolve Du k u 1 u t 1 1 exp k t C1 dsolve Du k u 1 u u 0 a 1 1 exp k t 1 a a 21 模型的理论研究 病人数何时增加得最快 当i 1 2 即病人数为总人口一半 时 传染病爆发达到高潮 di dt增速达到最大 tm的计算 病人始终增加 22 设当t tm时对应i 1 2 即tm时传染病爆发达到高潮 tm 23 问题3 病人不可治愈 24 传染病模型III 传染病无免疫性 病人治愈成为健康人 健康人可再次被感染 无免疫性 增加假设 单位时间病人治愈的比例为 一天平均有多少比例的病人可以治愈 建模 SIS模型 25 参数解释 日传染率 平均一个病人一天传染给几个健康人得病 1 感染期 感染期内每天平均每个病人传染的人数 称为传染数 一天平均有多少比例的病人可以治愈 26 方程求解 27 解的研究 情况1 传染数s 1 28 传染数s 1 29 用matlab计算例子 l 0 4s 1 2 11 1 s 0 1667i0 0 2 上图 0 1 下图 ezplot 1 6 exp 1 15 t 0 100 上图 ezplot 1 6 4 exp 1 15 t 0 100 下图 30 解的研究 情况2 传染数s 1 31 发展趋势 32 用matlab计算例子 l 0 4s 0 8 ezplot 1 4 9 exp 1 10 t 0 100 上图 ezplot 1 6 4 exp 1 15 t 0 100 下图 33 模型的意义 传染病机制解释 传染病终趋消失的条件 1 感染因素弱于治疗因素 传染病无法消亡的情况 1 感染因素强于治疗因素 34 微分方程建模步骤 根据建模目的和问题分析作简化假设根据函数及其变化率之间的关系建立方程定解条件按照正确方法解微分方程讨论解的性质 35 方程建模应注意 物理量纲 在等式两边中应注意物理单位相同 比例系数有时也是有量纲单位的列出定解条件 定解条件是系统在某一特定时刻或 和 边界上的信息 独立于方程 用以确定有关通解中的常数 为了完整充分地给出问题的数学陈述 应将这些给定的条件和方程一起列出 36 微分方程的进一步分析 对初值 参数依赖性的灵敏度分析可能会引起解的较大变化 也可能不大影响解的值对求解过程中的误差控制有一定的要求方法可以写出解对初值 参数的导数公式并作讨论 或用不同初值 参数求解 并作比较对有平衡态的情况 作稳定性分析可参考任何一本比较详细的常微分方程教科书 模型检验 37 措施效果预测 38 灵敏度分析 39 40 药物模型I 假设 单位时间药物浓度减速与现有浓度成正比记号 t时刻的浓度i t 函数 负指数增长模型 图像 41 42 例二 鱼雷击舰问题 问题 如图所示 一敌舰在某海域内沿正北方向航行时 我方战舰恰位于敌舰正西方1海里处 我舰向敌舰发射制导鱼雷 敌舰速度为0 42海里 分钟 鱼雷速度为敌舰速度的2倍 鱼雷的运行方向始终指向敌舰 试问敌舰航行多远时将被击中 43 建模目的 研究x y随t变化的关系 假设 鱼雷的运行方向始终指向敌舰设敌舰速度v0 鱼雷速度v为常数记号 建立坐标系后 敌舰速度为v0 t时刻敌舰的位置为 1 v0t 鱼雷速度为v 2v0 t时刻鱼雷的位置为 x y 模型假设与记号 44 1 建立微分方程模型 45 解模 46 2 模型求解 问题解答 当x 1时 y 2 3 时间t y v0 1 59分 95 24秒时鱼雷击中敌舰 47 Matlab求解 dsolve D2u sqrt 1 Du Du 2 1 t u 0 0 Du 0 0 ans 1 3 i 2 t 1 t 1 2 2 3 1 3 2 t 1 t 1 2 2 3 48 3 建立计算机模拟模型 鱼雷的初始位置 0 0 tk时刻鱼雷的位置为 xk yk 运动方向的方向角a tk时刻敌舰的位置为 1 v0tk 初始位置 1 0 49 计算机模拟 50 计算机模拟敌舰 51 计算机模拟鱼雷 52 历届数模竞赛中与微分方程有关的问题 注意 不一定纯粹为微分方程问题 和统计 计算方法等知识结合起来1996A最优捕鱼策略2003ASARS的传播2006B艾滋病疗法的评价及疗效的预测2007A中国人口增长预测 1 常微分方程模型选讲 兼简谈差分方程建模 2 方程模型主要适用的对象 动态系统 动态系统 与时间 or and空间 有关的系统建立动态模型的目的描述对象随时间 or and空间 的演变过程分析对象的变化规律预报对象的未来性态研究控制对象的方法等 3 常见的动态模型 确定性模型 微分方程常微分方程偏微分方程差分方程随机性模型 随机过程 4 动态 变化与数学工具 连续对象 函数 函数的变化率 导数 微分方程离散对象 数列 差分 差分方程两者互相转化 基础概念 两类变化率概念 变化率设自变量t有微小改变量 t时 因变量W的改变量 W W对t的变化率有单位相对变化率相对数 6 实践中的变化率 速度 增长率 速率 衰变率 边际 弹性 利率 出生率 等 7 本次讲座内容 传染病模型建模方法参数选择解模与模型研究灵敏度讨论鱼雷击舰问题人口问题和生态问题常微分方程建模步骤 8 例一 传染病模型 按照传染病传播规律 特点建立适当的数学模型描述传染病的传播过程 分析病人数的变化规律 预报传染病传播高潮到来的时刻研究用隔离 药物治疗 注射疫苗等措施后对传染病蔓延的影响帮助寻找控制传染病的有效方法 问题和目标 9 传染病模型I 假设 单位时间新增病人数与现有病人数成正比 比例系数为 日传染率 平均一个病人一天传染给几个健康人得病 记号 t时刻的病人数为i t 函数 建模 指数增长模型 10 问题1 模型中的l如何确定 11 如何利用实际数据确定l 按上述公式选择适当的t 采用部分数据确定l采用全部数据按统计方法确定l先确定解的形式 再用函数拟合方法求出其中参数选取l的效果可用模型计算解 理论值 和实际数据之间的误差予以检验 12 13 区分人口中的病人和健康人 问题2 问题 人口总数有限 传染机制 通过病人与健康人的接触使病人数增加 健康人减少 14 传染病模型II 假设 总人口数N不变 病人i 健康人 N i新增病人数与现有病人数成正比 其比例系数记为k k与健康人占总人口比例成正比 即k l N i N OR新增病人数与两种人数的乘积成正比 建模 Logistic模型 15 数学模型简化 无量纲化 16 解模 17 解的图像 18 利用Matlab求积分 int 1 k u 1 u 1 k log u 1 k log 1 u solve t 1 k log u 1 k log 1 u 1 1 exp t k exp t k solve t 1 k log u 1 k log 1 u 1 k log a 1 k log 1 a a exp t k 1 a exp t k 19 选择参数利用Matlab画图 ezplot 1 1 exp 0 2 t 1 0 1 0 1 0 40 20 利用Matlab直接求微分方程解 dsolve Du k u 1 u t 1 1 exp k t C1 dsolve Du k u 1 u u 0 a 1 1 exp k t 1 a a 21 模型的理论研究 病人数何时增加得最快 当i 1 2 即病人数为总人口一半 时 传染病爆发达到高潮 di dt增速达到最大 tm的计算 病人始终增加 22 设当t tm时对应i 1 2 即tm时传染病爆发达到高潮 tm 23 问题3 病人不可治愈 24 传染病模型III 传染病无免疫性 病人治愈成为健康人 健康人可再次被感染 无免疫性 增加假设 单位时间病人治愈的比例为 一天平均有多少比例的病人可以治愈 建模 SIS模型 25 参数解释 日传染率 平均一个病人一天传染给几个健康人得病 1 感染期 感染期内每天平均每个病人传染的人数 称为传染数 一天平均有多少比例的病人可以治愈 26 方程求解 27 解的研究 情况1 传染数s 1 28 传染数s 1 29 用matlab计算例子 l 0 4s 1 2 11 1 s 0 1667i0 0 2 上图 0 1 下图 ezplot 1 6 exp 1 15 t 0 100 上图 ezplot 1 6 4 exp 1 15 t 0 100 下图 30 解的研究 情况2 传染数s 1 31 发展趋势 32 用matlab计算例子 l 0 4s 0 8 ezplot 1 4 9 exp 1 10 t 0 100 上图 ezplot 1 6 4 exp 1 15 t 0 100 下图 33 模型的意义 传染病机制解释 传染病终趋消失的条件 1 感染因素弱于治疗因素 传染病无法消亡的情况 1 感染因素强于治疗因素 34 传染病模型IV 增加假设 病人治愈后不会再被感染三种人 健康人 病人和病愈者总人数N不变 记病人 健康人和病愈者的比例分别为记病人的日传染 日治愈率 传染数 需建立含的两个方程 常微分方程组 SIR模型 35 建模 变化率 36 解模 s t i t 可以看做 s i 平面上的曲线 相轨线 的参数式 37 研究模型 相轨线方程 38 在D内作相轨线 s t i t 可以看做 s i 平面上的曲线 相轨线 的参数式 相轨线 39 相轨线走势 40 最大病人数条件 41 相轨线分析 s t 单调减 相轨线向左变化 im P3 相轨线起点在斜线附近 42 相轨线分析结论 P2 s0 1 s i t 单调降至0 43 相轨线分析结论 P1 s0 1 s i t 先升后降至0 1 s 阈值 44 模型的意义 预防传染病蔓延 日传染率 隔离 日治愈率 提高医疗水平 传染病不蔓延的条件 s0 1 的估计 降低s0 提高r0 提高阈值1 打预防针 群体免疫 更多传染病模型 SEIR 45 46 SEIRD模型 47 微分方程建模步骤 根据建模目的和问题分析作简化假设根据函数及其变化率之间的关系建立方程定解条件按照正确方法解微分方程讨论解的性质 48 方程建模应注意 物理量纲 在等式两边中应注意物理单位相同 比例系数有时也是有量纲单位的列出定解条件 定解条件是系统在某一特定时刻或 和 边界上的信息 独立于方程 用以确定有关通解中的常数 为了完整充分地给出问题的数学陈述 应将这些给定的条件和方程一起列出 49 微分方程的进一步分析 对初值 参数依赖性的灵敏度分析可能会引起解的较大变化 也可能不大影响解的值对求解过程中的误差控制有一定的要求方法可以写出解对初值 参数的导数公式并作讨论 或用不同初值 参数求解 并作比较对有平衡态的情况 作稳定性分析可参考任何一本比较详细的常微分方程教科书 模型检验 50 措施效果预测 51 灵敏度分析 52 53 例二 鱼雷击舰问题 问题 如图所示 一敌舰在某海域内沿正北方向航行时 我方战舰恰位于敌舰正西方1海里处 我舰向敌舰发射制导鱼雷 敌舰速度为0 42海里 分钟 鱼雷速度为敌舰速度的2倍 鱼雷的运行方向始终指向敌舰 试问敌舰航行多远时将被击中 54 建模目的 研究x y随t变化的关系 假设 鱼雷的运行方向始终指向敌舰设敌舰速度v0 鱼雷速度v为常数记号 建立坐标系后 敌舰速度为v0 t时刻敌舰的位置为 1 v0t 鱼雷速度为v 2v0 t时刻鱼雷的位置为 x y 模型假设与记号 55 1 建立微分方程模型 56 解模 57 2 模型求解 问题解答 当x 1时 y 2 3 时间t y v0 1 59分 95 24秒时鱼雷击中敌舰 58 Matlab求解 dsolve D2u sqrt 1 Du Du 2 1 t u 0 0 Du 0 0 ans 1 3 i 2 t 1 t 1 2 2 3 1 3 2 t 1 t 1 2 2 3 59 3 建立计算机模拟模型 鱼雷的初始位置 0 0 tk时刻鱼雷的位置为 xk yk 运动方向的方向角a tk时刻敌舰的位置为 1 v0tk 初始位置 1 0 60 计算机模拟 61 计算机模拟敌舰 62 计算机模拟鱼雷 63 类似问题 问题 如图所示 一条猎犬发现它的正西方1里处有一只野兔正朝北边1里处的兔巢逃奔 猎犬随即朝兔子奔走方向追赶 已知兔子奔跑速度为0 42里 分钟 猎犬速度为兔子速度的2倍 试问猎犬能否在野兔逃回兔巢前追上野兔 64 类似问题 问题 1988AMCM A 确定毒品走私位置 走私船走向随机发现范围是一个区域寻找最大可能发现毒品船对策略 65 例三 人口问题和生态问题 马尔萨斯人口模型有资源限制的人口模型勒斯里模型 66 前两种模型 67 勒斯里模型 人口与年龄 时间有关 两个自变量归结为含偏导数的微分方程 偏微分方程 参考文献 离散化后得到差分方程 勒斯里模型简化了的勒斯里模型假设 三种鱼 一龄鱼 二龄鱼 三龄鱼只有二龄鱼能生育 68 简化了的勒斯里模型 N1的说明 对t积分离散化 按1年周期计算 69 生态模型与ode45的用法 u0 1 1 u0 11 t u ode45 aa 0 6 u0 plot t u functionrw aa t u rw 3 2 u 2 u 1 2 5 u 1 u 2 70 71 相轨线 72 历届数模竞赛中与微分方程有关的问题 注意 不一定纯粹为微分方程问题 和统计 计算方法等知识结合起来1996A最优捕鱼策略2003ASARS的传播2006B艾滋病疗法的评价及疗效的预测2007A中国人口增长预测 ?(?)?“?”.?(?),?100 mm?4?A, C, D, E?12 mm?AC?A?30 mm?B?12 mm?1ABCDE?(1)?(2)?(3)?AAA K?XXXXXXXXXXXXXXXX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .OxyzPp?P?(x,y,z),?p?(u,v,f),x = tuy = tvz = tfu =fxzv =fyz?(H1)?z 0.2(H2)?(?)?(?)?3.1?u1u2u3v1v2v3111?=?x1fz1x2fz2x3fz3y1fz1y2fz2y3fz3111?=f2z1z2z3?x1x2x3y1y2y3z1z2z3?=f2z1z2z3?x1x2(1 t)x1+ tx2y1y2(1 t)y1+ ty2z1z2(1 t)z1+ tz2?= 0?3.2?3.3?aaaaaaaaaaPQSQSO3?(x0,y0,z0)?R?ax + by + cz = p?a2+ b2+ c2= 1, p 6= 0.?u0=fx0z0,v0=fy0z0?u0=f(x0z0+ acR2)z20 (a2+ b2)R2,v0=f(y0z0+ bcR2)z20 (a2+ b2)R2?a = b = 0, c = 1?u0=fx0z0,v0=fy0z0?u0fx0z0?=?fR2z0acz0+ (a2+ b2)x0z20 (a2+ b2)R2?v0fy0z0?=?fR2z0bcz0+ (a2+ b2)y0z20 (a2+ b2)R2?4.1?4.2?(?)?4.3?4.4?(?)?4.5?(?)?4?ax2+ 2bxy + cy2+ 2dx + 2ey + f = 0Ax2+ 2Bxy + Cy2+ 2Dx + 2Ey + F = 0?y = kx + l(a + 2bk + ck2)x2+ 2(bl + ckl + d + ek)x + cl2+ 2el + f = 0(bl + ckl + d + ek)2 (a + 2bk + ck2)(cl2+ 2el + f) = 0e ak2+ 2ebkl + e cl2+ 2edk + 2e el +ef = 0eAk2+ 2eBkl +eCl2+ 2eDk + 2eEl +eF = 0?kxy +l,?4.6?O?l1?l2?Ai, Bi, Ci, Di(i = 1,2),?CR(A1,B1,C1,D1) = CR(A2,B2,C2,D2)?CR(A,B,C,D) =|AC|AD|BD|BC|? ?BBBBBBBBBBBBBOA1B1C1D1A2B2C2D2l1l25?l1?y = kx + l?OA1, OB1, OC1, OD1?y = ax,y = bx,y = cx,y = dx?CR(A,B,C,D) =|AC|AD|BD|BC|=|c a|d b|d a|c b|?ax + by + cz = p?a2+ b2+ c2= 1, p 6= 0.?(x0,y0,z0),?R.?(x,y,z),?(u,v,f).u =fxz,v =fyzx =ufz,y =vfz?ufz x0?2+?vfz y0?2+ (z z0)2= R2aufz +bvfz + cz = pz =pqfq = au + bv + cf?pqu x0?2+?pqv y0?2+?pqf z0?2= R2(pu x0q)2+ (pv y0q)2+ (pf z0q)2= R2q2?(x0,y0,z0,a,b,c),?(puj x0qj)2+ (pvj y0qj)2+ (pf z0qj)2= R2q2j,j = 1,2, ,N?a2+ b2+ c2= 1?p = ax0+ by0+ cz0,qj= auj+ bvj+ cf6?(x0,y0,z0,a,b,c),?minF(a,b,c,x0,y0,z0) =NXj=1(puj x0qj)2+ (pvj y0qj)2+ (pf z0qj)2 R2q2j2?a2+ b2+ c2= 1?(u0,v0) =?fx0z0,fy0z0?x = (x,y,z),?X = (X,Y,Z).x = RX + T?R?T?(u,v)?(U,V ),?x0= (x0,y0,z0)?X0= (X0,Y0,Z0).u =fx0z0,v =fy0z0U =FX0Z0,V =FY0Z0x0= z0?uf,vf,1?X0= Z0?UF,VF,1?x0= RX0+ T?z0?Z0,?x0?X0.?7?X = (X,Y,Z)?x = (x,y,z).?(Xi,Yi,0),?(ui,vi).?uizif,vizif,zi?.x = RX + T?R =r11r12r13r21r22r23r31r32r33,T = (t1,t2,t3)uifvif1zi= RXiYi0+ Tuizif= r11Xi+ r12Yi+ t1vizif= r21Xi+ r22Yi+ t2zi= r31Xi+ r32Yi+ t3(ui(r31Xi+ r32Yi+ t3) = f(r11Xi+ r12Yi+ t1),vi(r31Xi+ r32Yi+ t3) = f(r21Xi+ r22Yi+ t2),i = 1,2, ,NRR= I?x1= (x1,y1,z1)?x2= (x2,y2,z2)x1= R1X + T1x2= R2X + T2x2= Rx1+ T?R = R2R1,T = T2 R2R1T1?8?(?),?1.?2.?3.?4.?9?(?)?1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23456789101112rOrArBrC?1?(300,400)?2002?(550,450),?703?(360,240)?140?(400,330)4?(280,100)?(345,210)?(410,100)5?(80,60)?1506?(60,300)?(150,435)?(235,300).? = 0,800 0, 800,?12?1?N,?N = 12.?4?(?)?10?a.?a.?v() =v01 + e100.12?O(0,0), A(300,300), B(100,700), C(700,640),(1)?O?A, B, C?(2)?O?A, B, C,?O?(3)?O?A?i(1 i N),?(?)?e i= P | d(P,i) a?e =Ni=1e i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6?a-a. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7. . . . . . . . . . . . . . . . . . . . . . . . .8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9. . . . . . . . . . . . . . . . . . . . . . . . .10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12. . . . . . . . . . . . . . . . . . . . . . . . . .rOrArBrC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .rOrA5DEl1DEl2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .rOrASDEPQl|gOP| |OP| |OD|,|gAQ| |AQ| |AE|gPQ| =?Z21p2+ 2d?Z21d?Z21ad?= a|2 1| = |DE|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .rArBl1l2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .rArB3?1?P1,?P2.?1?P1P2?e,?P1P2?P1, P2?d12= d21= +.?2?P1?e,?n1,?P3, Pn1+2,?d1j= dj1(j = 3, ,n1+ 2).?3?P2?e,?n2,?Pn1+3, ,Pn1+n2+2,?d2j= dj2(j = n1+ 3, n1+ n2+ 2).?4?e?5?n = n1+ n2+ 2n3+ 2.?Pi, Pj(i,j = 1, ,n),?(?)?dij= dji.?6?G = (V,E),?D = (dij)nn,?dij?Pi?Pj?15?+.?7?D?Dijkstra?P1?P2?Q =Q1Q2Qm.?8?Q,?QiQi+1Qj1Qj?Qi+1, ,Qj1,?Qi?Qj.?P1?P2?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6. . . . . . . . . . . . . . . . . . . . . . . . .7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8. . . . . . . . . . . . . . . . . . . . . . . . .9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11. . . . . . . . . . . . . . . . . . . . . . . . . .12rOrArBrC?P1, ,Pk.4?Pi1?Pi?Pi+1,?Pi?Pi?a?Pi(i = 2, ,k 1)?Oi.?Pi?(xi,yi),?Oi?(ui,vi)?(ui= xi+ acosivi= yi+ asini?i(i = 2, ,k 1),?P1?Pi(i = 2, ,k1),?Pk?2?P1,?Pk,?P2, ,Pk1.?1?,?2= = k1= 0,?dmin= +.?2?2, ,k1,?1?26?(V,E)?D.?3?D?Dijkstra?Pi?Pi+1?di(i = 1, ,k 1),?d =k1Xi=1di.?4?d dmin,?dmin= d,?2, ,k1.?5?2, ,k1:?i = k 1.(1)?i:= i+ .(2)?i 2,?i := i 1.?i = 0,?(1).(3)?i 2,?2?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6. . . . . . . . . . . . . . . . . . . . . . . . .7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8. . . . . . . . . . . . . . . . . . . . . . . . .9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11. . . . . . . . . . . . . . . . . . . . . . . . . .12eeerOrArBrC5?,?2, k1?0?2?i(i = 2, ,k 1).?(? := /10),?i?i ?i+ ?i(i = 2, ,k 1).?mk2(?m?),?(k 2)m,?i?Pi?i?Pi1?Pi+1?Pi?.