改良式廣度優先網路爬蟲演算法之組合分析

科展類別
臺灣國際科展作品
屆次
2020年
科別
數學
得獎情形
一等獎
學校名稱
臺北市立大直高級中學
指導老師
劉繕榜;胡裕仁
作者
陳品劭
關鍵字
k-錯排、遍歷、網路爬蟲
備註
青少年科學獎;出國正選代表

摘要或動機

本研究旨在探討分散式網路爬蟲瀏覽時間及覆蓋率之最佳化問題原理。藉由相異物排列所形成的循環組關係式進行一系列的探討。在n個相異元素的簡單排列中,不存在任意元素個數為k (k≤n)的子集對應到自己本身所成集合,我們稱此型態的排列方式為k-錯排。換言之,假如n個相異元素進行簡單排列,排列後每個元素都不在原來的位置上,此時這樣的排列稱為一般的錯排列,也就是1-錯排。本研究從分散網路爬蟲搜尋網址中進行相關發想,發現它的本質是遍歷完所有的頂點且沒有重複經過,即所謂「哈密頓路徑(Hamiltonian path)問題」中一筆畫的NP-hard問題,即圖遍歷問題的一種。因此本研究由k-錯排遞迴之性質來探討分散式網路爬蟲最佳化問題。最後透過電腦模擬及組合數學分析推導,本研究將提出改善以k-錯排應用至分散網路爬蟲的最佳化方式。


「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
010034.pdf 2 MB Adobe Reader(Pdf)檔案