[Jprogramming] A practical problem: minimum distance with penalties

[Henry Rich]

'proc' has the right idea, but CP+<./\ CD does not take into account all 
the P values between the minimum point found by <./\CD and the point 
that the minimum value is being propagated to.  It adds in only the last 
P.  [Also it doesn't prevent a value from affecting results on the other 
side of a blockage, but I reckon you were going to deal with that in a 
later version.]

The data structure is a rectangular table representing the display.  
Think of each point as representing a pixel (actually the gridpoints are 
bigger than pixels, but the idea would be the same).

The program starts with a set of block locations and desired wires.  
Routing the wires involves allocating 'pixels' to the wires.  The 
algorithm starts at the source of the net, probing pixel-by-pixel until 
it reaches the goal.  At each pixel-step there are several different 
moves (straight, bend, jog), and there are penalties for each, as well 
as penalties for crossing a wire or getting too close to another wire or 
to a block.  The algorithm proceeds until the best route is found.

[I don't want to consider here any major changes in approach.  The 
method works, looks OK, and fits in with a larger design goal of using 
the result of the wiring phase to detect areas of congestion and change 
the placement accordingly.]

The main point in the implementation is to keep from wasting time 
following paths that are not part of a best path.  My code uses several 
techniques to score paths as they are created and put unpromising ones 
on the shelf while the most promising ones are continued to a conclusion.

But a problem arises in certain complicated situations where the 
position has so many blockages that it is impossible to get a good idea 
of what the final route will be.  Then, even (or especially) when the 
algorithm is routing over a large empty area, it tries all the different 
ways to cross the area with two turns, and there are a lot of those 
ways, all with the same score, and the route bogs down trying to keep 
them all active.

You could think of several ways to respond to this problem, but the 
easiest and best that I can see is to zip across straight areas with one 
long leap rather than pixel-by-pixel - best, that is, provided it can be 
implemented efficiently.  That is where the current problem comes from.  
The list D represents one row (or column) of pixels: at certain pixels 
there is a new source-to-pixel distance, coming from all the bends and 
jogs that cross the row; at other pixels there is an old distance left 
over from previous routes.  The goal is to calculate the best 
source-to-pixel distances for each pixel in the row, all in one go.

This whole-grid processing will be slower than pixel-by-pixel processing 
much of the time, but I think I can detect when those times will be and 
use the whole-grid method only when it will be worthwhile.

Henry Rich



On 2/23/2016 12:30 AM, Raul Miller wrote:
> So, ok, maybe we can talk a bit more about the system this fits into,
> in dissect? Please forgive me for being slow, I'm not thinking about
> this very well at the moment.
>
> My first attempt at an implementation looked like this:
>
> 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
>
> proc=: dyad define
>    P=. x
>    D=. y
>    C=. notblocked=. _1 ~: D
>    CP=. C#P
>    CD=. C#D
>    C #inv!._1 CD<.CP+<./\ CD
> )
>
> Here, I was thinking that D would represent the shortest distance from
> any node to the left. But, clearly, that's not what you have asked
> for. Instead, you're going for "nearest left neighbor", and apparently
> there tend to be a lot of these, and you run a lot of tries.
>
> So, taking a step back, just a little - for dissect I imagine you have
> a rectangle size that you need to support (and presumably you're
> clamping these sizes for large arrays, with interior scrolling within
> the rectangle though... hmm... a quick test (10+i.1e3 1e3) suggests
> that you are also handing the entire inner rectangles off to Qt to
> manage - perhaps out of necessity, given the current jQt
> implementation?).
>
> Anyways... I imagine your data structure is some kind of a directed
> acyclic graph describing which rectangles connect to which rectangles
> and you're trying to approximate a "minimum total distance for the
> connections" algorithm.
>
> So... all of this sort of suggests that D represents a specific path
> from the start of the expression down through the various rectangles
> representing intermediate results and down to a specific
> [intermediate] result.
>
> But that path contains several aspects: left-to-right position and
> where you introduce the bends. So, anyways, presumably this
> represents... the location of those bends? And the total horizontal
> distance traveled?
>
> (As you can see, I'm having trouble understanding the spec itself, and
> not just the algorithm it fits into... )
>
> Going back to the algorithm I described above - it might represent
> something like an A* approach if you slapped a ^:_ onto it. But
> limiting us to the immediate left neighbor? That... doesn't actually
> seem to me to be an a star algorithm.
>
> Anyways, if you feel comfortable spelling this out in more detail, I
> think that could help me understand what you're asking for.
>
> Thanks,
>