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

Optimizing a Determinstic Switch Tasking

Expand Messages
  • Shlomi Fish
    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,
    Message 1 of 2 , Jun 13, 2002
      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?"
    • 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 2 of 2 , Jun 13, 2002
        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.