Searching Problem with Numbers

Question

Start state = Number "4"
Target state = Number "5"
Successor function:

• factorial, cost = 3
• square root, cost = 2
• floor, cost 1.

1. Frame this problem as a regular AI "search" problem.
2. Find the shortest cost path from start node to target node.

Comments

Should we compute the factorial (gamma function?) on nodes with fractional values or can we say that that operation is illegal for non-integers?

Answer 1

This problem could be solved using UCS if we use a search tree with '4' as the root. The branching factor is 3 with each branch having a different cost.

Let's use a notation of ('node name',cost) when discussing this problem.

('4',0) -> [ ('4',1), ('2',2), ('24',3) ]

The ('4',1) is suboptimal as a repeated value and the ('2',2) node leads to a dead end due to the factorial.

The best option is to choose ('24',3) as the next item.

('24',3) -> [ ('24',4), ('4.89...',5), ('24!',6) ]

The ('4.89...',5) leads to nodes '2' and '4' again based on the operations and the '24' node is the identity. We should continue with ('24!',6).

Since '24!' is a large number, we will certainly use the square root several times. Luckily, after 5 rounds, we get '5.54', which the floor function can turn into the desired 5.

(4,0) -> (24,3) -> (24!,6) -> (sqrt(24!),8) -> (sqrt(sqrt(24!),10) -> (sqrt(sqrt(sqrt(24!)),12) -> (sqrt(sqrt(sqrt(sqrt(24!)))),14) -> (sqrt(sqrt(sqrt(sqrt(sqrt(24!)))),16) = ('5.54',16) -> (5,17)

Thus, we can reach the desired state of '5' at a cost of 17 units.