本科人工智能作业代写 Artificial Intelligence代写

CS367: Artificial Intelligence

Worth: 10% of total grade [10 marks]

Due Date: Friday August 20th 2021, 23:59

本科人工智能作业代写 Make two heuristics, h1 and h2, for the BubblePuzzle. h1 should be stronger than h2 and neither should be the 0-heuristic.

Greedy Search versus A* (10 marks): 本科人工智能作业代写

Task1: (1 mark)

You will have to download the A1.zip file for this assignment. You should only make changes to the search.py file. Do not change other files. Instrument the astar_search code in search.py so that it prints out

the number of expanded nodes (when a node is removed from the open list and added to the closelist),
the number of generated nodes (when a node is created from itsparent),
the number of duplicate nodes (when the state is already in the open list or the closedlist),
the solution path, andthe
the solution path length. 本科人工智能作业代写

In addition figure out how to make a greedy_search algorithm (there are comments above astar_search in the search.py file saying how to do this). You should call it as you would astar_search, as follows:

astar_search(EightPuzzle((1,2,3,4,0,6,7,5,8))) greedy_search(EightPuzzle((1,2,3,4,0,6,7,5,8)))

Task 2: (1 mark) 本科人工智能作业代写

Implement the Manhattan distance heuristic for the EightPuzzle class, called it h_Man. Find the “misplaced tile” heuristic that is already in the code, and rename it h_MT.

Task3: (1 mark)

Run the following 5 problems with both the “misplaced tiles h” (this is given in the code) and your Manhattan heuristic.

The five problems you should run are:

Problem	Optimal solution path length
EightPuzzle((1,2,3,4,0,6,7,5,8))	2
EightPuzzle((2,3,6,1,0,4,7,5,8))	8
EightPuzzle((5,3,6,2,0,7,1,4,8))	14 本科人工智能作业代写
EightPuzzle((1,5,6,3,4,8,0,2,7))	20
EightPuzzle((3,2,5,6,8,4,0,7,1))	26

Make a table as follows

		Prob1	Prob2	Prob3	Prob4	Prob5
Misplaced Tile	A* expanded nodes
	Greedy expanded nodes
	Greedy Solution Path Length		本科人工智能作业代写
	A* Solution Path Length
Manhattan	A* expanded nodes
	Greedy expanded nodes				本科人工智能作业代写
	Greedy Solution Path Length
	A* Solution Path Length

Task 4: (2 marks) 本科人工智能作业代写

Make a new class BubblePuzzle to solve the following puzzle. https://www.crazygames.com/game/bubble-sorting

You should call it as follows:

astar_search(BubblePuzzle([[RED, BLUE], [RED], [BLUE], []]))

This is an initial state with 4 bottles. The first bottle has red on the bottom and blue on the top, the next bottle just has red, the third bottle just has blue and the last bottle is empty.

Task 5: (2 marks)

Make two heuristics, h1 and h2, for the BubblePuzzle. h1 should be stronger than h2 and neither should be the 0-heuristic.

Since you are running A* you should make sure your heuristics are admissible and consistent. If your heuristic is not admissible or not consistent you might notice that you are getting solutions longer than optimal. If you see solutions shorter than optimal, you have a bug in your actions or your goal test.

To help you out here are 4 problems and their optimal solution path length.

Problem	Solution path length
[[RED,BLUE],[BLUE,RED],[],[]]	3
[[RED,ORANGE,BLUE,ORANGE],[RED,RED,BLUE,BLUE],[BLUE,RED,ORANGE,ORANGE],[],[]]	10
[[RED,ORANGE,BLUE,ORANGE],[RED,RED,BLUE,BLUE], [BLUE, RED,GREEN,GREEN], 本科人工智能作业代写 [GREEN, ORANGE,GREEN,ORANGE],[], []]	14
[[GREEN,RED,RED,BLUE],[RED,ORANGE,PURPLE,PURPLE],[BLUE,GREEN,BLUE,ORANGE], [ORANGE,RED,ORANGE,GREEN],[PURPLE,PURPLE,GREEN,BLUE],[],[]]	17

Task6: (3 marks) 本科人工智能作业代写

Write a report discussing how A* compares to greedy search when you have a weak heuristic and a stronger one. Use the table from task 3 and include a similar table for the BubblePuzzle.

Task7: (Extra for Experts – 1 bonus mark – a bonus mark can be used to offset any lost marks in any assignment – but you cannot get more than 30 marks in the practical section)

Make your code handle inconsistent heuristics.
Make an admissible and inconsistent heuristic for the Eight Puzzle.
Prove that your heuristic is admissible and inconsistent.
Instrument your code to print out reopened nodes (a duplicate node whose g-value is lower than the node with the same state in the open list or the closedlist)

What you need to turn in:

You need to turn in a search.py file with all your code.

You need to turn in a .pdf file of 2 page MAXIMUM (it can be 4 pages if you did the extra for experts task) which should include:

1)The expanded nodes table for the both sliding tiles and bubble sort.

2)A discussion of how you think greedy compares to A* when the heuristic is weak versus when it is strong. Also, how the number of nodes expanded is affected by whether a solution path is short or long. 本科人工智能作业代写

Marking is based on the following material:

1 mark for having instrumented the code correctly and created greedy search

1 mark for implementing the Manhattan Heuristic for sliding tiles.

1mark for having the correct table forEightPuzzle

21marks for implementing BubblePuzzle Class correctly

2 marks for implementing two BubblePuzzleHeuristics

3marks for a discussion of how greedy and A* compare as the heuristic gets better or the solution path gets longer. (this must be IN YOUR OWNWORDS)

1mark for extra for experts

The zip file can be found in the Assignment announcement.

The assignment must be submitted to Canvas. It will be run through Turnitin.

Copyright Warning Notice

Copyright © University of Auckland. This material is provided to you for your own use. You may not copy or distribute any part of this material to any other person. Failure to comply with this warning may expose you to legal action for copyright infringement and/or disciplinary action by the University.

合作平台：essay代写论文代写写手招聘英国留学生代写