Hi for those who would like to comment on it. It helps to understand what other people are thinking as well (at least for me).
4.1
a) Local Beam search generates all successors of k initial states, then choosed the best K successors over all results and starts again. Until goal is generated.
So if k = 1, we generate the successors of 1 state, choose the best and go again. The question asks which search algorithm results from each of these
Looks like normal Hill Climbing to me (current state has successors both sides of it and we choose the best 1 and go again from there).
Or perhaps UNIFORM COst search _ which is breath first with a priority queue - thus expanding all sucessors and choosing the brest 1 (best node cost). This sounds like the best answer.
b) Local beam search with 1 initial state and no limit on the number of states retained. So we have 1 state and generate all successors, then we choose the best 1 and go again (without worrying about memory usage).
Thus is looks like were looking for a very inefficient algorithm. Cant be Normal Breadth First (it doesnt choose the best path), and cannot be Depth First (it doesnt store a lot of nodes only O(bm)). I woudl once again choose Uniform Cost Search (generates all nodes at each level, and chooses the best 1).
c) If T = 0, we will most likely not easily allow bad moves (we are already within some crevice (global minimum) which we dont really want to get out of). SO all moves are small and precise. I have no clue further.
d) If t = infinity. We allow al sorts of random moves. Sounds very much like stochastic hillclimbing, but allowing downhill moves. I would choose Random Restart Hill CLimbing - why? It generates random initial states (will eventually generates the goal state). Hence jsut as random as Simulated annealing with T = infinity.
e) Genetic Algorithm with population size = 1. The fitness function would result in only 1 item to choose, which would have to reproduce with itself...The crossover point would be chosen and the first and last parts of the string would just be swapped around. Then we would have a random mutation of 1 of the digits. Basically we are just arranging and randomly changing a digit.
What kind of search algorithm? I have no idea.
Your inputs much appreciated.
Danie van Eeden
------------------------
