Method of Achieving the Goal on a Graph Model with Two Quality Criteria

Abstract

The features of the construction and application of graph models for solving applied problems are considered. A graph model with two quality criteria is proposed, on which the search for optimal paths between given graph vertices is performed. Each edge of the graph has a weighting factor that determines the number of time unitsrequired to pass this edge. Each vertex can be in one of two states: “open” or “locked”. Initially, all vertices are open, but their states may change in the process of problem solving. The search for a solution is limited by a given time. If during the movement along the chosen route the graph vertices become blocked, it is necessary to look for alternative ways to achieve the goal. A method for constructing a Pareto set from which admissible paths are selected is proposed. The notion of an admissible path on a graph is defined. A procedure for choosing a path from the Pareto set has been developed. Upon completion of the choice, the path is considered optimal for follo wing it from the initial vertex to the target. Situations that can occur in the process of choosing a path and passing along it are presented. Based on the selection procedure, an algorithm for finding optimal paths bet ween given vertices on a graph model has been developed.