Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/92948
Title: Post’s Correspondence Problem之困難例子
Research on the Generator of Hard Instances
Authors: 林順喜
江陳威
CHIANG CHEN-WEI
Keywords: 波斯特對應問題
不可判定性問題
基因重整繁衍演算法
基因演算法
Post’s correspondences problem
undecidable problem
genes restructuring algorithm
genetic algorithm
Issue Date: 2008
Abstract: Post’s correspondences problem(波斯特對應問題,縮寫為PCP)的難易程度以往是由各集合中解答的長度所決定,解答的長度越長者難度越高,然而這並無法公平客觀的面對所有instances。故本論文提出一套有別於以往的困難度定義:即解題時間除以該例子所得到有解的數目。 本篇論文有兩個主要方向:其一是使用較小size與width的instance透過「PCP基因重整繁衍」之演算法,繁衍出特定不同的size與width的instances,並使用由「Solver」程式改寫而成的「Hard index solver」程式做為困難度判定的指標,重覆地篩檢,進而產生特定不同的size與width且合法有解的instance,以做為後續實驗的素材,並供後人研究參考。其二則是藉由前人所定義的困難度指標所留下較困難的200 hard instances,與本論文透過「PCP基因重整繁衍」之演算法並藉由新定義的困難度指標所找出較困難的200 hard instances做一比較,以證明本論文所定義的困難度有其較合理的意義。
The hardness of an instance of the Post’s correspondences problem (abbreviated to PCP) was defined in the past based on its solutions’ lengths. That is, the longer the lengths of the solutions are, the harder the instance becomes. But this cannot reflect the real characteristic of the hard instances. In this thesis, we present a new definition of the hardness for the PCP where the solving time divided by the number of solutions is defined as the index of the hardness of a PCP instance. This thesis is composed of two major parts. Firstly, starting from the PCP instances with smaller sizes and widths, we use a "PCP genes restructuring" algorithm to generate lots of PCP instances with larger sizes and widths. To filter those PCP instances, we rewrite the "Solver" program to be "Hard index solver". At last, some of the legal and solvable instances are remained and kept into our PCP database, which can be used in the future research. Secondly, we compare the 200 hard instances derived by previous researchers with the 200 harder instances derived from our study. Through this comparison, we are able to show that our new definition for the hardness of the PCP instance is more reasonable than previous definition.
URI: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=%22http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22GN0694080169%22.&%22.id.&
http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/92948
Other Identifiers: GN0694080169
Appears in Collections:學位論文

Files in This Item:
File Description SizeFormat 
n069408016901.pdf243.69 kBAdobe PDFView/Open
n069408016902.pdf333.37 kBAdobe PDFView/Open
n069408016903.pdf259.11 kBAdobe PDFView/Open
n069408016904.pdf281.44 kBAdobe PDFView/Open
n069408016905.pdf582.03 kBAdobe PDFView/Open
n069408016906.pdf214.84 kBAdobe PDFView/Open
n069408016907.pdf40.83 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.