[Jprogramming] A practical problem: minimum distance with penalties

[Henry Rich]

No, the weights are fixed.

I am implementing essentially the A* algorithm:

https://en.wikipedia.org/wiki/A*_search_algorithm

The code is for dissect: given a number of blocks and a set of 
(source,destination) pairs, find paths to connect the pairs, on a 
discrete routing grid.

One important optimization is the problem I gave.  It arises when the 
connection to be made is across a large empty space, and it is important 
to cross the space without trying all the different ways to do it.

The distance in each element of D is the distance from the starting 
point(s) to the cell represented by the element.  If cell B is next to 
cell A, with a penalty of P for moving to the cell, one way of reaching 
B is D(A)+P(B); the other is whatever external path provided a distance 
for D(B).  The requested program solves this problem for the whole grid 
at once, for the special case of moves in a single direction.

I was thinking about asking for help in solving this problem, but I came 
up with a good solution.  I hope that a better one will be found, but 
for the moment I pose it as a challenge to use J to produce an efficient 
solution for this problem which would be easily solved in C.

Henry Rich


On 2/22/2016 9:17 PM, Michal Wallace wrote:
> Huh?  :)
>
> I'm not sure I understand what any of this has to do with finding a
> shortest path.
>
> You say D is a list of ordered distances... Distances between what?
>
> Is the idea that you have a graph, with a fixed number of nodes, but the
> edge costs have shifting weights for some reason? (Like say, traffic
> congestion during rush hour?)
>
> And if so, is the idea that you're trying to dynamically adjust to the
> changing weights, to see if a longer route might be better when congestion
> is high?
>
> I'm not sure, but it seems like you're asking us to help you optimize the
> innermost loop of an algorithm you've already created. If so, it might be
> more enlightening to ask how people might solve the problem as a whole --
> maybe we might turn up a different algorithm altogether?
>
>
>
>
> On Mon, Feb 22, 2016 at 12:28 PM, Henry Rich <henryhrich at gmail.com> wrote:
>
>> This task shows J in my hands at its best and its worst.  Best, because I
>> found a good solution; worst, because it took me 4 hours to come up with
>> something that would have been trivial in a scalar language.  See what you
>> can do with it.
>>
>> The task is to write a REALLY FAST program to solve the problem.  Solving
>> the problem correctly is not so hard, but this is the innermost loop of
>> many nested loops, and it must run at close to maximum machine speed.
>>
>> The problem arises in shortest-path-finding.  You are given two lists, the
>> list of distances D and the list of penalties P.  D is to be thought of as
>> ordered left-to-right.  An atom of D indicates the minimum number of
>> penalty points that must be incurred to reach that position.
>>
>> At each step, new elements of D are created by external code, as new best
>> ways to reach positions are discovered.  After the new elements of D have
>> been installed, you come in.  You have to process D (and P) to propagate
>> the new distances through D, leaving every atom of D showing the best
>> distance.  This best distance may be either the incumbent distance at that
>> position, or a smaller value inherited from the position to its left.  If
>> you inherit the distance from the left, you must add the value of the atom
>> of P in the position being moved into.  The incumbent value in that
>> position already includes the value of P.
>>
>> There is one more fillip.  Certain positions of D are blocked off.  A
>> blocked-off atom must not be changed, and its value may not be inherited by
>> the cell to its right.
>>
>> In the representation of D, empty cells are given a distance of HIGH-VALUE
>> (=1e6), and blocked cells are given a distance of LOW-VALUE (=_1).
>>
>> Example:
>>
>> Given the setup
>> H =. 1e6
>> L =. _1
>> D =. H, H, 1, H, 5, H, 8, H, 11, L, L, H, H, 20,3
>> P =. 1, 1, 1, 2, 4, 2, 1, 1,  1, 1, 1, 1, 2, 1, 2
>>
>> you would produce
>>
>>
>>       *  *  *  3  *  7  *  9  10  *  *  *  *  20 3
>>
>> 3 = 1+2-------|
>> 7 = 5+2-------------|
>>
>> The * values indicate 'anything greater than or equal to the incumbent
>> value' and indicate atoms that are unchanged by the process.  You are free
>> to give them any value you like, as long as it is not less than the
>> incumbent value.
>>
>> The numbered values are the inherited distances: the ones you must find.
>>
>> All the values can be integer and all are small compared with the range of
>> an integer.  The length of the lists will not exceed 10,000, the values of
>> D will not exceed 50,000, and the values of P will not exceed 20.
>>
>> Your code will be executed many times.  If you want to factor out
>> computation by pre-computing any values, do so and do not count that as
>> part of the execution time.
>>
>> Henry Rich
>>
>>
>>
>>
>>
>>
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm