From: Gavin Kistner <gavin@...>
Date: 2005-05-10T11:28:44+09:00
Subject: Re: Representing Undirected Edges (advice, please)

On May 9, 2005, at 5:30 PM, Jacob Fugal wrote:
>> I feel that it is necessary to avoid evaluating n^d ( n-number of  
>> paths, d-
>> dimension of criteria) items in searching for an optimal path ...
>
> You don't need to evaluate them, unless you want to consider all
> criteria at once. Usually you'd only choose one criterion. A
> pathfinder which only cares about one criterion only needs to evaluate
> one value from each of n paths. With incidence matrices you'd only
> select one matrix (that corresponding to the chosen criterion) and
> have n evaluations. Same boat.

Aye. My goal for this library is to first make it really clear (and  
probably slow). It will yield repeatedly to user-supplied blocks/ 
methods to decide what to do.

"In general, would you like me to try breadth-first or depth-first?"

"Hey, I can't get to the end node from the current node, but here are  
the nodes I can directly get to from here. Given my path so far, do  
you have any preference for which node I try next?"

"OK, I have 3 edges to get to the node I'm going to try. Which one  
seems best?"

"Given the route I've got so far (and given any sort of instance  
variables you've stored as I've been traversing) is it worthwhile to  
continue trying this particular path, or should I give up on this one?"

"Here are two routes I've found so far. Which one is better?"

The "which edge should I use?" question will help pare things down a  
good bit, but (in my experience with the quiz) the "is it worthwhile  
to continue trying this particular path?" question is the one that  
really gives you the ability to pare down the search tree massively.


Thanks for the continuing questions that help me critically think  
about this.


--
(-, /\ \/ / /\/