架构设计 相关文档希望互相学习共同进步风123456789-CSDN博客系统架构设计 相关文章【架构专栏】架构考试介绍【架构专栏】架构知识点知识总览​共19章内容主要包括11绪论、2计算机系统、3信息系统、4信息安全技术、5软件工程26数据库设计、7系统架构设计基础知识38系统质量属性与架构评估、9软件可靠性、10软件架构演化与维护、11未来信息综合技术412信息系统架构设计、13层次式架构设计、14云原生架构设计、15面向服务架构设计、16嵌入式系统架构设计、17通信系统架构设计、18安全架构设计、19大数据架构设计每天进步一点点加油小伙伴们本文学习 20.2 数学与经济管理以下为个人笔记希望有所帮助共同学习。20.1 知识产权和标准化20.2 数学与经济管理20.2.1 线性规划例题1云服务器采购成本优化最小化成本类例题2多机房流量调度优化最小化延迟类20.2.2 指派问题例题1. 通用基础场景翻译任务分配例题2. 物流配送场景司机派单例题3. 软件开发场景研发任务分配例题4. 运维场景服务器任务调度例题5. 非标准场景人员不足的任务分配不平衡指派20.2.3 最短路径1. 几何类最短路径初中/竞赛数学场景例题1将军饮马基础题‌‌例题2长方体表面爬行题‌‌例题3‌造桥选址题‌2. 图论类最短路径算法/架构设计场景‌例题4单源最短路径基础题Dijkstra算法适用‌例题5全源最短路径题Floyd算法适用‌例题6负权边场景题Bellman-Ford算法适用‌20.2.4 最小生成树1. Prim普里姆算法2. Kruskal克鲁斯卡尔算法例题1村落网线铺设Kruskal算法求解例题2机房网络布线Prim算法求解20.2.5- 20.2.8 决策论、网络与最大流量、 集合问题、最优解问题架构学习补充知识点​20.1 知识产权和标准化【架构专栏】补充1 知识产权和标准化https://blog.csdn.net/weixin_42081167/article/details/166794839?spm1001.2014.3001.550220.2 数学与经济管理20.2.1 线性规划线性规划是架构设计中做资源最优分配、成本/性能权衡的经典量化方法核心是在资源、性能、成本等线性约束下求解目标函数如总成本最低、资源利用率最高、延迟最小的最优解。典型应用场景包括服务器资源调度、多机房流量分配、云资源采购规划、服务容量规划等。例题1云服务器采购成本优化最小化成本类某互联网公司需要部署新业务经压测测算业务至少需要200核CPU、300GB内存、10TB存储资源。云厂商提供两种服务器实例实例A每台配置4核CPU、 8GB内存、200GB存储单台月成本200元实例B每台配置8核CPU、16GB内存、500GB存储单台月成本350元要求采购的实例总数不超过40台降低运维复杂度问如何采购两种实例在满足业务资源需求的前提下让月度总采购成本最低建模与求解1定义决策变量‌设采购实例A的数量为x台实例B的数量为y台x,y 均为非负整数。2目标函数最小化总成本‌min⁡Z200x350y3约束条件‌4求解结果‌先忽略整数约束用图解法求可行域顶点再验证附近整数点可得最优解为x0y25。资源校验CPU共200核、内存共400GB、存储共12.5TB完全满足业务需求实例总数25台符合运维约束最低月度总成本Z200×0350×258750Z200×0350×258750元。例题2多机房流量调度优化最小化延迟类‌场景‌某公司有两个机房机房A的服务能力为每秒处理1000次请求机房B的服务能力为每秒处理1500次请求当前有三个用户区域区域1每秒请求量800次区域2每秒请求量700次区域3每秒请求量600次。各区域到机房的平均请求延迟如下区域1到A延迟20ms到B延迟50ms区域2到A延迟30ms到B延迟20ms区域3到A延迟40ms到B延迟25ms要求所有请求必须被处理问如何调度各区域到两个机房的流量让全局平均请求延迟最低建模与求解 架构设计中线性规划的通用解题步骤明确决策变量把需要决策的资源分配量、流量比例、实例数量等量化为变量确定目标函数把架构优化目标成本、延迟、资源利用率转化为线性表达式梳理约束条件把容量上限、资源下限、运维规则、SLA要求等转化为线性不等/等式求解验证小规模问题可用图解法求解大规模问题可借助单纯形法或求解器计算最后验证结果是否符合业务实际约束。20.2.2 指派问题指派问题是运筹学中一类特殊的 0-1整数线性规划问题本质是‌“执行者-任务”的一对一最优匹配‌将 n 个任务分配给 n 个执行者要求每人仅承担1项任务、每项任务仅由1人完成最终实现总成本最低或总效率最高的优化目标在架构设计的资源调度、任务分配场景中应用非常广泛。经典求解方法匈牙利算法小规模问题可手工计算核心步骤如下‌行列归约‌每行元素减去该行最小值每列元素减去该列最小值让矩阵中出现尽可能多的0元素。‌试指派‌从仅含1个0的行/列开始圈出独立0元素不同行不同列的0划去同行同列的其他0直到所有0被处理。‌覆盖调整‌若圈出的独立0数量小于n用最少的直线覆盖所有0元素在未被覆盖的元素中找最小值未覆盖区域减去该值直线交叉点加上该值生成新矩阵。‌迭代求解‌重复试指派和覆盖调整步骤直到找到n个独立0元素对应位置即为最优指派方案。非标准场景的转化方法实际架构设计中常遇到非标准指派问题可通过简单转化为标准形式求解‌不平衡指派问题人数≠任务数‌添加虚拟执行者或虚拟任务虚拟节点对应的成本设为0或对应闲置惩罚值将矩阵补为方阵后按标准问题求解。‌最大化收益问题‌用收益矩阵中的最大值减去所有元素将收益矩阵转化为成本矩阵即可按最小化问题求解最终最优分配方案与原最大化问题完全一致。‌禁止分配场景‌若某执行者无法承担某任务将对应位置的成本设为极大值如∞优化过程会自动规避该不可行匹配。例题1. 通用基础场景翻译任务分配有一份中文技术文档需要翻译成 英、日、德、俄 4种语言现有 甲、乙、丙、丁 4名翻译每人仅负责1种语言的翻译不同翻译完成各语种翻译的耗时单位小时如下表求总耗时最短的分配方案。翻译人员英文日文德文俄文甲67112乙4598丙31104丁5982最优解‌甲翻译俄文2小时、乙翻译英文4小时、丙翻译日文1小时、丁翻译德文8小时总耗时15小时。例题2. 物流配送场景司机派单‌场景‌配送中心有4名司机需要给4个用户送货每个司机仅负责1个用户的配送任务各司机到不同用户的配送时间单位分钟如下求总配送时间最短的派单方案。司机用户1用户2用户3用户4司机14875司机23692司机35267司机46438最优解‌司机1配送用户14分钟、司机2配送用户42分钟、司机3配送用户22分钟、司机4配送用户33分钟总配送时间11分钟。例题3. 软件开发场景研发任务分配‌场景‌某迭代有4个开发任务前端页面、后端接口、数据库优化、测试用例编写分配给4名研发人员每人仅负责1个任务不同人员完成各任务的预估工时单位人天如下求总开发周期最短的分配方案。研发人员前端页面后端接口数据库优化测试用例前端工程师210125后端工程师9348DBA11527测试工程师6891最优解‌前端工程师负责前端页面2天、后端工程师负责后端接口3天、DBA负责数据库优化2天、测试工程师负责测试用例1天总开发周期8天。例题4. 运维场景服务器任务调度‌场景‌集群中有4台服务器需要同时运行4个计算任务每台服务器仅运行1个任务不同服务器运行各任务的耗时单位分钟如下求总计算耗时最短的调度方案。服务器日志分析数据备份模型推理报表生成服务器ACPU型58153服务器B内存型74126服务器CGPU型121029服务器D存储型62147最优解‌服务器A运行报表生成3分钟、服务器B运行日志分析7分钟、服务器C运行模型推理2分钟、服务器D运行数据备份2分钟总计算耗时14分钟。例题5. 非标准场景人员不足的任务分配不平衡指派‌场景‌现有3名运维工程师需要完成4项运维任务服务器巡检、漏洞修复、配置升级、监控部署允许1名工程师承担2项任务其余人各承担1项各人员完成不同任务的耗时单位小时如下求总耗时最短的方案。运维人员服务器巡检漏洞修复配置升级监控部署张工2543李工3354王工4632‌转化方法‌添加1名虚拟运维人员虚拟人员完成所有任务的耗时等于对应任务的最小耗时模拟重复分配给耗时最短的人员转化为4×4标准指派问题求解。‌最优解‌张工负责服务器巡检2小时、李工负责漏洞修复3小时、王工负责配置升级3小时监控部署2小时总耗时10小时。架构设计典型应用场景微服务请求调度将用户请求分配给不同服务节点实现总处理延迟最低容器资源编排将Pod分配到集群节点实现资源利用率最高、调度成本最低多机房流量分配将区域流量分配到不同机房实现带宽成本最低、跨网延迟最小研发任务分配将开发任务分配给团队成员实现总完成时间最短、人效最高。20.2.3 最短路径最短路径是图论与组合优化领域的经典问题核心目标是在加权图中找到两个节点之间的路径使得路径上的边权总和最小边权可以对应距离、时间、成本、延迟等实际度量指标广泛应用于交通导航、网络路由、物流规划、机器人路径规划等场景。最短路径问题主要分为几何类和图论类两大方向解题思路完全不同1.几何类最短路径初中/竞赛数学场景核心思路是‌化曲为直‌将立体、折线路径转化为平面直线距离用几何定理求解‌将军饮马问题‌直线同侧两点找直线上一点使路径和最小通过作对称点转化为两点之间线段最短求解。‌立体表面爬行问题‌蚂蚁在圆柱、长方体表面爬行的最短路径将立体侧面展开为平面矩形用勾股定理计算对角线长度多展开方式时取最小值。例圆柱底面周长24cm、高5cm蚂蚁从侧面A点爬到B点展开后半周长12cm最短路径为1225213cm。‌造桥选址问题‌河两岸两点建垂直河岸的桥使总路程最短通过平移点消除固定桥长的影响转化为直线距离求解。例题1将军饮马基础题‌牧马人从A点出发到笔直的河边饮马后返回B点A、B两点在河的同一侧A到河岸垂直距离2kmB到河岸垂直距离3km两点沿河岸方向的水平距离为12km求牧马人最短的行走总路程。解法作A点关于河岸的对称点A连接AB与河岸交点即为饮马点最短路径为AB的长度由勾股定理得‌例题2长方体表面爬行题‌长方体长3cm、宽2cm、高1cm蚂蚁从下底面顶点A爬到上底面相对顶点B求蚂蚁在表面爬行的最短路径。解法将长方体相邻两个面展开为平面共3种展开方式分别计算对角线长度‌例题3‌造桥选址题‌河宽固定为100m两岸平行A、B两点分别在河的两侧沿河岸方向水平距离300m垂直河岸方向总距离400m需要建一座垂直于河岸的桥求从A到B的最短总路程。解法将A点沿垂直河岸方向向河对岸平移100m到A连接AB与对岸交点即为桥的位置最短总路程为 桥长AB长度2.图论类最短路径算法/架构设计场景核心思路是通过松弛操作逐步扩展已知最短路径根据问题场景选择对应算法算法适用场景时间复杂度核心特点Dijkstra算法单源最短路径一个起点到所有点边权非负堆优化后O(EVlog⁡V)O(EVlogV)贪心策略全局最优是导航、路由场景最常用的经典算法Bellman-Ford算法单源最短路径支持负权边可检测负权回路O(VE)O(VE)适用范围广但速度较慢适合存在负权的特殊场景Floyd算法全源最短路径任意两点间最短路径可处理负权边无负权回路O(V3)O(V3)动态规划实现代码简单适合顶点数较少V100的图A*算法起点到终点的点对点最短路径启发式优化后效率远高于Dijkstra加入启发函数引导搜索方向适合机器人路径规划、游戏寻路‌例题4单源最短路径基础题Dijkstra算法适用‌6个城市 v1~v6 之间的有向道路权值单位公里如下v1→v210v1→v63v2→v37v2→v45v4→v13v4→v34v4→v57v6→v22v6→v46v6→v51所有道路均为单向且无负权求从v1出发到其余所有城市的最短路径。求解结果v1→v63km直达v1→v54kmv1→v6→v5v1→v25kmv1→v6→v2v1→v49kmv1→v6→v4v1→v312kmv1→v6→v2→v3例题5全源最短路径题Floyd算法适用‌4个机房之间的网络延迟单位ms如下机房1到机房2延迟10ms机房1到机房4延迟30ms机房2到机房3延迟50ms机房3到机房4延迟10ms机房2到机房4无直连链路求任意两个机房之间的最短通信延迟。求解结果机房1到机房3最短延迟为60ms1→2→3机房2到机房4最短延迟为60ms2→3→4其余直连链路为最短路径。例题6负权边场景题Bellman-Ford算法适用‌4个节点的有向图中边权分别为v1→v25v2→v3-2v3→v43v1→v410求v1到v4的最短路径。求解结果最短路径为v1→v2→v3→v4总权值为5(-2)36比直达路径10更短因存在负权边无法用Dijkstra算法求解。架构设计中的典型应用‌网络路由‌OSPF等内部网关协议采用最短路径优先原则计算数据包传输的最低代价路径降低通信延迟、节约网络资源。‌交通导航‌地图导航软件基于道路权重拥堵程度、距离、限速计算两点间最短行车/步行路线是最短路径最常见的民用场景。‌物流配送‌物流系统通过最短路径算法规划配送路线降低运输成本、缩短配送时间。‌服务调度‌微服务架构中计算用户请求到服务节点的最短延迟路径优化全局响应速度。20.2.4 最小生成树最小生成树Minimum Spanning Tree, MST是‌带权连通无向图‌的极小连通子图它包含图中全部n个顶点且仅用 n−1 条边保持连通同时满足所有边的权值总和最小。它是图论中解决“最低成本连通所有节点”问题的核心模型广泛应用于网络建设、交通规划、资源调度等场景。核心性质边数固定nn个顶点的生成树恰好包含n−1n−1条边且不存在回路环。总权唯一最小生成树可能不唯一存在权值相同的可选边时但所有合法MST的总边权和一定是唯一最小值。存在前提仅当原图是连通图时存在最小生成树若原图不连通只能得到各连通分量的最小生成树组成的最小生成森林。割集性质任意将顶点划分为两个不相交集合连接两个集合的权值最小的边一定属于某一棵最小生成树——这是所有MST算法的核心理论依据。两种算法均基于贪心策略都能保证得到全局最优解适用场景各有区别1. Prim普里姆算法‌核心思想‌从顶点出发逐步扩展连通集每次选择连接「已选顶点集」和「未选顶点集」的最小权边直到所有顶点被纳入。‌执行步骤‌任选一个顶点加入已选集合其余顶点为未选集合每次从跨两个集合的边中选择权值最小的边将边连接的未选顶点加入已选集合重复直到所有顶点都被纳入已选集合。‌复杂度‌‌适用场景‌2. Kruskal克鲁斯卡尔算法‌核心思想‌从边出发将所有边按权值从小到大排序依次选择不形成回路的边加入生成树直到连通所有顶点。‌执行步骤‌初始化时每个顶点自成一个独立连通分量用并查集维护连通关系将所有边按权值从小到大排序依次遍历每条边若边连接的两个顶点属于不同连通分量则将该边加入生成树合并两个连通分量重复直到所有顶点属于同一个连通分量共选出n−1n−1条边。‌复杂度‌‌适用场景‌例题1村落网线铺设Kruskal算法求解‌7个村落记为 v1~v7 ​之间可铺设网线各村间的网线铺设成本单位万元如下要求所有村落都连通求总铺设成本最低的方案。‌求解步骤Kruskal算法‌先将所有边按权值从小到大排序依次选边保证所选边不会形成环直到选够7−16条边7个顶点的生成树共需6条边‌最终结果‌最小生成树总权值为57万元即最低网线铺设总成本为57万元。例题2机房网络布线Prim算法求解‌场景‌4个机房A、B、C、D之间的直连网线成本单位千元如下A-B2 A-C3 A-D6 B-C4 B-D5 C-D1要求所有机房连通求最低布线成本。‌求解步骤Prim算法从A点开始扩展‌‌最终结果‌最低布线总成本为6千元对应布线方案为A-B、A-C、C-D。典型应用场景‌通信网络建设‌城市间铺设光缆、基站间部署光纤在保证所有节点连通的前提下最小化总铺设成本。‌电力/管网规划‌优化输电线路、供水管道布局减少线路总长度、降低建设成本和传输损耗。‌数据聚类分析‌基于样本点间距离构建最小生成树剪去长边实现样本自动分组是无监督聚类的经典方法。‌网络路由协议‌电信网络中通过最小生成树维护最小成本转发路径避免广播风暴、降低传输延迟。‌基础设施优化‌我国科研团队曾将最小生成树算法应用于5G基站功能模块拆分使信号传输量减少36%处理延迟降低23%有效解决基站信号拥堵问题。20.2.5- 20.2.8 决策论、网络与最大流量、 集合问题、最优解问题【架构专栏】补充2 数学与经济管理 2/2https://blog.csdn.net/weixin_42081167/article/details/166849684ok, 今天就到这里吧 相关系列文章欢迎点赞、收藏提供意见​计算机系统基础知识 1分概述、计算机硬件、计算机软件操作系统 3分进程管理、存储管理、文件管理、设备管理数据库技术 3分数据库设计、关系代数、范式、事务并发、数据库安全、新技术嵌入式技术 3分嵌入式硬件、嵌入式操作系统、嵌入式软件开发计算机网络 3分超纲较多OSI七层模型、TCP/IP协议族、网络生命周期、IP地址其他计算机系统基础知识 1分计算机语言、多媒体、系统工程系统性能 1分性能指标、性能设计信息系统基础知识 3分信息系统生命周期、开发方法、五大典型系统信息安全技术基础 5分安全属性、信息安全技术、网络安全技术、安全协议软件工程 12分概述、需求工程、系统设计、运维、测试、基于构件面向对象技术 3分面向对象基础、分析设计、UML关系、图项目管理 1分进度管理、配置管理、质量管理、风险管理系统架构设计 20分架构概念、生命周期、ABSD、DSSA、架构风格、架构复用、质量属性、架构评估软件可靠性 2分可靠性建模、软件可靠性设计软件架构的演化和维护1分架构演化分类、评估、面向对象架构演化未来信息综合技术 3分信息物理系统、人工智能、边缘计算、机器人、数字李生、云计算数学与经济管理 2分最小生成树、最短路径、网络与最大流量、线性规划、决策论知识产权和标准化 2分知识产权属性、保护期限、产权人确定、侵权判定专业英语 5分完形填空大学英语3级难度自学架构专栏知识点【架构专栏】架构考试介绍【架构专栏】架构知识点【架构专栏】第1章 绪论【架构专栏】第11章 未来信息综合技术【架构专栏】第2章 计算机基础知识【架构专栏】第12章 信息系统架构设计理论与实践【架构专栏】第3章 信息系统基础知识【架构专栏】第13章 层次式架构设计理论与实践【架构专栏】第4章 信息安全技术基础知识【架构专栏】第14章 云原生架构设计理论与实践【架构专栏】第5章 软件工程基础知识【架构专栏】第15章 面向服务架构设计理论与实践【架构专栏】第6章 数据库设计基础知识【架构专栏】第16章 嵌入式系统架构设计理论与实践【架构专栏】第7章 系统架构设计基础知识【架构专栏】第17章 通信系统架构设计理论与实践【架构专栏】第8章 系统质量属性与架构评估【架构专栏】第18章 安全架构设计理论与实践【架构专栏】第9章 软件可靠性基础知识【架构专栏】第19章 大数据架构设计理论与实践【架构专栏】第10章 软件架构的演化和维护【架构专栏】补充1 知识产权和标准化【架构专栏】补充2 数学与经济管理希望有所帮助互相学习、共同进步欢迎点赞、收藏