ASSIGNMENT

1. Consider a state space where the start state is number 1 and each state k has two successors: numbers 2k and 2k + 1.

1. Draw the portion of the state space for states 1 to 15.
2. Suppose the goal state is 11. List the order in which nodes will be visited for breadth first search, depth-limited search with limit 3, and iterative deepening search.
3. How well would bidirectional search work on this problem? What is the branching factor in each direction of the bidirectional search?
4. Does the answer to (c) suggest a reformulation of the problem that would allow you to solve the problem of getting from state 1 to a given goal state with almost no search?
5. Call the action going from k to 2k Left, and the action going to 2k + 1 Right. Can you find an algorithm that outputs the solution to this problem without any search at all?

 

1. The traveling salesman problem consists of solving the order in which a person must visit each and every one of the defined cities only once, with the aim of minimizing the distance traveled. The problem definition includes a matrix of distances between the cities.

 

 

	Frederick		Hagerstown	Germantown	Shepherdstown
Frederick
Hagerstown		25.1
Germantown		21.9	44.9
Shepherdstown		31.7	18	50.7
Washington D.C		45.5	68.6	27.7	74.4

 

1. Formulate a Genetic Algorithm to solve this problem, you must define all the G.A components: a.Gene
2. Chromosome
3. Population
4. Fitness function
5. Crossover
6. Mutation
7. Roulette Selection
8. Create a code to implement your solution