標題: 使用循序式演算法尋找隱藏圖
Learning a Hidden Graph with Adaptive Algorithm
作者: 施智懷
Chie-Huai Shih
傅恆霖
Hung-Lin Fu
應用數學系所
關鍵字: 隱藏圖;hidden graph
公開日期: 2007
摘要: 我們考慮如何只使用邊偵測問題(edge-detecting query)的情況下去尋找隱藏圖,邊偵測問題可以回答任何點集合內是否包含至少一條邊。Grebinski以及kucherow[5]提供一個確定性演算法去尋找隱藏的漢米爾頓圈(Hamiltonian cycle),使用最多Ο(nlog n)個問題;Beigel等人[4]提出一個確定性演算法去解決配對圖(bipartite),使用八個平行的問題群,總共Ο(nlog n)個問題,尋找隱藏的漢米爾頓圈或是配對圖可以應用到基因排序計劃。Angluin以及陳[2] 針對一般的隱藏圖使用最多12m(log n)個問題。在這個論文中,我們提供一個循序式演算法解決一般的隱藏圖,當此圖點數為n、邊數為m時,最多花費(2log n + 9)m個問題。
We consider the problem of learning a hidden graph using edge-detecting queries in a model where the only allowed operation is to query whether a set of vertices induces an edge of the hidden graph or not. Grebinski and Kucherov [5] give a deterministic adaptive algorithm for learning Hamiltonian cycles using Ο(log n) queries. Beigel et al.[4] describe an 8-round deterministic algorithm for learning matchings using Ο(log n) queries, which has direct application in genome sequencing projects. Angluin and Chen [2] use at most 12m(log n) queries in their algorithm for learning a general graph. In this thesis we present an adaptive algorithm that learns a general graph with n􀝊 vertices and m edges using at most (2log n + 9)m queries.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009522506
http://hdl.handle.net/11536/38867
顯示於類別:畢業論文


文件中的檔案:

  1. 250601.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。