patternMinor
Finding the most efficient paths to cover an area from multiple starting locations
Viewed 0 times
fromstartinglocationstheefficientpathsareamultiplefindingcover
Problem
I'm looking to design an algorithm for a problem I have, and was hoping there may be someone that could provide some insight on where to start.
In my picture above, the grid is the area they needs to be explored by the circles. Each cell is a unit of work, so currently I've got lat/lng coordinates for the exact center of each of the grid cells. The goal is to visit every cell in the grid. Circles must start in their home locations, and must end in their home locations.
In my current algorithm (SUPER simple, but it works), I'm simply taking the center coordinates of each of those grid cells, splitting them up into lists (number of lists = number of circles), then adding the home location to the beginning and end of each of those lists. As you can imagine, this leads to some very inefficient routes.
The grid areas can vary wildly, as well as the location of the "Homes", so an algorithm that simply determines the best possible route, by minimizing the total distance travelled for each circle to complete the entire task, is what I'm looking for.
I'm thinking this may be some sort of variant of Dijkstra's algorithm, where the distances between all the different center points as well as the home locations are all calculated before determining the lowest possible solution. Where my understanding kind of falls apart is Dijkstra's algorithm is shortest path from A to B, whereas this algorithm is more of a "shortest path from A to A, given that an individual circle can complete X many units of work, with the end goal of the entire grid area being completed".
With this algorithm, I'm picturing that it would take into account the return trip, since its part of the calculated distance I'm trying to minimize, so it would try to complete units of work that are on the way back home.
Any insight or guidance is greatly appreciated. Thank you.
In my picture above, the grid is the area they needs to be explored by the circles. Each cell is a unit of work, so currently I've got lat/lng coordinates for the exact center of each of the grid cells. The goal is to visit every cell in the grid. Circles must start in their home locations, and must end in their home locations.
In my current algorithm (SUPER simple, but it works), I'm simply taking the center coordinates of each of those grid cells, splitting them up into lists (number of lists = number of circles), then adding the home location to the beginning and end of each of those lists. As you can imagine, this leads to some very inefficient routes.
The grid areas can vary wildly, as well as the location of the "Homes", so an algorithm that simply determines the best possible route, by minimizing the total distance travelled for each circle to complete the entire task, is what I'm looking for.
I'm thinking this may be some sort of variant of Dijkstra's algorithm, where the distances between all the different center points as well as the home locations are all calculated before determining the lowest possible solution. Where my understanding kind of falls apart is Dijkstra's algorithm is shortest path from A to B, whereas this algorithm is more of a "shortest path from A to A, given that an individual circle can complete X many units of work, with the end goal of the entire grid area being completed".
With this algorithm, I'm picturing that it would take into account the return trip, since its part of the calculated distance I'm trying to minimize, so it would try to complete units of work that are on the way back home.
Any insight or guidance is greatly appreciated. Thank you.
Solution
If I understand your description correctly, there is no polynomial-time algorithm that solves each instance optimally. Intuitively, if you had an efficient algorithm for your problem, we could use it to find a Hamiltonian cycle (i.e., a cycle that visits each vertex exactly once) in a grid graph which is known to be NP-complete [1]. (The paper also contains hardness results for various "grids"; see whether some of the definitions actually capture your concept of a "grid").
In other words, we can reduce the problem of determining whether a grid graph has a Hamiltonian cycle to your problem where we have single circle.
You should not be discouraged too much by such a result though. It is perfectly possible you can do considerably better than your current algorithm, i.e., perhaps maybe even most of your instances are actually quite simple to solve. For instance, you could look at various metaheuristics and consider using (say) a genetic algorithm to find a good solution.
[1] Arkin, Esther M., Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. "Not being (super) thin or solid is hard: A study of grid Hamiltonicity." Computational Geometry 42, no. 6-7 (2009): 582-605.
In other words, we can reduce the problem of determining whether a grid graph has a Hamiltonian cycle to your problem where we have single circle.
You should not be discouraged too much by such a result though. It is perfectly possible you can do considerably better than your current algorithm, i.e., perhaps maybe even most of your instances are actually quite simple to solve. For instance, you could look at various metaheuristics and consider using (say) a genetic algorithm to find a good solution.
[1] Arkin, Esther M., Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. "Not being (super) thin or solid is hard: A study of grid Hamiltonicity." Computational Geometry 42, no. 6-7 (2009): 582-605.
Context
StackExchange Computer Science Q#92933, answer score: 4
Revisions (0)
No revisions yet.