BrowserUk,
You're still missing the point.

I don't believe I am.

You can only know when to stop looking for an improvement...

For the sake of argument, let's distinguish between "initial best guess after preliminary analysis" and "refining that guess to find better solutions". Of course you are going to decide to stop looking for an improvement otherwise you might as well do an exhaustive search. The question is what types of "initial guessing" and "refinement approaches" lead to the "best guess" across varied data. If the refinement approach only limits changing the guess of 1 category at a time then of course there is a limit to improvements that can be made.

Without running an exhaustive search you have no way of judging how good any particular heuristic is for any given dataset.

I am not trying to judge how good a heuristic algorithm is against the optimal solution - just how good they compare to each other and how quickly they converge on the "best guess". I have already created a way to generate puzzles of large varied data and have a way to automate the scoring so it is easy to see how they behave.

And whilst your modifications find better solutions for this dataset, maybe my original will work better for a different dataset?

Hmm. That would be impossible. I just extended your original refinement algorithm. You iteratively went through and said after an initial guess, would the score improve if I change the guess for category X (looping in order). If yes, you started over. My modification doesn't start over - it just pushes that improvement on the work queue and says - if instead of modifying the guess to category X - would I improve my score if I changed category Y instead. In other words, it too checks improvements of changing just 1 guess at a time but unlike yours, it checks all possible improvements. I was just hoping there was a way to use prior knowledge (already using a %seen hash) to know that a particular path couldn't possibly lead to a score better than the current best.

And without an exhaustive search of a representative sample of datasets, you've no way to compare the efficacy of different heuristics.

Well, for now I am comparing them to each other and to be honest, they all perform very close to one another if they use my modified refinement algorithm. I am however thinking about a solution that will produce a guaranteed optimal solution without performing an exhaustive search by limiting the input to a specific set of conditions such as the dictionary used, length of words, number of categories, etc. It may be impossible but I learn from the exploration regardless and I have been successful in the past.

Feel free not to reply. I was serious about not needing to indulge me.

Cheers - L~R

In reply to Re^6: Challenge: Letter Power by Limbic~Region
in thread Challenge: Letter Power by Tanktalus

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.