Random Graph Model Generation And Application

Preference processing is an important application in the field of artificial intelligence.As a graph model describing qualitative conditional preferences among multiple attributes,the method of structure generation and reasoning of Conditional Preference Networks(CP-nets)plays an important role effect.Therefore,a random graphical model should be designed according to the structural characteristics and parameter characteristics of the graphical model.The generation algorithm designed in this acticle generates random full-structure CP-nets according to the number of vertices and degrees.The principle is to obtain the DAG code by improving the Prufer code,and realize the random generation of the graph model according to the one-to-one mapping between the DAG code and the graph structure.Then the running performance of the typical dominant query on the graph is proved the generated graph model has the randomness of the corresponding characteristics,and it is verified that the difficulty of the dominant query algorithm depends heavily on the randomness of the graph topology.Secondly,in order to improve reasoning efficiency and reduce redundancy,this acticle designs an algorithm for generating CP-nets with bounded tree width based on Dandelion coding.And use k-tree to complete the constraint of CP-nets tree width k.This acticle proposes a decoding and encoding algorithm between Dandelion coding and k-tree,so as to use the coding to generate CP-nets with a bounded tree width.Experiments show that this generation algorithm can effectively generate high-quality CP-nets with a tree width of k in linear time.Finally,use the common reasoning algorithm of CP-nets—dominant query to verify that the generated bounded tree width CP-nets not only has uniformity,but also has a fast reasoning speed.Thirdly,aimed at the problem of insufficient data storage and processing capabilities when computers face large-scale structures.This acticle uses the heuristic function of the A*algorithm to construct a scoring function,and proposes a CP-nets dominant query algorithm based on the A*algorithm.The algorithm uses the heuristic function+pruning idea to prune+search the candidate node structure,and then obtain the local optimum of the node flip in linear time to obtain the global optimum.This also provides new ideas for the structural reasoning of CP-nets with large-scale structures.Finally,using the bounded tree width k-tree constraint and the idea of A*algorithm,a heuristic dominant query N(?)o’ is performed from randomly generated bounded tree width CP-nets.Introducing the idea of quantitative preference information,designing the algorithm A*DT algorithm to study the structure reasoning problem of bounded tree width CP-nets.Under the premise of ensuring that the preference information is complete,obtain the bounded tree width CP-nets N corresponding to the original model CP-nets N0 structure,and the heuristic dominant query time is on this type of bounded tree width CP-nets and space complexity has been optimized,which also provides ideas for CP-nets multi-value attribute preference problem.The relationship between the three algorithms mentioned in this article is as follows:algorithm 1 realizes the generation of CP-nets with full structure,algorithm 2 realizes the generation of CP-nets with bounded tree width of special structure based on algorithm 1,and algorithm 3 generates heuristic dominant query algorithm for large-scale CP-nets structure.When the bounded tree width CP-nets is implemented,the algorithm time and space complexity of this algorithm are optimized.In summary,combined with the learning content of the above four parts,Get the random generation and reasoning method of CP-nets,This makes the obtained dominant query of CP-nets N more efficient and easier to implement.