Artificial Intelligence
Fall 2003

Homework Webpage

HW-01: Exercise 2.5 (See Textbook)

HW-02: Implementation of Greedy and A* Search  for the 8-puzzle problems.
              

Requirements:

1. Design a heuristic function and try out it in addition to those mentioned in the textbook.

2. Generate two best and completely distinct path sequences to the goal state for both algorithms.

3. Compare the search results of both algorithms in terms of path costs and effective branching factors.

4. Briefly explain your programming approach.

　

HW-03: Exercise 5.7 Map Coloring (See Textbook)

There are two exemplars of test sets proved by 黃立德 and 趙義雄. Thank them both!

Benchmark 1: Exemplar provided by   黃立德

    隨機產生的地圖，其地圖大小為100 * 100，內含50個nodes，如圖(經著色後)。



圖中nodes資訊如下說明：
       node_id x y cnt_number cnt_node_1 cnt_node_2 ... cnt_node_
       裡面每一行的格式為上所列，其中node_id為每一個node的編號，
       x和y為此node的座標(大小在100 * 100以內），cnt_number為此node連接
      其他nodes的數目，cnt_node_n 為此node連接的其他nodes之node_id。
      例如：
      0 80 23 5 21 29 33 42 44
      其表示它是第0號node，座標為(80,23)，總共連接5個其他nodes，分別為21,29,33,42,44。
   全部50 nodes資訊：

0 80 23 5 21 29 33 42 44
1 59 78 6 4 16 23 24 26 49
2 7 24 5 9 25 37 38 45
3 44 11 6 5 11 19 30 34 42
4 76 90 4 1 24 26 46
5 45 19 7 3 8 9 10 30 34 38
6 98 43 3 14 22 36
7 73 34 4 15 21 33 41
8 55 23 4 5 10 32 34
9 37 40 7 2 5 10 13 25 38 43
10 60 29 6 5 8 9 13 27 32
11 32 4 5 3 19 30 37 45
12 7 95 3 17 18 47
13 58 47 7 9 10 15 16 27 43 49
14 97 60 7 6 15 16 24 36 41 46
15 71 42 7 7 13 14 16 21 27 41
16 63 74 6 1 13 14 15 24 49
17 29 97 5 12 23 26 31 47
18 2 89 6 12 20 25 39 40 47
19 40 5 4 3 11 37 42
20 20 76 6 18 28 39 40 47 48
21 71 28 7 0 7 15 27 29 32 33
22 95 27 5 6 33 35 36 44
23 35 93 7 1 17 26 28 31 48 49
24 85 76 5 1 4 14 16 46
25 4 55 5 2 9 18 40 43
26 66 92 5 1 4 17 23 46
27 64 29 5 10 13 15 21 32
28 31 91 5 20 23 31 47 48
29 74 24 4 0 21 32 42
30 42 16 5 3 5 11 38 45
31 26 93 4 17 23 28 47
32 60 18 7 8 10 21 27 29 34 42
33 83 31 7 0 7 21 22 36 41 44
34 52 15 5 3 5 8 32 42
35 92 24 3 22 42 44
36 85 35 5 6 14 22 33 41
37 33 2 5 2 11 19 42 45
38 21 29 5 2 5 9 30 45
39 15 78 3 18 20 40
40 21 69 6 18 20 25 39 43 48
41 83 37 5 7 14 15 33 36
42 61 10 9 0 3 19 29 32 34 35 37 44
43 36 56 6 9 13 25 40 48 49
44 87 23 5 0 22 33 35 42
45 22 17 5 2 11 30 37 38
46 88 89 4 4 14 24 26
47 17 92 6 12 17 18 20 28 31
48 30 65 6 20 23 28 40 43 49
49 49 69 6 1 13 16 23 43 48

Benchmark 2: Exemplar provided by   趙義雄
     隨機產生的地圖，其地圖大小為100 * 100，內含50個nodes。
   
    圖中nodes資訊如下說明：
       The same as the preceding description.

   全部50 nodes資訊：

0 45 19 4 45 36 13 40
1 17 24 6 7 25 37 28 20 4
2 40 15 5 17 36 42 10 13
3 44 32 2 30 45
4 19 26 9 47 42 14 31 28 34 33 20 1
5 21 7 5 11 24 37 42 31
6 8 32 6 43 15 7 28 34 49
7 5 20 8 27 1 6 49 24 28 25 43
8 41 32 6 19 9 45 44 23 30
9 45 29 4 19 8 40 45
10 35 14 4 42 13 11 2
11 39 9 4 5 42 13 10
12 26 42 3 18 41 46
13 42 12 5 36 0 10 11 2
14 26 34 6 4 47 18 26 33 32
15 10 42 6 49 6 34 38 48 27
16 35 48 4 46 22 35 29
17 35 25 6 2 42 36 44 19 47
18 27 38 8 38 46 41 33 14 12 26 32
19 37 25 6 9 8 44 40 36 17
20 18 20 4 37 4 1 31
21 44 42 3 45 22 39
22 41 45 4 29 21 16 39
23 38 31 5 30 47 8 26 44
24 6 12 4 5 7 25 37
25 10 18 4 1 24 7 37
26 33 37 8 30 41 39 47 14 23 18 32
27 7 43 4 7 49 15 48
28 11 24 6 34 4 6 7 1 43
29 34 46 5 35 39 41 22 16
30 42 34 6 26 39 23 3 8 45
31 19 16 5 42 4 37 5 20
32 28 35 3 26 18 14
33 18 33 5 38 18 14 4 34
34 15 33 6 28 15 38 4 6 33
35 30 48 4 29 46 16 41
36 41 23 6 2 13 17 0 19 40
37 13 15 6 1 5 20 31 24 25
38 13 46 6 18 33 34 15 46 48
39 40 41 7 45 41 29 30 26 21 22
40 44 22 5 45 9 19 0 36
41 27 48 7 39 26 18 29 12 35 46
42 28 15 8 4 47 2 11 17 31 10 5
43 7 22 3 6 28 7
44 38 29 5 19 17 8 23 47
45 46 30 8 0 21 39 40 8 30 9 3
46 21 49 7 16 18 48 35 12 38 41
47 32 29 7 4 42 14 26 23 44 17
48 10 49 4 46 15 27 38
49 7 29 4 27 15 7 6

Results :

          1. Results provided by   黃立德

           2. Results provided by   趙義雄