[dakkon]

Hi everyone,
I've scoured the net, but couldn't find a satisfying example *with numbers* to be the answer of my question, so maybe you can help. It is a homework question, but I don't want you to do my work for me, I'm trying to understand if I got the wording right:

We have a uniform cost search problem. There are four actions with step costs 0.6, 1.1, 1.5 and 2. We know that the optimal solution has a path cost of 6. The professor is asking us the approximate number of nodes that will be generated in the worst case.

Ok, now, time complexity for uniform cost is: O (b ^ (1+(floor of(C*/e)))) where C* is the optimal solution cost( 8 here),
e is some constant of which all step costs are higher, and b is the branching factor.

What I'm not so sure are:
1) if I can select e to be 0.599..., essentially 0.6, so that C*/e is 10
2) if b, branching factor is 4, because we have four actions, (or is b not related to possible actions at all?)
3) if b is 4, and e can be 0.6, then what is the approximate number of O(4^20)? 4^10 is an exact number (1048576), so what is the approximation of it?

I would appreciate your swift replies, thanks a lot.
Dakkon

[dakkon]

Apologies, I wrote "where C* is the optimal solution cost (8 here).
It obviously should have been (6 here), not 8.

Though my questions were more on the logic of this calculation, not on the numbers themselves, so they all still stand. Thanks.