[學術]挑到一篇看似簡單卻很多疑問的Paper

 為什麼研二了還這麼緊張

挑到一篇看似簡單卻很多疑問的Paper，是OR這個領域解最佳化問題的，整個很不熟

紀錄一下找到的筆記
 

• non-deterministic polynomial，是NP

O(n^k)的複雜度能解決的問題，都稱為polynomial的問題 (能用 O(n^k) 計算量解決之問題之集合)


NP 問題的代表問題之一是 traveling salesman problem (i.e.無法用 O(n^k) 的計算量來解決)

若有N個城市，就有(N-1)! 窮舉的可能組合，當N(也就是城市數)約超過20以上時， 階乘的結果非常的大，要窮舉出所有可能性就必須花費非常多的時間。另外像購物車問題、質數問題也都是 non-deterministic algorithm

• 近似演算法

所謂「近似」，就是指結果不一定是最優的，但是也在可以承受的範圍內，而且可以比精確求解消耗更少的資源。
無法在多項式時間內精確求到最優解，然而在現實或理論研究中，這類問題都有廣泛的應用，在精確解無法得到的情況下，轉而依靠高效的近似演算法求可以接受的近似解

• Steiner tree problem 

與minimum spanning tree非常像(最小成本擴張樹的經典演算法：Prim's algorithm and Kruskal's algorithm)

Steiner tree問題：給定一個點的集合(vertices)，利用網路圖的最短路徑連接起來，其中，路徑長度是所有edge的weight總和，與最小成本擴張樹不同之處在於，在Steiner tree問題中，會有另外的中介點與邊 (vertices and edges)被加到圖中，藉以減低spanning tree的長度，這些新加入的點被用來降低total length of connection被稱做Steiner points or Steiner vertices.