Re: C to Forth converter?

On Apr 22, 11:29 am, J Thomas <jethom...@xxxxxxxxx> wrote:
On Apr 21, 6:40 pm, Jean-François Michaud <come...@xxxxxxxxxxx> wrote:



On Apr 21, 2:28 pm, Frank Buss <f...@xxxxxxxxxxxxx> wrote:
BTW: this reminds me of another question some time ago in this newsgroup:
how to find the minimum number of instructions for solving a stack juggling
problem? I've written a small Flash animation for it, with a very limited
set of Forth words:

http://www.frank-buss.de/forth/reverse.html

The solution for 5 cells could be extended to arbitrary number of cells.
But is this the shortest solution? Is it provable, that a given solution is
the shortest solution?

This seems to be a variant of the shortest path problem (or traveling
salesman problem without the constraint of having to visit every
"city" once; or more generally, of combinatorial optimization), you
would have to lay down a planar graph of possible operations and a
goal which would be and order of parameters in which you want the
algorithm to converge towards.

And to answer your question, yes it's provable, but if I remember
correctly this problem is NP Hard, which means there's no polynomial
time solution, which means that your algorithm will only run
relatively fast for relatively small problem sets but will become
impractical for larger sets. It will take as much time for you to find
the optimal solution as it will to actually prove that it is the
optimal solution because the only way to find that it is optimal is to
run the algorithm until it finds the solution. It's NP difficult to
prove and provably difficult to prove ;-P.

It doesn't matter whether it's NP-Hard if you never need to solve the
hard problems.

Hehe, thats what I was saying though, It will work for relatively
small problem sets, but will be impractical for larger ones. Frank
Buss's question question was whether the solution could be extended to
work for more than 5 stack elements (it can) and whether it was
provable that a solution was the shortest solution (it also can, but
the consequence of the problem being NP-hard is that it will take as
much time proving that a solution is optimal as it does actually
finding the optimal solution so it's not, in general, useful to prove
that we have an optimal solution because you'll have to run the
algorithm until it reaches a conclusion anyways; you might as well
just run the algorithm in all cases to find the optimal solution and
prove at the same time that it is optimal instead of finding solutions
and then trying to prove that they are optimal. This will work for
small problem sets but will become largely impractical because of
combinatorial explosion for larger problem sets.).

Do it in Forth and what's the chance you'll need ten
stack operations to get a lot of stack parameters just right. Though
translating from C you might....

If you follow good coding practices (particular to Forth), then odds
are you won't encounter larger problem sets, but I'm not at all
certain what kind of results a conversion from C to Forth would yield
as far as stack arguments goes.

[SNIP]

Regards
Jean-Francois Michaud

.

Relevant Pages

  • Re: C to Forth converter?
    ... small problem sets, but will be impractical for larger ones. ... work for more than 5 stack elements and whether it was ... finding the optimal solution so it's not, in general, useful to prove ... If you find the shortest versions ...
    (comp.lang.forth)
  • Re: Measuring the effectiveness of a GA implementation?
    ... GA - or of any optimisation algorithm, ... comparison with an optimal solution is ... mean fitness) plus, preferably, some measure of the ... about evaluating effectiveness of optimisation algorithms (I'm loath to ...
    (comp.ai.genetic)
  • Re: Needleman-Wunsch - producing more than the optimal solution -- please help
    ... What I want is the optimal solution, second optimal solution, third ... an issue I see is that it's not clear to me that the algorithm actually compares solutions to find the "optimal" one so much as it detects the best alignment of two inputs based on a pre-computed weighting matrix. ... But the moment you allow for the choice of something other than the maximal choice, you have to deal with every permutation possible, and evaluate those permutations in some way. ... Not only would you, after redoing the choice, have to recompute the rest of the "F" matrix that depended on that choice, there's no guarantee that when you're done, the score in the lower-right corner that results from that replacement would indeed be the next-lowest score possible in the matrix. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Shortish paths
    ... Remember I'm not asking for an algorithm, just for advice on what to ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Shortish paths
    ... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)