Method of Achieving the Goal on a Graph Model with Two Quality Criteria
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 deter...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Educational institution «Belarusian State University of Informatics and Radioelectronics»
2023-08-01
|
| Series: | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| Subjects: | |
| Online Access: | https://doklady.bsuir.by/jour/article/view/3686 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849772767093719040 |
|---|---|
| author | S. V. Chebakov L. V. Serebryanaya |
| author_facet | S. V. Chebakov L. V. Serebryanaya |
| author_sort | S. V. Chebakov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c069f3c907c3440ea38f2d8903cd3a14 |
| institution | DOAJ |
| issn | 1729-7648 |
| language | Russian |
| publishDate | 2023-08-01 |
| publisher | Educational institution «Belarusian State University of Informatics and Radioelectronics» |
| record_format | Article |
| series | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| spelling | doaj-art-c069f3c907c3440ea38f2d8903cd3a142025-08-20T03:02:14ZrusEducational institution «Belarusian State University of Informatics and Radioelectronics»Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki1729-76482023-08-01214849210.35596/1729-7648-2023-21-4-84-921925Method of Achieving the Goal on a Graph Model with Two Quality CriteriaS. V. Chebakov0L. V. Serebryanaya1Joint Institute for Informatics Problems of the National Academy of Sciences of BelarusBIP – University of Law and Social-Information Technologies; Belarusian State University of Informatics and RadioelectronicsThe 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.https://doklady.bsuir.by/jour/article/view/3686graph modeloptimal pathpareto setvertex statesearch algorithm |
| spellingShingle | S. V. Chebakov L. V. Serebryanaya Method of Achieving the Goal on a Graph Model with Two Quality Criteria Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki graph model optimal path pareto set vertex state search algorithm |
| title | Method of Achieving the Goal on a Graph Model with Two Quality Criteria |
| title_full | Method of Achieving the Goal on a Graph Model with Two Quality Criteria |
| title_fullStr | Method of Achieving the Goal on a Graph Model with Two Quality Criteria |
| title_full_unstemmed | Method of Achieving the Goal on a Graph Model with Two Quality Criteria |
| title_short | Method of Achieving the Goal on a Graph Model with Two Quality Criteria |
| title_sort | method of achieving the goal on a graph model with two quality criteria |
| topic | graph model optimal path pareto set vertex state search algorithm |
| url | https://doklady.bsuir.by/jour/article/view/3686 |
| work_keys_str_mv | AT svchebakov methodofachievingthegoalonagraphmodelwithtwoqualitycriteria AT lvserebryanaya methodofachievingthegoalonagraphmodelwithtwoqualitycriteria |