MODIFIED MONTE-CARLO METHOD FOR COVERING A PARTICULAR AREA BY NON-CONVEX POLYGONS WITH SPECIAL TYPE RESTRICTIONS

Abstract

In this paper we have considered a mathematical model of covering a given area by convex polygons with variable metric characteristics, taking into account the following limitations: minimum cross-sectional area of the coverage objects; minimum area of intersection of coverage objects and addition of a given area to two-dimensional space; the placement parameters of the coverage objects must be points in the specified subregions, taking into account the priority subregions; the maximum coverage of the specified subregions of the corresponding objects; the relevance of the specified subregions to the coverage objects; the prioritization of subregions by the intersection of a given number of coverage objects; special-type restrictions that affect the metric characteristics of coverage objects.

The analysis of the general model of the set coverage indicates that the task belongs to the class of combinatorial optimization tasks, that is, in order to obtain its solution, it is necessary to search for acceptable coverage options, and the solution will be the one that provides the minimum of the objective function.

A modified Monte Carlo method is proposed in the article for a solution to the general coverage model. The developed method allows to find local solutions of the problem. To implement a modified Monte Carlo method, you must specify the number of optimization series. Then you need to build the first level of the decision tree. At the decision tree level, the points at which the local coordinate system's coordinate system originates are randomly selected. The task constraints are checked. If these constraints are not completely fulfilled, then the next level of the tree is built, in which the point selected at the previous level is no longer taken into account. Thus, the process of constructing decision tree levels and randomly selecting elements at these levels is repeated until all constraints of the problem are met. For each series, the process of building decision trees and obtaining coverage options is repeated. After performing all the optimization series from the set, the coverage option for which the value of the objective function is the lowest is selected

Keywords: special type restrictions, general model, Monte Carlo method, decision tree.