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 <bmcclos...@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.
