Re: [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 <henryhr...@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

----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm