Good point. Hadn't thought about the monotonic problem with Dijkstra. My problem is I need the costs to represent considerations other than pure distance but my ultimate outcome must be constrained by a total distance, so there's not really a good way that I can see to fold them together.
One strategy I've been planning to investigate is developing an unconstrained cumulative cost matrix for each origin point and each destination point and then sum the O + D matrices to get the total route cost for the pair at every matrix coordinate. I'm not completely sure how I can use that to identify a route within my distance constraints but I think it might be a promising option. On Tue, May 2, 2017 at 3:01 PM, Zach Pincus <zpin...@gmail.com> wrote: > I can't think of any alternatives off the top of my head. The usual > solution is to incorporate everything into your cost function, instead > of having two separate stopping criteria -- most problems lend > themselves to this pretty well. > > And actually, now that I think of it: Dijkstra's algorithm (which is > all this graph traversal is running) fails with non-monotonic cost > functions. Since the algorithm only visits a given position one time > (on the minimum cost path), a shorter but more expensive path to the > same point will not be considered, even if that is part of the path > that gives a global optimum on your "minimum cost path below a certain > length" problem. It would be a good advanced algorithms problem set > question to consider if optimal solutions to that problem will > necessarily be exponential in complexity. > > So that's why people usually try to blend their cost considerations > into a single cost for traversing each node... > > That said, you might get OK solutions from this modified algorithm, > though there will be no guarantee of global optimality. > > I can also think of one awful hack you could try to just see how well > it works. You could "store" the number of steps in the cumulative cost > by defining a custom travel_cost function. > https://github.com/scikit-image/scikit-image/blob/ > master/skimage/graph/_mcp.pyx#L885 > > Let's assume that your "actual" costs are all >> 1. Then, instead of > returning new_cost, you return new_cost + 0.001. Then goal_reached > could count the number of steps by just looking at the value of the > cumulative cost after the decimal point. > > Again, this is gross, and there are lots of cases where it won't work > or will blow up badly. But for reasonably small maximum path lengths, > it should be OK. Also, for speed you'll still need to implement this > in a cython subclass. But you can use MCP_Flexible to proof out the > implementation in slow pure python. > > > > > On Tue, May 2, 2017 at 2:43 PM, Spencer Gardner > <spencergard...@gmail.com> wrote: > > Thanks. That's extremely helpful. I think I'll be able to work out the > > subclassing. I've never worked in cython but there's a first time for > > everything. > > > > Is there some alternative solution to my problem that I've missed? I've > > scoured the documentation from various software projects (GIS and > non-GIS) > > to try to find something that implements an algorithm like this but I > > haven't come across anything. This seems odd to me, since it's a problem > I > > assume others have had to solve before. > > > > In any case, I'm sure I'll be back with more questions as I dive in. > > > > Spencer > > > > On Tue, May 2, 2017 at 2:11 PM, Zach Pincus <zpin...@gmail.com> wrote: > >> > >> > I need to implement a minimum cost path through an array of costs. The > >> > added > >> > twist is that I need to ensure the path does not exceed some maximum > >> > geometric distance (represented as a total number of traversed cells). > >> > So I > >> > need my goal_reached() method to check whether the current path has > >> > exceeded > >> > the maximum number of cells and return 1 if true (which tells MCP to > >> > stop > >> > checking neighbors). > >> > > >> > Is there a good example implementation somewhere that I can refer to > for > >> > some guidance? I've sketched out a rough outline but I'm not sure I'm > on > >> > the > >> > right track: > >> > > >> > graph = MCP(costSurfaceArray,fully_connected=False) > >> > > >> > def goal_reached(index, cumcost): > >> > '''code to check total distance''' > >> > > >> > graph.goal_reached = goal_reached > >> > >> First, note that MCP is implemented in cython, so you can't > >> monkeypatch goal-reached like you could with a pure-python class. > >> Instead you have to subclass: > >> > >> class MyMCP(MCP): > >> def goal_reached(self, index, cumcost): > >> print(index, cumcost) > >> return 0 > >> > >> m = MyMCP(costSurfaceArray) > >> > >> Second, let's figure out about casting your problem in a way that > >> goal_reached can address. Here's the documentation for goal_reached: > >> > >> """ int goal_reached(int index, float cumcost) > >> This method is called each iteration after popping an index > >> from the heap, before examining the neighbours. > >> This method can be overloaded to modify the behavior of the MCP > >> algorithm. An example might be to stop the algorithm when a > >> certain cumulative cost is reached, or when the front is a > >> certain distance away from the seed point. > >> This method should return 1 if the algorithm should not check > >> the current point's neighbours and 2 if the algorithm is now > >> done. > >> """ > >> > >> So basically, the function receives the "current" index (i.e. position > >> in the array) under consideration, along with the minimum cost to get > >> there. If the algorithm should not continue this portion of the search > >> past that index, the function needs to return 1. If the algorithm > >> should terminate wholesale, return 2. > >> > >> If all you needed to do was stop searching after you'd gotten a > >> certain euclidian distance from the starting point, you could > >> calculate that with just the index and knowledge of the starting > >> points. However, you want to find out the current path length > >> terminating in the current index. > >> > >> For this, you will need to deal with the MCP object's > >> traceback_offsets attribute, which stores the paths to each point. For > >> speed reasons, this is only available to subclasses written in cython, > >> rather than pure-python. So you'll have to write it as a cpdef > >> function in a cython subclass of MCP. > >> > >> For the implementation, you'll need to consult how MCP.traceback(self, > >> end) is implemented, and run the same procedure in goal_reached() to > >> simply count the length of the path and return 1 if the path exceeds > >> your acceptable length: > >> > >> > >> https://github.com/scikit-image/scikit-image/blob/ > master/skimage/graph/_mcp.pyx#L648 > >> > >> This won't be totally trivial, however. You'll need to understand a > >> bit of cython, and a bit about how MCP works under the hood: it > >> doesn't store indices as n-dimensional tuples like (x,y,z) coordinates > >> or whatever. Instead it stores them as 1-dimensional indices into the > >> flattened cost array. So much of the logic in the traceback() function > >> is converting those indices around. Basically you'll just need to > >> copy-paste traceback() into goal_reached() but instead of > >> un-flattening the indices to append them to a traceback list, just > >> count the number of links required to get to a starting point. > >> > >> Let me know if this helps. > >> > >> Zach > >> > >> On Tue, May 2, 2017 at 12:14 PM, Spencer Gardner > >> <spencergard...@gmail.com> wrote: > >> > The skimage.graph documentation states that the goal_reached method > can > >> > be > >> > overloaded to introduce additional constraints on finding the minimum > >> > cost > >> > path. I'm having some trouble implementing this but I can't find any > >> > useful > >> > examples to follow online. I'm hoping someone can provide some > guidance. > >> > > >> > I need to implement a minimum cost path through an array of costs. The > >> > added > >> > twist is that I need to ensure the path does not exceed some maximum > >> > geometric distance (represented as a total number of traversed cells). > >> > So I > >> > need my goal_reached() method to check whether the current path has > >> > exceeded > >> > the maximum number of cells and return 1 if true (which tells MCP to > >> > stop > >> > checking neighbors). > >> > > >> > Is there a good example implementation somewhere that I can refer to > for > >> > some guidance? I've sketched out a rough outline but I'm not sure I'm > on > >> > the > >> > right track: > >> > > >> > graph = MCP(costSurfaceArray,fully_connected=False) > >> > > >> > def goal_reached(index, cumcost): > >> > '''code to check total distance''' > >> > > >> > graph.goal_reached = goal_reached > >> > > >> > Thanks for any help! > >> > > >> > PS I posted this also on a Google Group that appears to be defunct. > >> > Apologies if that list is actually active and you got a double post > from > >> > me. > >> > > >> > > >> > _______________________________________________ > >> > scikit-image mailing list > >> > scikit-image@python.org > >> > https://mail.python.org/mailman/listinfo/scikit-image > >> > > >> _______________________________________________ > >> scikit-image mailing list > >> scikit-image@python.org > >> https://mail.python.org/mailman/listinfo/scikit-image > > > > > > > > _______________________________________________ > > scikit-image mailing list > > scikit-image@python.org > > https://mail.python.org/mailman/listinfo/scikit-image > > > _______________________________________________ > scikit-image mailing list > scikit-image@python.org > https://mail.python.org/mailman/listinfo/scikit-image >
_______________________________________________ scikit-image mailing list scikit-image@python.org https://mail.python.org/mailman/listinfo/scikit-image
