人工智能代写: COMP-3703 Homework #4: Paern Databases

Homework #4: Paern Databases

Due Monday by 11:59pm Points 100 Submitting a file upload Available after Apr 16 at 11:59pm

HW #4
Due April 23, 2018 at 11:59pm

For this assignment, undergraduates may work in teams with up to one other student, while graduate students must work individually. You can discuss the assignment with other students in thinking about how to solve these problems, but all programming and other portions of the assignment must be entirely your own work. You may not show your code to other students. If you are working with another student, you need to designate this by forming a group in Canvas.

Task:

In this assignment you will implement two pattern databases for the 3×5 sliding­tile puzzle. Pattern Databases:
You should build pattern databases containing the following tiles:

a) 0 1 2 3 4 5 (3,603,600 entries)

b) 0 9 10 11 12 13 14 (32,432,400 entries)

Undergraduates can hard­code these patterns into the PDB code and ranking function. Graduate students should write code that takes any pattern as input for building the pdb.

Your PDB should store its values as an array/vector of 8­bit values. To build the PDB, do a breadth­first search from the goal state. Compute the (abstract) rank of a state to store its depth in the PDB. If you generate a state in the BFS which is already in the PDB you should discard the state to avoid generating states multiple times.

Ranking/Unranking:

Use a lexicographical ranking and unranking function (as described in class). To compute the abstract rank you must:

1) Compute the dual of the pattern
2) Compute the mixed­radix value of the pattern 3) Compute the rank of the mixed­radix pattern

Note that a naive implementation of step 1 takes O(n^2) time, while a smarter implementation (which computes the location of each tile first) will only take O(n) time.

Testing:

Test your code on the 20 test instances from homework three. Compare the time and number of nodes

expanded using:

Only Manhattan distance
The max of Manhattan distance and the PDBs

What to turn in:

1 person online 

New message alerts

Your submission should include all code written for the assignment. Along with the code also submit a run of your program that tests on all instances. Graduate students should also include a formal writeup that provides the experimental results in tables and explains the pattern databases and final results.

Verifying Correctness:

If you print the distribution of depths in your PDBs, you should get the following results:

PDB complete; 3603600 of 3603600 entries written PDB Distribution
0 :1
1 :2

2 :4
3 :9
4 : 20
5 : 32
6 : 53
7 : 78
8 : 140
9 : 215
10 : 383
11 : 572
12 : 994
13 : 1487 14 : 2551 15 : 3662 16 : 6083 17 : 8412 18 : 13285 19 : 17198 20 : 25715 21 : 31361 22 : 44669 23 : 51069 24 : 69998 25 : 76509 26 : 102351 27 : 108545 28 : 142635 29 : 146533 30 : 187956 31 : 184448

Send

29 : 520655
30 : 720291
31 : 789805
32 : 1062662
33 : 1117571
34 : 1453505
35 : 1457091
36 : 1820909
37 : 1730218
38 : 2067704
39 : 1863445
40 : 2138225
41 : 1833591
42 : 2021831
43 : 1644785
44 : 1735078
45 : 1331858
46 : 1337673
47 : 963259
48 : 915737
49 : 614432
50 : 551891
51 : 343792
52 : 291498
53 : 167802
54 : 133293
55 : 68521
56 : 49397
57 : 21711
58 : 13909
59 : 4827

60 : 2605
61 : 508
62 : 252
63 : 22
64 : 14

1 person online 

New message alerts

Send

File Upload

Google Doc

Upload a file, or choose a file you’ve already uploaded.

File:

No file chosen

 Add Another File
Click here to find a file you’ve already uploaded

Comments…

All comments are sent to the whole group.