贪心算法旅行商问题
㈠ 最短哈密顿回路！！！！！！！！！
你这个问题是NPC问题，不存在多项式时间的算法。
只有两种方法：
1，搜索：O(n!)
2，状态压缩的动态规划：O(n^2*2^n)
㈡ 算法基础
谨以此文，感谢我在这个学校最喜欢的两个老师之一——肖my老师。本文基本为老师上课说讲授内容加上一部分自己的感悟拼凑而来，写作文本的目的是为自己的算法课程留下一点点东西，站在老师肩膀上形成粗糙的框架，方便以后的复习以及深入。文笔有限，其中包含的错误还请多多包容，不吝赐教。
to do list：
时间复杂度中递归树法；动规，分治新的感悟；
点覆盖：一组点的集合，使得图中所有边都至少与该集合中一个点相连。
支配集：一组点的集合，使得图中所有的点要么属于该集合，要么与该集合相连。
最大团：在一个无向图中找出点数最多的完全图。
独立集：一组点的集合，集合中的顶点两两不相邻。（团转过来）
SAT问题：也称布尔可满足性问题。给一组变
其中Ci被称为句子。
点覆盖<->独立集<->最大团
最小割：割是一组边集。如s-t割就是如果去掉这些边，将把原图划分为两个点集，其中一个点集包含s，一个点集包含t。（两个是指不相连，而不是代表不存在边相连，如反向边）
decision problem: 是否存在。
search problem:找到一个解。
（这个还能扩展，比如decision problem在多项式时间内解决，所以他是P问题吗）
渐进符号：
注意以上三种都是紧的，对应的两个小写的符号是不紧的，即如下图所示：
概念：算法的时间复杂度是一个函数，用于定性描述算法的运行时间。注意，这个一个代表算法输入字符串长度的函数。
[注]输入字符串长度是一个比较关键的理解，比如在背包问题中，其时间复杂度为O(nW)，因为W不定，所以只能是一个伪多项式时间。
比较：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n
大致：常数<对数<幂函数<指数函数<阶乘
对于指数是n相关的进行比较，优先比较指数，再比较底数。
记住一个特例：n (logn)<n!<n n
计算：
一般来说，计算采用主方法和递归树法，其中递归树技巧性比较强，主方法其实也是递归树推导归纳而来，且主方法能得到一个比较紧的结果。
主方法：
f(n) = af(n-b)+g(n) =>O( a^(n/b) *g(n) )
P：decision problems有一个多项式算法。
NP（nondeterministic polynomial-time）：decision problems能够在多项式时间内验证。
NPC：NP完全问题，首先这个问题是NP的，其次，其他所有问题都可以多项式时间内归约到它。
NPH：如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。
因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。
一些NP问题能在多项式时间内解决，因为 P∈NP
NP难类型问题的证明：
先选好一个已知NP难的问题，然后将已知NP难问题多项式归约到要证明的问题上。先给出这个归约，然后再证明这个归约的正确性。
NPC类型问题的证明：
证明一个问题Y是NPC问题，先说明Y是NP的，然后找到一个NPC问题X，将这个问题X归约到问题Y上，即证明完成。
常见的NPC问题（重要，规约的时候有用！）：
packing problems: set-packing，独立集
覆盖问题：集合覆盖问题，顶点覆盖问题
严格满足问题(constraint satisfaction problems)：SAT，3SAT
序列问题：哈密尔顿回路，旅行商问题
划分问题：3D-matching, 3着色问题
数字问题：子集合问题（子集元素之和为t），背包问题
其他：分团问题（是否存在一个规模为k的团）
规约的概念与理解
规约：意味着对问题进行转换，例如将一个未知的问题转换成我们能够解决的问题，转换的过程可能涉及到对问题的输入输出的转换。
自归约：search problem <=p decision problem
归约：A归约到B，也就是说，我们对A套一个函数f，在f函数的作用下形成一个新的问题，对这个问题运用B的黑盒解法，能够解决问题A。
(B <=p A)一般说来，B问题如果可以归约到A问题，也就是说，一个解决A问题的算法可以被用做子函数（子程序）来解决B问题，也就是说，求解B问题不会比求解A问题更困难。因此，如果B问题是困难的，那么A问题也就是困难的，因为不存在求解A问题的高效算法。(最后一句不懂)
我简单说一下我理解的规约，以X规约到Y为准，大概分成两个方面：
注：在 三 的一些实例中细品。
概念：在对问题求解时，总是做出在当前看来是最好的选择。
贪心的证明：先假设贪心算法得到的解不是最优解，假设S1是贪心算法得到的解，而S2是所有最优解中和S1具有最多相同元素的解，然后比较S1和S2，观察S1和S2中第一个（最前面一个）不一样的元素，然后在贪心解S2中将不一样的元素换成S1中的那个元素得到另一个最优解S3，这样S3和S1比S2和S1有更多相同元素，和假设S2是与S1有最多相同元素的最优解矛盾，这样来推导S1是最优解。
我的理解：假设这个不是最优的，但是一定存在一个最优的解在某一个位置之前和我当前解结构是一样的，那么在这个位置，选最优解也可以选当前解，不影响最终答案。
[注]概念很简单，但是实际操作的时候，贪心的角度很重要，同样的贪心，方向对了，算法就是对的。
例子：
给你一系列活动，每个活动有一个起始时间和一个结束时间，要求在活动不冲突的情况下找到一种有最多活动的安排。
对于这个问题，我们有一下几种贪心的角度：
①将任务按照 开始时间 升序排列。
②将任务按照 结束时间 升序排列。
③将任务按照 任务时长 升序排列。
④对于每一个任务，都记录与其他任务冲突的数量，按照 冲突数量 的升序排列。
其中1，3，4都是不可以的。
任务结束时间的贪心证明（反证法）：
假设贪心不是最最优的，那我们在最优解中找一个与当前解有最相似的解。
由图可以知道，贪心贪的就是最早结束，所以如果不是最优，那么最优的结束时间一定晚于贪心的结束时间。
由上图就可以证明。
最大流通常与最小割相联系。
f 为任意一个流，cap为容量，对于任意的s-t割出来的点集（A，B），v( f ) <= cap(A, B)。
当流增加到与割的容量相等时候，就不可能再有增长空间了，称为最大流。
对于割的容量来说，不同的割法会有不同流量，有些割法永远不会有流达到，比如部分A = {s}, B = {V - s}，这种把源点割出来的割法。
综上，通过这种感性的认识，如果能找到一个最小的割，那么这个割就一定是最大能跑到的流（如果流能更高的话在这个割上就会超过容量，反证。）
上图为一条增广路，一条增广路即为一条s-t的路径，在路径上仍有流可以跑，其曾广的流就是该条路径上最小的剩余容量。（相当于每找一条增广路，就至少有一条边达到满流。）
直到在图中找不到增广路，此时已经达到了最大流。
找ST集合：把满流的边去掉，从S出发走到能到的点，遍历的点就是S集合；剩下的点就属于T集合。注意，如果找到了在找S集合的时候找到了T点，说明还可以继续找增广路。
[补]有一个很有趣的延伸，如多源点多终点问题。问：如果我有两个源点s1，s2，两个终点t1，t2，我想求一组流，使得s1-t1，s2-t2的流达到最大，是否可以加一个源点S，S与s1，s2相连，边流无限大；加一个终点T，T与t1，t2相连，边流无限大，然后这组ST的最大流即可。——答案是No，无法保证是s1-t1，s2-t2，有可能交错。
例子讲的感觉不是特别好，对理解感觉起不到很大作用，希望以后有新的想法后进行补充。
规约是一个重要的概念和思想。
一个图的 最大独立集 与 最小点覆盖 是不相交的两个点集，它们的并就是整个点集。
个人理解：独立集和点覆盖都是从点的角度进行划分的，如果我们从边的角度来看，①一个最小的点覆盖即为我集合中的每一个点都尽可能与更多的边相连，②同时，一条边的两个端点中，只能有一个端点在最小点覆盖中[下注]
[注]我们假设有一条边两个端点（u，v）都在点覆盖之中，首先显然u，v都不是端点，因为假设u是端点的话只需要选择v即可；
给一个集合S和一堆S的子集S1，S2，...，Sm，问是否存在存在k个子集，使它们的并集为S。
构造：
集合为点，集合中的元素为边，有相同元素的边相连。（注意如果某一元素只在一个子集中出现，应该怎么处理呢！）
规约：在构造的图中找最小的点覆盖，选中的点能覆盖所有的边即为对应集合的并集能包含所有的元素。所以就完成了集合覆盖到点覆盖的规约。
构造：每个句子构造一个三角形，把对应变量但是相反取值的点相连。
规约：3SAT的有一个特点就是，每一个句子中至少有一个为真即可，每个句子都必须是真。将相同变量相反取值相连的目的就是，在最大独立集中，比如选择x为真，则剩下所有句子中x-ba一定不会被选中，同时由独立集和构造出来三角形的性质可以知道，每一个句子，有且仅有一个会被选中（为真）。如上图，x1-ba为真，x2-ba和x3任选一个为真即可满足。
search problem <=p decision version
比如：如果能在多项式时间内找到一个哈密尔顿圈，那么就能在多项式时间内找到一个哈密尔顿圈（删边）
在此再谈P和NP：
我们知道有些问题是可以从搜索问题规约到判断问题的，也就是所该问题如果能在多项式内判断，那么久能在多项式中搜索到，那么我们只需要说，这个判断问题能在多项式时间内求解，就叫做P问题，也就是上图红字的意思；那NP问题呢，必须要给出一个解的实例，判断的是这个实例是否满足求解问题，这个才是上图中的红字。比如，我如果能在多项式时间内判断哈密尔顿圈是否（Yes/No）存在，那这个就是ploy-time algorithm，如果我给出了一系列点，能过多项式时间内判断这些点能否构成哈密尔顿圈，那这个就是poly-time certifier。
构造：把一个点拆分成三个点。
构造：（下面两个图要连在一起看）
从行的角度看，一行代表一个变量；从列的角度来看，每三列代表一个句子。两边中一边是两个点，一边是一个点，所以有k个句子的话，每一行有3k+3个节点。从哈密尔顿圈的答案转到3SAT的答案看这个圈在每一行是从左到右还是从右到左。
子集和问题：给一个集合S，问是否能在集合中选取元素，使得总和为W。
构造：如下图，按照前六行和前三列进行分割，可以分成4部分，其中1,3,4部分是固定的，即在第一部分，变量v列和 变量为v（包括变量及取反）的行对应的格子为0，其余为0；第三部分全为0；第四部分按照12依次写下来。第二部分，如果Ci句子中有变量v，则记为1，因为一个句子只有三个变量，可以简单通过第二部分每一列和为3进行判定。此时集合已经构造出来，W为111444，与上面的规约相似，可以通过3SAT的简单性质进行感性的认知。
近似的想法很简单，要解决一个问题，我们希望能够做到①求解结果是最优的 ②在多项式时间内解决 ③对于任意的实例都能够通过该算法解决。现在对于部分问题，无法完全满足以上要求，所以就牺牲了①，但是我们希望结果不是盲目的，所以就引入了近似的概念。
近似算法。比如2-近似，认为W为近似解，W 为最优解，在求最小值的情况下W<=2W ；在求最大值的情况下，W>=1/2W*
给m个机器和n个任务，每个任务有一个ti的执行时间，我们认为完成最后一个任务所需的时间为负载时间，希望能够让这个负载时间最短。
第一种：将任务依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。
证明：
引理1.最短时间安排是大于等于任务中时间最长的任务，L* >= max tj
我们在考虑放入最后一个任务前，根据我们放置的规则，该机器是耗时最短，也就是说，该机器此时的用时是低于除掉最后一个任务后的平均时长，更低于所有任务的平均时长（引理2）；再根据引理1，最后一个任务应该是小于最优解的。
补充：
在这里，我还想讨论一下这个近似算法的中等于符号，先上结论：等号不一定能够找到一个实例，但是可以构造出一种结构，通过取极限求得，我们认为这样 也算是紧的。
构造实例：有m个机器，其中m(m-1)个任务的用时为1，1个任务的用时为m。肯定有一种任务集合，可以按照以下方式进行安排，此时的贪心解为19。
此时最佳的解为10，如下图：
通过推广可以知道此时的比为（2m-1）/m，当m取极限，能够达到2倍。
第二种：将任务从大到小排序，然后依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。
引理3：如果有大于m个任务，那么L*>=2t(m-1)。证明：t(m+1)是目前最短的任务，且目前所有机器上都有任务了，所以该任务加入时最优的情况不过是加入设备的原有任务刚好和t(m+1)相等，即等号。
（2近似）在n个点中，选取k个中心点，使得这些中心点能够以半径R的圆包含所有的点，让其中最大的半径最小，如下图所示：
基础：距离需要满足的三个定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)
r(C)为C集合中所有点的最大覆盖半径。（需要求min r(C)）
算法：在点集中任选一个作为中心点，然后重复以下步骤k-1次:选取距离已选点集中最远的点，加入点集。
证明：先假设r(C )< 1/2 * r(C)以选好的点画半径为1/2 * r(C)的圆，显然可知[注]，这个圆里有且仅有一个r(C )中的点。那么根据在下图中，根据三角不等式可以得出：
[注]在每个点上r(c )一定会包含到c点，而r(C )<1/2 * r(C)，相当于大圆套小圆，所以c*一定在c的圆中。
（2近似）问题还是很好理解的，在点上加权值，要找一个点覆盖，使得权值最小。如下图左边就是一个带权的最小点覆盖。
算法： 任选一条边(i, j)加上代价，这个代价从零开始，且这个代价的最大值低于i和j节点的权值。显然，这个边权值的最大值取决于两个端点权值的最小值，我们认为当边权值与点权值相等时，对应的那个点是紧的。把所有紧的点找出来即为点覆盖。
流程：
证明：
引理：边权之和小于等于点覆盖的点权之和。这主要是由于涉及到一条边上两个点都被选（紧的）的情况，感性认知可以看上图，缩放证明如下：
w(S)是等于所选的节点的权值之和的，等于所选节点节点所对应的边权之和，可以把它放大到所有节点对应边权之和，这样因为一条边(u, v)在u上算过一次后还要在v上算一次，所以等于边权和的两倍。再由上面引理可得。
主要为了线性规划和整数规划。
（2近似）没啥好说的，只需要把方程构造出来就行了。
由于求解出来结果不一定是整数，所以我们认为某一点的值大于1/2，就选入点集。
证明：
因为xi+xj >=1,且都是正数，那必至少一个点是大于1/2的（反证，两个都小于1/2则和小于1）。
给你n个物品和一个背包，每个物品有一个价值v和一个大小w，背包的容量是W，要求让背包装下尽可能大价值。
背包的时间复杂度：O(nW)
注意其中n表示物品的个数，无论是1个还是999个，他都是多项式的，这个很好理解。但是W就不一样了，这是一个数字。我理解的是这个数字会很奇特，比如1.00001，比如99999，这些有可能看起来不大但是实际在处理的时候很难处理的数字，统一的来说，如果我们把这些数字放在电脑上，都会以二进制的方式存储起来，有些数字用十进制表示很小，但是放在二进制上面就会很大，由W导致不能在多项式时间内解决（找不到一个范围/上界来框它）。
算法： 为了处理这个问题，我们改动了dp的状态转移方程，要让这个转移方程和W无关[注]。
此时还不是多项式的，然后我们再对value进行约。[注]
[注]这两步中，我们把w改成v，并对v进行近似处理。OPT的含义变成了，在面对是否选择第i个物品时，要想让价值达到当前值，最少的weight。理由是更改后的误差是可以忍受的：对v进行近似，结果只会出现最大价值的上下误差，如果对w进行近似，则有可能出现该物品不能放入背包中，导致整个物品直接放弃的情况。
㈢ 用动态规划求旅行商问题是不是一个有效的算法为什么
实际工程中动态规划往往很难实现，但是求解能得到全局最优。 但是贪心算法虽然较易陷入局部最优，但是求解效率极高。 若是决策量前后之间影响不是很大，且较大规模问题贪心法较好。
㈣ 常见的计算机英语专业词汇
常见的计算机英语专业词汇
作为计算机相关专业学生，面试或者笔试时不可避免地会遇到与专业相关的'问题，而考核专业问题的时候，又不可避免地涉及到很多专业词汇，这就需要求职者掌握好常见的专业词汇，才能在阐述问题时得心应手，避免出现表达错误引起误解。以下是计算机专业常见相关词汇。
计算机导论 Introction to Computer Science
高等数学 Advanced Mathematics
应用创造学 Creativity Methodology
工程图学与计算机绘图 Engineering Graphics and Computer Graphics Drawings
面向对象程序设计 Object-oriented Programming
概率论与数理统计 Probability Theory and Statistics
离散数学 Discrete Mathematics
软件工程概论 Introction to Software Engineering
数据结构 Data Structures
计算机组成与结构 Computer Organization and Architecture
操作系统 Operating System
计算机网络 Computer Network
算法设计与分析 Algorithm Design and Analysis
软件工程经济学 Software Engineering Economics
Java技术 Java Technology
UML建模 UML Modeling (Unified Modeling Language Modeling)
数据库系统概论 Introction to Database Systems
编译原理 Principle of Compiler
软件体系结构 Software Architecture
程序分析 Program Analysis
软件过程与项目管理 Software Process and Project Management
系统分析与设计 System Analysis and Design
程序测试 Program Testing
模式识别 Pattern Recognition
嵌入式程序设计 Embedded Programming
人机交互技术 Human-computer Interaction Technology
云计算 Cloud Computing
计算机与网络安全 Computer and Network Security
计算机图形学 Computer Graphics
数据挖掘技术 Data Mining Technology
分布对象技术 Distributed Object Technology
网络多媒体 Internet Multimedia
网络程序设计 Network Programming
.NET程序设计 . NET Programming Design
协议工程 Protocol Engineering
5.4.2 操作系统相关术语
虚拟机 Virtual Machine
访问控制列表 Access Control List
线程 Thread
多线程 Multithreading
进程 Process
守护进程 Daemon
进程间通信 IPC (Interprocess Communication)
死锁 Deadlock
银行家算法 Banker’s algorithm
内存管理 Memory management
虚拟地址 Virtual address
物理地址 Physical address
引导盘 Boot Disk
页面失效 Page Fault
后台进程/前台进程 Background Process /Foreground Process
文件传送协议 FTP (File Transfer Protocol)
图形用户界面 GUI (Graphical User Interface)
权限 Permission
移植 Port/Ported/Porting
可移植系统接口 Portable Operating System Interface
分时 Time-sharing
工作区 Workspace
工作目录 Working Directory
窗口管理器 Window Manager
封装器 Wrapper
5.4.3 算法相关术语
字典 Dictionaries
堆 Heap
优先级队列 Priority queue
矩阵乘法 Matrix multiplication
贪心算法 Greedy algorithm
上界/下界 Upper bound / Lower bound
最好情况/最坏情况/平均情况 Best case /Worst Case/ Average case
插入排序 Insertion sort
合并排序 Merge sort
堆排序 Heap sort
快速排序 Quick sort
动态规划 DP (Dynamic Programming)
背包问题 Knapsack problem
霍夫曼编码 Huffman Coding
迪杰斯特拉算法 Dijkstra’s algorithm
贝尔曼-福德算法 Bellman-Ford algorithm
弗洛伊德算法 Floyd-Warshall algorithm
回溯 Back-Tracking
N皇后问题 N-Queen problem
渐进增长 Asymptotic growth(包含O-notationΩ-notation Θ-notation)
线性规划 Linear programming
随机数生成 Random number generation
图的生成 Generating graphs
图论-多项式算法 Graph Problems – polynomial algorithm
连通分支 Connected components
最小生成树 Minimum Spanning Tree
最短路径 Shortest path
NP问题 Non-Deterministic Polynomial problem
旅行商问题 Traveling salesman problem
同构 Graph isomorphism
压缩 Text compression
最长公共子串 Longest Common Substring
最短公共父串 Shortest Common Superstring
收敛速度 Rate of convergence
5.4.4 数据结构相关术语
集合 Set Data Structures
线性方程组 Linear Equations
数据抽象 Data abstraction
数据元素 Data element
数据对象 Data object
数据类型 Data type
逻辑结构 Logical structure
物理结构 Physical structure
线性结构/非线性结构 Linear structure / Nonlinear structure
线性表 Linear list
栈 Stack
队列 Queue
串 String
图 Graph
插入 Insertion
删除 Deletion
前趋 Predecessor
后继 Successor
直接前趋 Immediate predecessor
直接后继 Immediate successor
双端列表 Double-ended queue
循环队列 Circular queue
指针 Pointer
先进先出表(队列) First-in first-out list
后进先出表(队列) Last-in first-out list
栈底/栈顶 Bottom /Top
压入/弹出 Push/ Pop
队头/队尾 Front/ Rear
上溢/下溢 Overflow/ Underflow
数组 Array
矩阵 Matrix
多维数组 Multi-dimensional array
以行为主/以列为主的顺序分配 Row major order / Column major order
三角矩阵 Triangular matrix
对称矩阵 Symmetric matrix
稀疏矩阵 Sparse matrix
转置矩阵 Transposed matrix
链表 Linked list
线性链表 Linear linked list
单链表 Single linked list
多重链表 Multilinked list
循环链表 Circular linked list
双向链表 Doubly linked list
十字链表 Orthogonal list
广义表 Generalized list
指针域 Pointer field
头结点 Head node
头指针/尾指针 Head pointer/ Tail pointer
空白串 Blank string
空串(零串)Null string
子串 Substring
树 Tree
子树 Subtree
森林 Forest
根 Root
叶子 Leaf
深度 Depth
双亲/孩子/兄弟/祖先/子孙 Parents/ Children/ Brother/ Ancestor/ Descendant
二叉树 Binary tree
平衡二叉树 Balanced binary tree
满二叉树 Full binary tree
完全二叉树 Complete binary tree
遍历二叉树 Traversing binary tree
二叉排序树 Binary sort tree
二叉查找树 Binary search tree
线索二叉树 Threaded binary tree
哈夫曼树 Huffman tree
有序树/无序树 Ordered tree / Unordered tree
判定树 Decision tree
数字查找树 Digital search tree
树的遍历 Traversal of tree
先序遍历 Preorder traversal
中序遍历 Inorder traversal
后序遍历 Postorder traversal
子图 Subgraph
有向图/无向图 Digraph(directed graph)/Undigraph(undirected graph)
完全图 Complete graph
连通图 Connected graph
非连通图 Unconnected graph
强连通图 Strongly connected graph
弱连通图 Weakly connected graph
有向无环图 Directed acyclic graph
重连通图 Biconnected graph
二部图 Bipartite graph
边 Edge
顶点 Vertex
连接点 Articulation point
初始结点 Initial node
终端结点 Terminal node
相邻边 Adjacent edge
相邻顶点 Adjacent vertex
关联边 Incident edge
入度/出度 In-degree/ Out-degree
有序对/无序对 Ordered pair/ Unordered pair
简单路径 Simple path
简单回路 Simple cycle
连通分量 Connected component
邻接矩阵 Adjacency matrix
邻接表 Adjacency list
邻接多重表 Adjacency multi-list
遍历图 Traversing graph
生成树 Spanning tree
拓扑排序 Topological sort
偏序 Partial order
AOV网 Activity On Vertex network
AOE网 Activity On Edge network
关键路径 Critical path
线性查找(顺序查找) Linear search (Sequential search)
二分查找 Binary search
分块查找 Block search
散列查找 Hash search
平均查找长度 Average search length
散列表 Hash table
散列函数 Hash function
直接寻址法 Immediately allocating method
数字分析法 Digital analysis method
平方取中法 Mid-square method
随机数法 Random number method
内部排序 Internal sort
外部排序 External sort
选择排序 Selection sort
基数排序 Radix sort
平衡归并排序 Balance merging sort
二路平衡归并排序 Balance two-way merging sort
多步归并排序 Ploy phase merging sort
置换选择排序 Replacement selection sort
索引文件 Indexed file
索引顺序文件 Indexed sequential file
索引非顺序文件 Indexed non-sequential file
多重链表文件 Multi-list file
倒排文件 Inverted file
5.4.5 计算机网络相关术语
端口 Port
服务器 Server
客户端 Client
服务访问点 SAP (Service Access Point)
开放系统互联 OSI (Open System Interconnection)
物理层 Physical layer
数据链路层 Data link layer
网络层 Network layer
运输层 Transport layer
会话层 Session layer
表示层 Presentation layer
应用层 Application layer
TCP/IP协议 TCP / IP protocol
信道容量 Channel capacity
香农 Shannon
奈奎斯特 Nyquist
双绞线 UTP (Unshielded Twisted Paired)
同轴电缆 Coaxial cable
光纤 Optical fiber
不归零码 NRZ (Non Return to Zero)
曼彻斯特编码 Manchester coding
调制 Molation
脉码调制 PCM (Pulse Code Molation)
增量调制 DM (Delta Molation)
同步传输/异步传输 Synchronous transmission / ATM (Asynchronous transmission)
循环冗余校验 CRC (Cyclic Rendancy Check)
流量控制 Flow control
滑动窗口 Sliding window
差错控制 Error control
帧结构 Frame structure
复用 Reuse
非对称数字用户线路 ADSL (Asymmetric digital subscriber line)
电路交换和分组交换 Circuit switching and packet switching
频分多路复用 Frequency division multiplexing
信令 Signaling
数据报 Datagram
虚电路 Virtual circuit
帧中继 Frame relay
信元 Ceil
拥塞 Congestion
反压 Back pressure
令牌桶 Token bucket
环形/总线形/树形和星形结构 Ring/ bus/ tree and star structure
局域网 LAN (local area network)
集线器 Hub
交换机 Switch
路由器 Router
网桥 Network bridge
以太网监听算法 Ethernet listener algorithm
子网掩码 Subnet mask
三次握手 Three-way handshake
地址解析协议 APP (Address resolution protocol)
瘦客户机 Thin client
网际控制报文协议 ICMP (Internet Control Message Protocol)
因特网群组管理协议 IGMP (Internet Group Management Protocol)
拒绝服务 Denial of service
边界网关 Border gateway
域名系统 DNS (Domain Name System)
数据链路控制 DLC (Data Link Control)
互联网电子邮件协议标准 POP (Post Office Protocol)
远程控制 Remote control
简单邮件传送协议 SMTP (Simple Mail Transport Protocol)
;㈤ tsp贪心算法旅行商问题怎么判断是否到过某个城市
用vis[]数组标记。。。
㈥ 假设哈密顿问题是NPC,证明:TSP（旅行商问题）属于NP-hard问题（现代优化计算方法 邢文旬主编 P50第11题）
首先HC是一个npc问题且是一个搜索问题，假设使用贪心策略的算法A（·）可解HC得到一条哈密顿回路。
再利用无向图G构造tsp的图G'，图G中存在的边权值设为1，图G中不存在的边权值设为X（X>1的整数）。
这样得到的一个TSP问题可使用算法A（·）来解。
图灵规约条件：（1）问题1，问题2都是搜索问题；
（2）求解问题1的算法A（·）可求解问题2；
（3）算法A（问题1）时间复杂度是多项式时间，则算法A(问题2)也是多项式时间；
所以HC可以图灵规约到这样一个TSP问题实例。
又因为HC是NPC类问题，可以图灵规约到TSP，所以TSP是NP-hard问题
㈦ 1.简述一下：两军问题及其引申的含义。2.生产者与消费者问题，反映了计算机学科的说没问题
5 贪心算法的核心思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解
6 程序调用自身的编程技巧称为递归,是函数自己调用自己。
迭代:利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B。
7 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”
哎，太多了。写不完了。。。。
尽量帮你一点吧
㈧ Python贪心算法
所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优加以考虑，它所做出的仅仅是在某种意义上的局部最优解。下面让我们来看一个经典的例题。假设超市的收银柜中有1分、2分、5分、1角、2角、5角、1元的硬币。
顾客结账如果需要找零钱时，收银员希望将最少的硬币数找出给顾客，那么，给定需要找的零钱数目，如何求得最少的硬币数呢？这个找零钱的基本思路：每次都选择面值不超过需要找给顾客的钱最大面值的硬币。
我们可以从面值最大的硬币开始，然后依次递减（图1）。
首先定义列表d存储已有币值。并且定义d_num存储每种币值的数量。通过循环遍历的方法计算出收银员拥有钱的总金额并保存在变量S中，要找的零钱变量为sum。当找零的金_比收银员的总金额多时，无法进行找零，提示报错。要想用的钱币数量最少，我们从面值最大的币值开始遍历。这里也就是我们贪心算法的核心步骤。计算出每种硬币所需要的数量，不断地更新硬币个数与硬币面值，最终获得一个符合要求的组合（图2）。
贪心算法在对问题求解时，不是对所有问题都能得到整体最优解，也不是从整体上去考虑，做出的只是在某种意义上的局部最优解。从面值最大的硬币开始依次递减，寻找可用的方法。一般贪心算法并不能保证是最佳的解决方法，这是因为：总是从局部出发没有从整体考虑，只能确定某些问题是有解的，优点是算法简单。常用来解决求最大值或最小值的问题。来源：电脑报
㈨ 高分求修改或者化简一个matlab code,最好是熟悉英文的
1、首先，你上传的文件不全，至少缺Sample_Data3.xls。至于还有没有其他问题现在还不好说。
2、你只是泛泛地说“修改或者化简”，有什么具体要求？比如说，加一个多余的空格也算是修改？
==================================================
上面的内容回答于2014-02-04 10:20，经楼主补充后简单说明如下：
我看了一下，这个问题可以算是一类特殊的旅行商问题（TSP）。题目并未要求得到最优解，只要求满意解即可。现有代码的思路是，总寻找最近的bolt然后送到同类型最近的hole，应该属于贪心算法（ Greedy algorithm），总体上是可行的（虽然得到的解未必最优）。
楼主要求修改代码，那么修改的标准是什么？
改动可大可小，改动大的话，可以重新设计路径规划算法（那样工作量会大很多），例如采用穷举法得到最优解（需枚举6!*3!*3!=25920种可能，规模不算大，可以接受）；而改动小的话，可以只对现有代码进行微调（例如修正小BUG，改变输出信息的方式）。请把要求明确一些。
另外，如果有补充说明或存在疑问，建议楼主采用追问的方式。
顺便上一幅图，把初始时刻bolt、hole以及机械臂的位置展示一下。