(3.215.183.251) 您好!臺灣時間:2021/04/22 09:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:吳俊達
研究生(外文):Dream Day Wu
論文名稱:取寶問題之演算法討論
論文名稱(外文):Algorithms on Tresure Searching Problem
指導教授:吳政勳吳政勳引用關係
指導教授(外文):Jesse Wu
學位類別:碩士
校院名稱:國立成功大學
系所名稱:應用數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:1994
畢業學年度:82
語文別:中文
中文關鍵詞:取寶問題計程車載客問題變形迷宮問題變形 TSPNP-完備
外文關鍵詞:Treasure Searching ProblemTexi Routing ProblemModified Maze
相關次數:
  • 被引用被引用:0
  • 點閱點閱:63
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
現實世界中, 計程車司機的載客過程可視為供需問題. 就意義上而言, 供
需問題與事物出現的機率有關, 譬如顧客出現的機率, 競爭對手之多寡,
同時, 時間的進行也是重要的考慮因素. 這樣的問題並不單純, 於是我們
先把它簡化成不考慮時間, 已知顧客去處的單向搜尋問題, 然後檢視其複
雜度, 藉此一窺當面臨真正的供需問題時可能會遭遇的時間複雜度. 不幸
地, 我們發現簡化後的載客問題其實是 NP-complete, 於是我們決定把重
點指向簡化的載客問題上面.簡化後的載客問題還不夠簡單去證明 NP-
complete, 因為``顧客能隨意指定去處''使得計程車的行跡較難追蹤, 於
是我們又將問題簡化成去掉顧客去處的取寶問題. 取寶問題指``有一個尋
寶者已經知道有某些地方埋著寶藏, 我們想問在同時考慮路途花費和寶藏
利益的情況下, 尋寶者該怎麼走才能賺到最多錢?''因為取寶問題為這些
問題單純化的原始模型, 比較易於著手, 於是我們正式以取寶問題作為本
篇論文的主題.取寶問題與 TSP (Traveling Salesperson Problem) 有點
相像,該皆描述在圖形上遊走的最佳化問題. 但 TSP 中限制了頂點只能被
經過一次, 而取寶問題則不設此限; TSP 要求每個頂點都要被經過,取寶
問題也不須如此. 在取寶問題中, 除了給定邊代價外, 還給定頂點附加利
益. 我們將證明取寶問題是 NP-complete.本篇論文中, 我們將介紹三種
演算法來解決取寶問題並說明取寶問題和 TSP 實施演算法的不同處, 另
外還要介紹另一些相關的 NP-complete 問題.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔