On Fri, Jul 13, 2012 at 10:24 AM, Raul Miller <[email protected]> wrote: > Anyways, I'll try and put my thoughts into code.
So... mostly I did not write any code yet. Instead, I ran into some minor problems and did not have enough motivation to do much about them, so I slept on them instead. I think the biggest issue which bothers me is this data structure: require 'strings' dists =: 20 20 $ ". 0 :0 rplc LF,' ' _ 81.6 _ _ _ _ _ _ _ _ 286.1 _ _ _ _ _ _ _ _ 315 81.6 _ 57.6 _ _ _ _ _ _ 221.1 _ _ _ _ _ _ _ _ _ _ _ 57.6 _ 51.9 _ 108.6 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 51.9 _ 48.4 _ _ _ _ 223.2 _ _ _ _ _ _ _ _ _ _ _ _ _ 48.4 _ 54 128.9 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 108.6 _ 54 _ 93.5 _ 203 173.7 _ _ _ _ _ _ _ _ _ _ _ _ _ _ 128.9 93.5 _ 38.3 160.5 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 38.3 _ _ _ _ _ 97.5 _ _ _ _ _ _ _ _ _ _ _ _ 203 160.5 _ _ 78 _ 47.2 99.3 _ _ _ _ _ _ _ _ 221.1 _ 223.2 _ 173.7 _ _ 78 _ 64.3 _ _ _ _ _ _ _ _ _ 286.1 _ _ _ _ _ _ _ _ 64.3 _ 109.8 _ _ 178.3 265.5 _ _ 229.4 174.9 _ _ _ _ _ _ _ _ 47.2 _ 109.8 _ 103.5 _ 107.5 _ _ _ _ _ _ _ _ _ _ _ _ 97.5 99.3 _ _ 103.5 _ 178.2 183 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 178.2 _ 62.4 _ 216.5 _ _ _ _ _ _ _ _ _ _ _ _ _ 178.3 107.5 183 62.4 _ 149.3 208.2 _ _ 289.1 _ _ _ _ _ _ _ _ _ _ 265.5 _ _ _ 149.3 _ 90.6 _ 217.3 _ _ _ _ _ _ _ _ _ _ _ _ _ _ 216.5 208.2 90.6 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 58.4 85.8 _ _ _ _ _ _ _ _ _ _ 229.4 _ _ _ _ 217.3 _ 58.4 _ 105.5 315 _ _ _ _ _ _ _ _ _ 174.9 _ _ _ 289.1 _ _ 85.8 105.5 _ ) One problem, here, is that I do not know how to make a "good" estimator for finding a path between cities here. The best I can think of is "path length so far". And, given that estimator, the A* algorithm, conceptually, would just drive a circle around the nodes which have been completely explored so far, expand it until it includes an unexplored node and then explore inside its radius -- this process would complete until the result was found. Except, hypothetically speaking, this would not be a circle but an n-dimensional hypersphere -- there's nothing about the data structure which prevents it from representing location in strange topology. (And, if we get into multiple modes of transportation -- air, foot, car, train, boat... -- we can get some cases where travel cost (time, money, whatever) is different from distance... but then you can get into scheduling costs and other factors which do not depend on path. So I am going to ignore that -- and, anyways, that's not represented in the data here.) Also, if I was going to use "distance traveled so far" as my estimator and if I wanted to use A* I would probably want to start from both known locations and swap back and forth between them (whichever had the best estimates so far) until the explored territories overlapped. But that's not the A* algorithm any longer so it doesn't make sense to me try to tune the A* implementation to deal with this case. Another approach would be to include city location (for example: latitude and longitude for each city). If we know where the cities are located we can produce a somewhat plausible estimator based on distance to destination. And, this would work with A* (even an A* where my frontier was just a set of paths -- with bestness calculated based on the paths and the representation of the city graph and locations) just fine... but I'd have to cook up some data to work with to try this out... Another issue with the algorithm is that the paths could be directional -- roads between cities could be one way? But, again, that's not represented here. Another approach might be to first find the shortest distances between all the cities, and prune the paths which are not optimal, but if you are going to do that (indexing numbers from (] <. <./ .+)^:_~ dists), is it fair to call the result A*? Anyways... I have too many questions to know where I would want to take this. On a related note: somewhere along the line I picked up the idea that "it's good to design code for re-use". But in my experience, designing code to deal with unstated requirements is almost always a bad idea. What happens is: when the requirements get stated they are new things that I did not design for. So I wind up with complexities in my code to deal with cases that no one cares about. It's better to focus on requirements that people care about. (Which can include interfaces to other code -- and there we wind up with designs that need to focus on simple sequences of interaction. The classic OS interface -- open/use/close -- is probably appropriate here for anything too big to make an atomic operation. But that's only worthwhile for community efforts.) Anyways... I wan't able to put my thoughts in code here -- my code didn't make sense to me. FYI, -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
