旅行商問題（Traveling Salesman Problem, TSP）
這個問題字面上的理解是：有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的具有最短路程的環路。
TSP的歷史很久，最早的描述是1759年尤拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線性規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
2、中國郵遞員問題（Chinese Postman Problem CPP）
同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發，到所轄街道投遞郵件，最後返回郵局，如果他必須走遍所轄的每條街道至少一次，那麼他應如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題， 因為是中國學者管梅古谷教授於1962年提出的這個問題並且給出了一個解法。
3、“一筆畫”問題（Drawing by one line）
還有一個用圖論語言的描述方式：平面上有n個點，用最短的線將全部的點連起來。稱為“一筆畫”問題。
4、配送路線問題（Route of Distribution）
TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。
TSP問題最簡單的求解方法是列舉法。它的解是多維的、多區域性極值的、趨於無窮大的複雜解的空間，搜尋空間是n個點的所有排列的集合，大小為（n-1）！。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。
旅行商問題（Traveling Salesman Problem, TSP）
這個問題字面上的理解是：有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的具有最短路程的環路。
TSP的歷史很久，最早的描述是1759年尤拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線性規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
2、中國郵遞員問題（Chinese Postman Problem CPP）
同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發，到所轄街道投遞郵件，最後返回郵局，如果他必須走遍所轄的每條街道至少一次，那麼他應如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題， 因為是中國學者管梅古谷教授於1962年提出的這個問題並且給出了一個解法。
3、“一筆畫”問題（Drawing by one line）
還有一個用圖論語言的描述方式：平面上有n個點，用最短的線將全部的點連起來。稱為“一筆畫”問題。
4、配送路線問題（Route of Distribution）
TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。
TSP問題最簡單的求解方法是列舉法。它的解是多維的、多區域性極值的、趨於無窮大的複雜解的空間，搜尋空間是n個點的所有排列的集合，大小為（n-1）！。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。