標題: | 使用循序式演算法尋找隱藏圖 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 |
顯示於類別: | 畢業論文 |