Forum Freshman
Joined: 11 May 2008
Posts: 1
|
I ran across a paper recently which contained a reference to the classic 1975 Knuth paper titled "Estimating The Efficiency of Backtrack Programs" JSTOR link. There's also an alternate link to a summary of the paper for those without JSTOR access (like me).
So, basically, I understand the concept. Knuth proposes estimating the running time of a CSP solver by repeated sampling of the search tree using random assignment of successor states without backtracking. In this way Knuth makes use of the law of large numbers and observes that the average of the sampled branches will eventually converge to the actual cost of running the program to find some solution. Easy.
I also understand that in the paper Knuth proposes introducing systematic bias into the successor-selection part of the algorithm in order to measure variability.
What I'm struggling with is Theorem 2, where Knuth asserts that there exists a set of probabilities which are perfect and, given such a set, the cost estimate will always equal the actual running cost of the program.
Specifically, Knuth's theorem asserts that:
probability*_k(j) = Cost(T(x1, ... xk+1(j)) / (Cost(T(x1, ... ,xk) - c(x1, ... xk))
I've deciphered this as: the cost of the tree given a randomly selected successor state (j) as an assignment for variable xk+1 divided by the cost of the tree from (x1...xk) minus the cost of the parent state (of j).
So, I want to find what these "perfect" probabilities are for the Instant Insanity subtree leading to the solution (as shown in the paper). My problem is my math doesn't add up. To put this into perspective:
The actual costs associated with the tree are:
3+16*3+16*10+24*13+1 = 524
I've been able to work out the following probabilities:
p1(j) = (3+16*3)/3 = 17 (ie. cost of tree at level 1 divided by the root cost).
p2(j) = (3+16*3+16*10)/((3+16*3)-16) = 6 (cost @ level 2 divided by cost at level 1 minus cost of parent state)
p3(j) = (3+16*3+16*10+24*13)/((3+16*3+16*10) - 16) = 2.68
p4(j) = (3+16*3+16*10+24*13+1)/((3+16*3+16*10+24*13)-24) ~ 1
Plugging the above into Step E4.1 of Knuth's algorithm yields:
3+16*17+16*16+ 24*2.68+1 = 436.
So, something is wrong somewhere. I suspect I've totally misunderstood some simple point (like maybe I'm not calculating tree costs correctly) but I can't for the life of me work out what I'm doing wrong. I've been starting at this for 2 days without any luck so I thought I'd post in the hope that people wiser than I might be able to shed a clue on this for me 
Any help would be greatly appreciated. It's driving me insane!  |
|
