The telecommunications company is currently in the process of developing an optimized layout for a 7G network. The city is conceptualized as a grid, with certain blocks inaccessible for tower placement, while others are suitable. The objective is to achieve the highest possible coverage with the fewest number of towers.
It is required to develop a method of placing the smallest number of towers with a certain range so that all free blocks are within the range of at least one tower in randomly generated city for its full network coverage. It is necessary to take into account that it is impossible to place towers on blocks with obstacles.
Red node - 7G-network tower
Green node - possible (free) location of the facility
Empty cell - obstacle block (object placement is forbidden, not necessarily communication spreading)
Edges - possible connections between city squares
The problem is to develop an algorithm to find the most reliable path between two towers in a data transmission network. The reliability of a path is determined by the number of hops between towers: a path with fewer hops is considered more reliable.
