The code presented below implements a complete, informed generator. Each combination generated is tested on the fly instead of storing the combinations. The generator is non-redundant as it produces all the possible combinations in a proper sequence thus making sure that no combination is generated twice. The code is as follows. By nature of the problem some variables can have only selected values.
S denotes the starting state and G denotes the goal state.
The number attached to each edge in the graph represents the COST of traversing the edge. Show your work . Suppose that we remove that assumption. Discuss how allowing some of the costs to be negative would affect the search methods below, and illustrate the effects of this change with examples. Because these four search methods do not consider cost, it will not make any difference to these methods if we allow negative costs.