Research On Developing Algorithms For Solving Circuit Problems

Automatic solver is an important research problem in the field of intelligent education.It aims at developing intelligent algorithms to automatically understand and solve problems stated by both texts and diagrams.This dissertation starts from a basic solving task in the field of automatic solver,and explores the intelligent solving method with high accuracy and expansibility.At present,the published solving methods include traditional frame-based method and semantic-based method.These methods not only need to set a large number of templates to understand the complex and changeable problem text,but also lack effective mining of hidden information which result in the poor accuracy of solving problems.Several deep learning based methods are developed for automatic solver,but the effective methods are less.Due to the fact that automatic solver has many tasks,it is hard to develop an unified deep learning framework to complete integrated learning of text understanding,diagram understanding,relation reasoning and automatic solving.Meanwhile,existing deep learning methods cannot generate readable solutions at present.This dissertation starts with the research status of automatic solver,and develops algorithms for solving circuit problems.This dissertation conducts research work in four aspects:the method of problem text understanding,the method of circuit diagram understanding,the method of automatic solving,and a system for solving circuit problems.In order to possess the intelligent solving ability for circuit problems,automatic solver must understand problem text.Since circuit problems often have complex textual description in natural language,traditional semantic understanding based methods,which need a large number of templates,are unable to cover the diversity of language expression in text understanding.The results of text understanding are usually presented in the form of parse trees,which limit the further reasoning and readable generating.A few circuit theorems are implicitly expressed in the problem text,which are essential for solving circuit problems,but existing methods lack of mining these implicit information.Hence,this dissertation models the text understanding as a problem of relation extraction,and proposes an automatic text understanding method,which can extract both explicit relations and implicit relations.This method builds a syntax-semantics model pool and proposes an algorithm to extract the explicit relations from problem text using the model pool.The syntax-semantics model uses the part of speech patterns to represent the complex textual description in natural language,and combines keyword structure and syntax patterns to extract relations.Considering that a circuit theorem is often directly related to the circuit element and the circuit element with multiple names has the same unit representation,so it builds an unit-theorem model pool and proposes an algorithm to extract the implicit theorem relations from problem text using the model pool.Compared with traditional methods,our method not only reduces the number of models but also improves the efficiency of text understandingSince diagrams contain abundant information for solving problems,the diagram understanding is an important part of automatic solver.The existing methods mainly focus on the understanding of geometric diagrams while the understanding of circuit diagrams are less.The former mainly analyzes vertices,curves and geometric structure,and the results are often used for the proof of geometric theorems.The latter analyzes the directional circuit attributes according to the circuit structure,and the results are often used to solve circuit problems.It is difficult to understand circuit diagrams directly,so this dissertation models the diagram understanding as a problem of relation extraction,and proposes a method for extracting relations from circuit diagrams.The method uses a topological contraction algorithm for extracting relations from serial and parallel circuits.This algorithm decomposes a circuit diagram and forms an equivalent circuit by topology contraction,then extracts relations in the process As the topological contraction algorithm fails to extract relations from bridge circuits,the mesh search algorithm is proposed to solve this problem.When we combine these two algorithms for circuit diagram understanding,it effectively improves the efficiency of circuit diagram understanding and expends the scope of problem understanding.Automatic solving is another important research problem in automatic solver.This dissertation proposes an automatic solving method for circuit problems,which can solve both text problems and diagram-text problems.This method is motivated by lacking of automatic solving methods for multimodal problems.The method models the problem solving as a problem of relation reasoning according to the latest equivalence conversion principle,and proposes an automatic solving algorithm based on relation reasoning.With the proposed problem understanding methods,circuit problems could be solved.Furthermore,a system for solving circuit problems is developed.The system is used to verify the effective of circuit problem solving and provides intelligent tutoring services.The main contributions of this dissertation are as follows(1)It proposes an automatic text understanding method,which can extract both explicit relations and implicit relations.This method is implemented by explicit relation extraction algorithm based on syntax-semantics model and implicit relation extraction algorithm based on unit-theorem model.Compared with the traditional methods,this method not only reduces the number of models but also significantly improves the performance of text understanding(2)It proposes an automatic circuit diangram understanding method,which is implemented by topological contraction algorithm based on relation extraction and mesh search algorithm based on relation extraction.This method improves the efficiency of circuit diagram understanding and expends the scope of problem understanding.(3)Aiming at lacking of automatic solving methods for multimodal problems,it proposes an automatic solving method for circuit problems,which can solve both text problems and diagram-text problems.In solving circuit problems,this method greatly improves system performance.