More precisely:Searching a solver for all tasks in the sequence:
To find and then freeze qn+1, do in parallel:
SEARCH1: test all prefixes on all tasks ? n+1
SEARCH2: test only prefixes starting with qn, and only on task n+1! (safe because we know such prefixes solve all tasks ? n)
Both searches depth-first: branches of search tree are program prefixes; backtrack (restore tasks and states) once the sum of runtimes of current prefix on all current tasks exceeds prefix probability times current search time limit
8-bias-optimal: lose at most factor 2 for SEARCH2, factor 2 for backtracking, factor 2 for incremental time limit doubling
Back to J. Schmidhuber's OOPS page