Loading ...
Sorry, an error occurred while loading the content.

Re: Optimizing a Determinstic Switch Tasking

Expand Messages
  • Shlomi Fish
    Replying to myself, I came up with a greedy algorithm that is not optimal. What we do is give the first scan (which we don t in advance what it is) a quota of
    Message 1 of 2 , Jun 13 10:26 AM
    • 0 Attachment
      Replying to myself, I came up with a greedy algorithm that is not optimal.
      What we do is give the first scan (which we don't in advance what it is) a
      quota of N[1] iterations. We choose the scan that solves the most boards
      in this time, and limit it to the maximal number of iterations in which it
      will solve all these boards.

      We then update the database by removing all these boards, and subtracting
      N[1]~ iterations from the iterations count of all the other boards for
      this scan. We then repeat the process for an extra N[2] iterations, and so
      forth until all boards are solved.

      I can run this algorithm for any given { N[i] | 1 <= i < inf } vector and
      receive the optimal result for it.

      Regards,

      Shlomi Fish

      On Thu, 13 Jun 2002, Shlomi Fish wrote:

      >
      > I thought of this question in regard to Freecell Solver, but it is not
      > really specific to it. There are many ways in which I can configure
      > it to solve boards, and some would work much better than others for some
      > boards. What I can also do is suspend a scan from running after a given
      > number of iterations, and resume it from there. (both actions take
      > O(1) time).
      >
      > Now, let's suppose I collect data about several elementary scans for a
      > large constant range of boards. I'd like to run the scans in a certain
      > order in which each time, each of them would be run for a certain number
      > of iterations.
      >
      > For example. Suppose my scans are A, B, C, D and E, than I can run them
      > as:
      >
      > A@500, B@300, A@200, C@100, D@1000, ....
      >
      > What I want is that for the entire range of boards, the total number of
      > iterations for solving all of the range would be minimal.
      >
      > Does anybody know of a numeric or algorithmic way to optimize it or
      > achieve it? One thing I thought about is that we can assume the order is
      > rotating:
      >
      > A@t_A1, B@t_B1, C@t_C1, A@t_A2, B@t_B2 ...
      >
      > and then perhaps assign zeros for some of the t's.
      >
      > But other than that, I'm stumped.
      >
      > Regards,
      >
      > Shlomi Fish
      >
      >
      >
      > ----------------------------------------------------------------------
      > Shlomi Fish shlomif@...
      > Home Page: http://t2.technion.ac.il/~shlomif/
      > Home E-mail: shlomif@...
      >
      > "Let's suppose you have a table with 2^n cups..."
      > "Wait a second - is n a natural number?"
      >
      >
      >
      > To unsubscribe from this group, send an email to:
      > hackers-il-unsubscribe@egroups.com
      >
      >
      >
      > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
      >
      >



      ----------------------------------------------------------------------
      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      "Let's suppose you have a table with 2^n cups..."
      "Wait a second - is n a natural number?"
    Your message has been successfully submitted and would be delivered to recipients shortly.