Subject: Optimizing a Determinstic Switch Tasking

From: Shlomi Fish <[email-masked]>
Date: Thu, 13 Jun 2002 16:51:54 +0300 (IDT)

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        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 13 Jun 2002 20:26:33 +0300 (IDT)

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:

> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>