20140501-大学计算机第7讲-算法-程序与计算系统之灵魂.ppt

算法与算法类问题求解;符号化,计算化;算法---计算机与软件的灵魂。“算法”(Algorithm)一词源于数学家的名字：公元825年，阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)写了著名的《波斯教科书》(Persian Textbook)，书中概括了进行四则算术运算的计算规则。 算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。;有穷性：一个算法在执行有穷步规则之后必须结束。 确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。 输入：算法有零个或多个的输入。 输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。 能行性：算法中有待执行的运算和操作必须是相当基本的(可以由机器自动完成)，并能在有限时间内完成。;哥尼斯堡七桥问题：“寻找走遍这7座 桥且只许走过每座桥一次最后又回到原出发点的路 径”“对给定的任意一个河道图与任意多座桥判定 可能不可能每座桥恰好走过一次?”。 梵天塔问题：有三根柱子，梵天将64个直 径大小不一的金盘子按照从大到小的顺序依次套放 在第一根柱子上形成一座金塔，要求每次只能移动 一个盘子，盘子只能在三根柱子上来回移动不能放 在他处，在移动过程中三根柱子上的盘子必须始终 保持大盘在下小盘在上。 其他如：背包问题，丢番图方程可 解性问题；……;TSP问题(Traveling Salesman Problem，旅行商问题)，威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出TSP问题． TSP问题：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。 TSP是最有代表性的组合优化问题之一， 在半导体制造(线路规划)、物流运输(路径规 划)等行业有着广泛的应用。;问题抽象及数学建模：将问题抽象为一个数学问题，并给出求解该数学问题的算法模型。 算法策略设计 算法的数据结构和控制结构设计：将数学模型转换为可由计算机自动计算的算法。 算法的实现：用程序设计语言编写算法实现的程序。 算法的分析：分析算法的正确性和复杂性，判断能行性！;数学建模与算法策略设计---算法思想;算法类问题求解的第一步就是要数学建模。 数学建模是用数学语言描述实际现象的过程，即建立数学模型的过程。 数学模型是对实际问题的一种数学表述，是关于部分现实世界为某种目的的一个抽象的简化的数学结构。;哥尼斯堡七桥问题被抽象成一个“图(Graph)” --由节点和边所构成的一种结构， --依据“图”，可发现该问题所蕴含的许多性质： “连通----两个节点间有路径相连接” “回路---从一个节点出发最后又回到该节点的一条路径” “可达----从一个节点出发能够到达另一个节点” “经过图中每边一次且仅一次的回路” “经过图中每个节点一次且仅一次的回路” 什么情况下有解，什么情况下无解？;TSP问题的数学模型;算法策略设计---算法思想;TSP问题的难解性：随着城市数量的上升，TSP问题的“遍历”方法计算量剧增，计算资源将难以承受。 2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。;TSP问题，有没有其他求解算法呢？ 最优解 vs. 可行解 不同的算法设计策略： 遍历、有哪些信誉好的足球投注网站算法 分治算法 贪心算法 动态规划算法 ……;贪心算法是一种算法策略，或者说问题求解的策略。基本思想“今朝有酒今朝醉”。 一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。 TSP问题的贪心算法求解思想 从某一个城市开始，每次选择一个城市，直到所有城市都被走完。 每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短。 ;基本目标: 理解算法类问题求解框架;算法思想的精确表达--算法的数据结构设计(I);算法思想的精确表达--算法的数据结构设计(I) (1)算法设计包括什么? ;数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。;变量与存储单元 ;;“变量”与 “变量类型”及其存储 ;向量或列表是有序数据的集合型变量，向量中的每一个元素都属于同一个数据类型，用一个统一的向量名和下标来唯一的确定向量中的元素。在程序设计语言中，又称为数组。 向量名通常表示该向量的起始存储地址，而向量下标表示所指向元素相对于起始存储地址的偏移位置。;矩阵或表是按行按列组织数据的集合型变量，通常是一个二维向量，可表示为如M[2,