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