貪心演算法旅行商問題
㈠ 最短哈密頓迴路！！！！！！！！！
你這個問題是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以及機械臂的位置展示一下。