Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397
Issue N7 2016 year
The increase in the volumes and complexity of processed information makes the use of artificial intelligence systems more and more actual. In such systems, one of the most widespread knowledge representation models is the production model and search algorithms are based on the inference engine. In practice, obtaining information about the subject area status is time-consuming operation for many problems. The examples are the requests to the DBMS, the analysis of medical data or other complex sequences of calculations can be those. Often in such problems, the search for solution (or set of possible solutions) is performed in the absence of part of information about the subject area status. This circumstance requires optimal use of limited resources. There are tasks of control of complex objects with random processes (risk management, socio-economic systems), in which the control process is based on fuzzy knowledge representation model. For them, the result of the controlling influence can be predicted only with some probability. In addition, process of obtaining information that is necessary for making decision about the control action can be time-consuming operation. In such situations it is necessary to maintain or to bring the system to the predetermined state, spending as little as possible resources for time-consuming operations of obtaining the necessary information, taking into account at the same time the fuzziness of the relationship between knowledge. The complexity of the operations of data acquisition necessary for decision-making, leads to the problem of minimizing the number of requests for information about the subject area status during inference. This problem is NP-hard. To achieve global minimization there is the general method of LP-inference with exponential computational complexity relative to the number of atomic facts in the knowledge base. However, some of its heuristic modifications have polynomial complexity. The goal of the provided research is development of the approximating method to better minimize the number of requests performed in the inference. Earlier, the structural properties of partition of the binary relation were considered, based on which it is possible to select for the analysis such subset of production, that most significantly changes the rate of relevancy. This paper presents the method for calculating the value of the exact number of layers without cycles based on capacities of quotient set equivalence classes that builds as the partition of binary relations by unique right parts. In addition, this paper considers questions of the algorithmic implementation of components that are necessary to calculate the approximate value of the number of layers without cycles. The presented approach can be applied to accelerate the reverse inference in production type systems of artificial intelligence. It can be extended also to more complex logical systems in computer science.