- Can I Get The Answers For These 1 (705.12 KiB) Viewed 40 times
Can I get the answers for these?
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
Can I get the answers for these?
Can I get the answers for these?
3) Applications (20 marks] POLITICAL MAP OF THE WORLD 1 January 12 Map 1 Above is a map of the countries in the world for reference. The graph colouring problem is an application where the countries of a map must be coloured so that no two adjacent countries (touching or neighbours) are the same colour. Current theory states that this can be done with four colours. Assume that we number the countries of a map 1,...,n; we number the colours 1,...,4; and that we have an n by n matrix which contains 1 at each row (i) and column (j) where region i and j are neighbours (are adjacent) and 0 otherwise. You decide to solve the graph colouring problem using a Hill Climbing algorithm. 3.1) Give the pseudo code for the Random Mutation Hill Climbing (RMHC) algorithm specialised for solving this problem. [5 marks] 3.2) Describe in words the representation you would use and give a small example (less than 10 countries). [3 marks] 3.3) Describe in words the fitness function you would use and state whether you would minimise or maximise the calculation. [4 marks] 3.4) Describe in words the small change operator you would use. [2 marks] 3.5) Highlight the similarities and/or differences between Random Mutation Hill Climbing, Random Restart Hill Climbing and Simulated Annealing algorithms. [6 marks]
3) Applications (20 marks] POLITICAL MAP OF THE WORLD 1 January 12 Map 1 Above is a map of the countries in the world for reference. The graph colouring problem is an application where the countries of a map must be coloured so that no two adjacent countries (touching or neighbours) are the same colour. Current theory states that this can be done with four colours. Assume that we number the countries of a map 1,...,n; we number the colours 1,...,4; and that we have an n by n matrix which contains 1 at each row (i) and column (j) where region i and j are neighbours (are adjacent) and 0 otherwise. You decide to solve the graph colouring problem using a Hill Climbing algorithm. 3.1) Give the pseudo code for the Random Mutation Hill Climbing (RMHC) algorithm specialised for solving this problem. [5 marks] 3.2) Describe in words the representation you would use and give a small example (less than 10 countries). [3 marks] 3.3) Describe in words the fitness function you would use and state whether you would minimise or maximise the calculation. [4 marks] 3.4) Describe in words the small change operator you would use. [2 marks] 3.5) Highlight the similarities and/or differences between Random Mutation Hill Climbing, Random Restart Hill Climbing and Simulated Annealing algorithms. [6 marks]
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!