(Mod my ignorance)

This appears to be computer science/math problem and has nothing
specifically to do with statistics nor R. So I suggest you post on a more
appropriate venue rather than here.

Cheers,
Bert


Bert Gunter
Genentech Nonclinical Biostatistics
(650) 467-7374

"Data is not information. Information is not knowledge. And knowledge is
certainly not wisdom."
H. Gilbert Welch




On Wed, Mar 5, 2014 at 9:44 AM, McCloskey, Bryan <bmccloskey@usgs.gov>wrote:

> Here is some example data (hopefully the monospace formatting is
> preserved):
>
>     a   b   c   d   e
>     -   -   -   -   -
> 1 | F | T | F | T | F |
>     -   -   -   -   -
> 2 | T | F | T | F | T |
>     -   -   -   -   -
> 3 | T | T | F | F | F |
>     -   -   -   -   -
> 4 | F | T | F | T | F |
>     -   -   -   -   -
> 5 | F | T | F | F | T |
>     -   -   -   -   -
>
> So, for cell b1, the shortest possible path to a true value in row 5 is
> b1-a2-a3-b4-b5 (distance: sqrt(2) + 1 + sqrt(2) + 1).
>
> * Shortest paths are not necessarily unique, but I just need to find the
> length.
>
> * If it's computationally hard to guarantee the absolute shortest path, I
> can probably live with "nearly" shortest paths.
>
> * Paths can "backtrack", so the shortest path from cell e2 to row 4 is
> e2-d1-c2-b3-b4-b5.
>
> I need to calculate the shortest path for all true cells to all rows
> further down the matrix. I'm afraid I'm going to have to write some sort of
> recursive path-tracing algorithm, but I'm hoping there's a package already
> in existence that accomplishes this already...
>
> -bryan
>
> On Tue, Mar 4, 2014 at 1:13 PM, McCloskey, Bryan <bmccloskey@usgs.gov
> >wrote:
>
> > I have a binary rectangular T/F matrix; I need to be able to calculate
> the
> > shortest path (i.e., Pythagorean distance) between a populated cell in
> row
> > j and any populated cell in some row j+n.
> >
> > For instance, if I have a chessboard with random black/white square
> > colors, I need the shortest distance (linear distance, not number of
> steps)
> > for a king to get from a specified black space on the first row, to _any_
> > black space in a specified further row, traveling only on black spaces.
> >
> > Any idea? Thanks,
> >
> > -bryan
> >
>
>         [[alternative HTML version deleted]]
>
> ______________________________________________
> R-help@r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>

	[[alternative HTML version deleted]]


