0

So I have a grid-like graph. Let's say I want to go from (1,1) to (3,3). Assuming all edges are equally weighted, BFS will clearly return multiple paths (of same total cost). Is there a way to choose paths (among the shortest paths) that maximizes turns ?

So in the example (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3) and (1,1) -> (1,2) -> (2,2) -> (2,3) -> (3,3) have the same length, but the second one will be a more desired path.

I know I can generate all paths then filter the results. But I'm wondering if there's a way to do it within the search. I was thinking about changing the order of how neighbor nodes are pushed into the queue. However I can't prove that it will work.

Any help, hint or guidance is appreciated!

Dominique Fortin
  • 2,212
  • 15
  • 20
Cmeme
  • 3
  • 2
  • Please consider the code example from wiki: https://en.wikipedia.org/wiki/Breadth-first_search – FisNaN Mar 21 '18 at 03:31
  • @FisNaN Thank you for replying. I checked the page you linked. It seems to me that the only code example is just a regular BFS. It returns the "shallowest goal". I don't see how it solves my problem. I'll try to rephrase the post. Please clarify. – Cmeme Mar 21 '18 at 14:54
  • I'm wondering if there is a way to adjust the weights to account for the turns? I also like your idea of ordering of the queue idea. I don't actually think you can do this with vanilla BFS. – Brian Stinar Mar 21 '18 at 15:42
  • @BrianStinar Thank you for input! Is it possible to maintain the original total cost if we adjust the weights? The path I want still has to be the "shortest". I was hoping that there's something we can do within the BFS to achieve this. – Cmeme Mar 22 '18 at 00:58
  • a. post [mcve] with test data b. quantitatively define a turn (change of both x and y ?) – c0der Mar 22 '18 at 09:37
  • No - the costs would change for my proposal. If this were my problem, I'd enumerate all shortest paths (Floyd–Warshall?) and then re-run this using what @c0der suggested with a quantitative definition of a turn. His quantitative definition is the same as my suggestion to adjust weights to account for the turns. Once you have a concept of how a turn impacts weights, then you can use normal algorithms here. You do could do this iteratively, with slowly increasing the value you give to turns on all ties, and possibly weighing "earlier" turns more than later turns. – Brian Stinar Mar 22 '18 at 13:36

1 Answers1

0

I think that BFS isn't the right algorithm to use for pathfinding here. Vanilla BFS doesn't care about weights. You should adjust your edge weights to account for turns, and then use something like Dijkstra's algorithm to find the shortest path, or Floyd–Warshall to find multiple shortest paths.

Brian Stinar
  • 1,080
  • 1
  • 14
  • 32