Fractal Measure Of Complexity Of Quotient Space In The Chain Of Hierarchical Quotient Space

Hierarchical quotient space chain is an important research content in the field of artificial intelligence.It can be used to solve complex problem quickly with properties of different quotient space structures,and it has important theoretic values and broad applied prospects.Without considering the process of establishing a hierarchical quotient space chain,the complexity of solving the problem can be reduced by using the hierarchical quotient space chain.However,in practical problems,the process of establishing hierarchical quotient space chain of specific problems will also consume certain time and space cost,and increase corresponding complexity,which will inevitably increase the solution complexity of the whole problem.Therefore,it remains to be further discussed whether the use of the hierarchical quotient space chain method can reduce the complexity of problem and add the complexity of the preprocessing process when dealing with practical problems.In real life,to make accurate and efficient decisions,choosing a right way to deal with problems is a premise.How to measure the quotient space complexity of the hierarchical quotient space chain of a given problem is key to choosing a reasonable solution.Therefore,the study on measurement of the chain complexity of hierarchical quotient space has important and practical significance.This thesis discusses the basic theory of quotient space chain,analyses of the one-to-one relationship between the layered hierarchical chain of quotient space and the fractal iteration function system deeply,and summarizes the existing complexity measuring defects based on the complexity of the algorithm analysis which can only roughly compute complexity and can't accurately measure the whole process including preprocessing procedure.In terms of this issue,this thesis conducts in-depth analysisand research on the complexity measurement of hierarchical quotient space chain,and obtains research results as followed:Firstly,combining with fractal function iteration system,the quotient space and mathematical essential characteristics between the hierarchical quotient space chain and the function iteration system are systematically analyzed.According to this characteristic,a new measure method of hierarchical quotient space chain complexity based on fractal dimension in fractal is proposed.The results of theoretical analysis and experimental comparisons show that the new method can not only measure the complexity of problems in practical problems,but also effectively describe the complexity of quotient space of hierarchical quotient space chain,and overcome the fuzziness of measurement boundary of asymptotic complexity analysis.Secondly,the proposed method is used to measure the complexity of the hierarchical quotient space chain of the shortest path problem in context of undirected and unweighted networks.Firstly,the establishment process of hierarchical quotient space chain of undirected and unweighted networks is analyzed.Then,combined with the characteristics of specific network background,the proposed method of measuring the complexity of hierarchical quotient space chain by fractal method is applied to the complexity of hierarchical quotient space chain of this network background.Both theoretical and experimental results show that the new method can effectively measure the complexity of the hierarchical quotient space chain in practical problems.