Re: can-of-worms

Drew Krause wrote:
Ken Tilton wrote:

Constraints? All numeric all the time? Looking for shorter paths? Is func1 always to be applied to the output of func2 applied to all atoms? no. sorry. but howseabout func1 always applied to ((output of func2 applied to any number of atoms) and any number of atoms)? No iteration in the final form? etc etc.


OK. To lay bare the problem I'm working on, I have:

a starting node,
and ending node,
several unary operations that can act on the first or any intermediate steps,
and no other restrictions that I'm aware of (*except* that failure is a possibility)

so for example, tg = target, s = start, op1...opn = operations

solution might look like tg = (op2 (op1 (op7084 (op10 (op2 (op5 s))))))

.. and yes, shortest path would be nice, but ITWICG (I'll take what I can get)..


sounds like an A* problem. A* (A-star) is a search algorithm
that finds optimal paths in maze or near-maze conditions. It's
basically an optimization of breadth-first search.

What it consists of is keeping a set of reachable points (numbers
in this problem domain, I guess) ordered by an estimate as to the
minimum possible number of steps from each point to the solution
space. You use some kind of heuristic to come up with the estimate.
You repeatedly take the point with the smallest estimate, apply your
possible moves to that point to give you new points, apply your
heuristic to the new points to give estimates of remaining-steps
for each, and then repeat.

The heuristic is key. As long as it's conservative (smaller than
the actual number of steps required to get there from that point)
the algorithm is guaranteed to find the shortest path.

Bear









.

Relevant Pages

  • Re: can-of-worms
    ... but howseabout func1 always applied to ((output of func2 applied to any number of atoms) and any number of atoms)? ... After which any number of operands can be used, and each can be used any number of times. ... I wonder if something like Screamer or Prolog would make this easier to express. ...
    (comp.lang.lisp)
  • Re: Howto access to a prolog database
    ... readwrite(Source, Target), ... The choice-point of the repeat is never destroyed. ... Why doing concat_atom to create long atoms and then write? ... translate_value(Term, SqlValue):- ...
    (comp.lang.prolog)
  • Re: can-of-worms
    ... Drew Krause writes: ... func2 applied to any number of atoms) and any number of atoms)? ... and ending node, ...
    (comp.lang.lisp)
  • Re: can-of-worms
    ... Ken Tilton wrote: ... but howseabout func1 always applied to ((output of func2 applied to any number of atoms) and any number of atoms)? ... and ending node, ...
    (comp.lang.lisp)
  • Re: can-of-worms
    ... domain-knowledge, so: ... stripped-down version: ... Given the atoms +,*,1,2 and a number n, the function returns n ... but howseabout func1 always applied to and any number of atoms)? ...
    (comp.lang.lisp)