English  |  正體中文  |  简体中文  |  Items with full text/Total items : 2737/2828
Visitors : 268696      Online Users : 2
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ir.lib.stu.edu.tw:80/ir/handle/310903100/1278

Title: 基於Branch and Bound的Approximation Scheme–以最小等待時間為例
An Approximation Scheme for MLP Base on B&B
Authors: 許釗慎
Chao Shen Hsu
Contributors: 吳邦一
資訊工程學系
Keywords: 最小等待時間問題;近似演算法
Approximation Scheme;NP-Hard;Branch and Bound method
Date: 2007
Issue Date: 2011-05-24 15:12:05 (UTC+8)
Publisher: 高雄市:[樹德科技大學資訊工程學系]
Abstract: 對於NP-hard的問題,在以往的研究中,大部分的學者都以近似演算法做為研究的目標,但我們希望在使用者隨時都能停止求解,並能輸出一個解,所以我們利用了Branch and Bound Method的特性,設計在一定時間內不斷求解之演算法,且在中止演算法時輸出一個解與其保證的近似倍率,在本論文我們用一個NP-Hard問題,最小等待時間問題作為主要解決的問題,並且使用兩個在針對最小等待時間問題所設計的Lower Bound。我們以近似倍率為考量之下使用者能依自己所需而設定演算法的目標,經由實驗的結果,在一般情況下,我們可以快速得到不錯的近似倍率的解。在最後我們也展示出在輸出的保證近似比率與實在相對於最佳解的近似比率。
For NP-Hard problems, most of the researches work for approximation algorithms. Instead, the goal of our work is to design an approximation scheme which can output a solution and its performance ratio whenever it is stopped. Our approximation scheme is based on the Branch and Bound method. In this thesis, we use the NP-Hard problem: Minimum Latency Problems, or MLP for short, as an example to show how the scheme works, in which two lower bound functions of the problem are tested. The experimental results show that, in most of the cases, we can get solutions of good approximation ratio efficiently. We also show that the actual ratios are much smaller than what it guarantee.
Appears in Collections:[資訊工程系(所) ] 博碩士論文

Files in This Item:

There are no files associated with this item.



All items in STUAIR are protected by copyright, with all rights reserved.

 


無標題文件

著作權政策宣告:

1.

本網站之數位內容為樹德科技大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,惟仍請適度,合理使用本網站之內容,以尊重著作權人之權益。商業上之利用,則請先取得著作權人之授權。
 
2. 本網站之製作,已盡力防止侵害著作權人之權益,如仍發現本網站之數位內容有侵害著作權人權益情事者,請權利人通知本校護人員(clairhsu@stu.edu.tw),維護人員將立即採取移除該數位著作等補救措施。
 
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback