Probabilistic Model

NTT Communication Science Labs.

• If p > n/B, the second scenario is more attractive.

• If p becomes reasonably high by incorporating appropriate heuristics, the weak-commitment search will be more efficient.

14

probability p

without BT

with BT

B

probability q

p

pq

pq2

average n+Bq

average n/p

min-conflict BT

weak-commitment

n

n

3n

2n

n

Prev

Next

Top

With Graphics