算法类问题求解过程(例:TSP算法)

算法类问题 唯一的个算法,但是可以解决的一系列单个问题
TSP问题 旅行商问题(经过所有城市的最短路径问题)
数学建模 用数学语言描述实际现象的过程
问题的解决过程
数学建模
算法设计与分析
数据结构设计+算法过程设计(算法正确性+算法复杂性)
程序设计
问题求解
  • 算法是程序的灵魂>>是否能写算法==是否会编程
  • TSP=traveling Salesman Problem
  • TSP(旅行商问题的难解性源于,阶层问题的组合爆炸)
  • TSP问题难解性的解决方法:较优解替代最优解
  • TSP问题解决较优解:遍历算法/分治算法/贪心算法/动态规划算法…

数学建模(离散数学)

算法的数据结构

数据结构 逻辑结构+存储结构+操作
变量名 存储单元的地址
变量值 存储单元的内容
指针 反应数据元素间的逻辑关系

算法的控制结构/算法的设计过程

顺序结构
分支结构 >>例:else-if
循环结构
程序流程图
矩形>>执行的语句
菱形>>判断
圆形框>>程序开始或结束
箭头线>>程序走向

流程图例:

算法的控制结构设计过程
1:步骤描述法(其中某个步骤还能细分,例:步骤5>>5.1+5.2…)
2:将思想策略转化为流程图

算法程序的执行过程

程序执行过程如下!
编译源程序
编译
连接(连接公用函数库与目标程序再转化为机器指令)
执行

算法分析与计算复杂性

算法分析 数学方法证明+仿真分析证明(实例测试)
算法复杂性 时间复杂性+空间复杂性
时间复杂性T(n) 一个问题规模为n,解这一问题所需时间函数为T(n)>>T(n)的同阶表示为O(n)
  • O(n) >> O=order=量级
  • T(n)与O(n)都是时间复杂性
P类问题 问题复杂度为多项式>>>>
NPC类问题 只能带入验证的难解性问题>>>