Yioop - PHP Search Engine

Aug 31 In-Class Exercise Thread.

Please post your solution to the Aug 31 In-Class Exercise to this thread.

Best,

Chris

Please post your solution to the Aug 31 In-Class Exercise to this thread. Best, Chris

-- Aug 31 In-Class Exercise Thread

Initial Manhattan distance:

Tile	Dist
1	1
2	0
3	2
4	2
5	2
6	3
7	1
8	2

Total: 13

Moving 1

Tile	Dist
1	2
2	0
3	2
4	2
5	2
6	3
7	1
8	2

Total: 14

Moving 2

Tile	Dist
1	1
2	1
3	2
4	2
5	2
6	3
7	1
8	2

Total: 14

Moving 4:

Tile	Dist
1	1
2	0
3	2
4	1
5	2
6	3
7	1
8	2

Total: 12

Moving 7:

Tile	Dist
1	1
2	0
3	2
4	2
5	2
6	3
7	2
8	2

Total: 14

c(n) is 3 for all 4 moves.

A* costs

Moving 1: 14 + 3 = 17

Moving 2: 14 + 3 = 17

Moving 4: 12 + 3 = 15

Moving 7: 14 + 3 = 17

The cost is lowest if we move 4, so that is the move that would be chosen.

(Edited: 2022-08-31)

Initial Manhattan distance: {| |- | Tile || Dist |- | 1 || 1 |- | 2 || 0 |- | 3 || 2 |- | 4 || 2 |- | 5 || 2 |- | 6 || 3 |- | 7 || 1 |- | 8 || 2 |} Total: 13 Moving 1 {| |- | Tile || Dist |- | 1 || '''2''' |- | 2 || 0 |- | 3 || 2 |- | 4 || 2 |- | 5 || 2 |- | 6 || 3 |- | 7 || 1 |- | 8 || 2 |} Total: 14 Moving 2 {| |- | Tile || Dist |- | 1 || 1 |- | 2 || '''1''' |- | 3 || 2 |- | 4 || 2 |- | 5 || 2 |- | 6 || 3 |- | 7 || 1 |- | 8 || 2 |} Total: 14 Moving 4: {| |- | Tile || Dist |- | 1 || 1 |- | 2 || 0 |- | 3 || 2 |- | 4 || '''1''' |- | 5 || 2 |- | 6 || 3 |- | 7 || 1 |- | 8 || 2 |} Total: 12 Moving 7: {| |- | Tile || Dist |- | 1 || 1 |- | 2 || 0 |- | 3 || 2 |- | 4 || 2 |- | 5 || 2 |- | 6 || 3 |- | 7 || '''2''' |- | 8 || 2 |} Total: 14 c(n) is 3 for all 4 moves. A* costs Moving 1: 14 + 3 = 17 Moving 2: 14 + 3 = 17 Moving 4: 12 + 3 = 15 Moving 7: 14 + 3 = 17 The cost is lowest if we move 4, so that is the move that would be chosen.

-- Aug 31 In-Class Exercise Thread

Possible moves: 1, 2, 4, 7

Moving 1:

6 2 8

x 1 4

5 7 3

4 + 1 + 1 + 3 + 1 + 3 + 2 + 0 + 2 = 17

Moving 2:

6 x 8

1 2 4

5 7 3

4 + 2 + 2 + 3 + 1 + 3 + 2 + 0 + 2 = 19

Moving 4:

6 2 8

1 4 x

5 7 3

4 + 2 + 1 + 3 + 0 + 3 + 2 + 0 + 2 = 17

Moving 7:

6 2 8

1 7 4

5 x 3

4 + 2 + 1 + 3 + 1 + 3 + 2 + 1 + 2 = 19

Since the cost for moving 4 and 1 has the least, moving 4 or 1 will be chosen.

(Edited: 2022-08-31)

Possible moves: 1, 2, 4, 7 Moving 1: 6 2 8 x 1 4 5 7 3 4 + 1 + 1 + 3 + 1 + 3 + 2 + 0 + 2 = 17 Moving 2: 6 x 8 1 2 4 5 7 3 4 + 2 + 2 + 3 + 1 + 3 + 2 + 0 + 2 = 19 Moving 4: 6 2 8 1 4 x 5 7 3 4 + 2 + 1 + 3 + 0 + 3 + 2 + 0 + 2 = 17 Moving 7: 6 2 8 1 7 4 5 x 3 4 + 2 + 1 + 3 + 1 + 3 + 2 + 1 + 2 = 19 Since the cost for moving 4 and 1 has the least, moving 4 or 1 will be chosen.

-- Aug 31 In-Class Exercise Thread

According to the manhatten distance heurisitc and 8 puzzle on with initial state on top left The function is f = c + h. c = 4 for all. h is different.

                   c   1   6   2   8   4   5   7   3

For block 1, it is 4 + 1 + 2 + 1 + 2 + 1 + 3 + 0 + 3 = 17

                   c   2   6   8   1   4   5   7   3

For block 2, it is 4 + 2 + 2 + 2 + 2 + 1 + 3 + 0 + 3 = 19

                   c   4   6   2   8   1   5   7   3

For block 4, it is 4 + 0 + 2 + 1 + 2 + 2 + 3 + 0 + 3= 17

                   c   7   6   2   8   1   4   5   3

For block 7, it is 4 + 1 + 2 + 1 + 2 + 2 + 1 + 3 + 3 = 19,

We should therefore move block 1 according to A* algorithm

(Edited: 2022-08-31)

According to the manhatten distance heurisitc and 8 puzzle on with initial state on top left The function is f = c + h. c = 4 for all. h is different. c 1 6 2 8 4 5 7 3 For block 1, it is 4 + 1 + 2 + 1 + 2 + 1 + 3 + 0 + 3 = 17 c 2 6 8 1 4 5 7 3 For block 2, it is 4 + 2 + 2 + 2 + 2 + 1 + 3 + 0 + 3 = 19 c 4 6 2 8 1 5 7 3 For block 4, it is 4 + 0 + 2 + 1 + 2 + 2 + 3 + 0 + 3= 17 c 7 6 2 8 1 4 5 3 For block 7, it is 4 + 1 + 2 + 1 + 2 + 2 + 1 + 3 + 3 = 19, We should therefore move block 1 according to A* algorithm

-- Aug 31 In-Class Exercise Thread

 6 0 8
 1 2 4
 5 7 3

 6 2 8
 0 1 4
 5 7 3

 6 2 8
 1 4 0
 5 7 3

 6 2 8
 1 7 4
 5 0 3

The second move should be chosen cause the heuristic cost would be minimum as 0 and 1 are the closest from this

1+2+2+3+1+3+2+2=16+3= 19

1+1+1+3+1+3+2+2= 14+3= 17

3+2+1+3+3+2+2=16+3=19

3+2+1+3+1+3+2+1+2=18+3=21

(Edited: 2022-08-31)

6 0 8 1 2 4 5 7 3 6 2 8 0 1 4 5 7 3 6 2 8 1 4 0 5 7 3 6 2 8 1 7 4 5 0 3 The second move should be chosen cause the heuristic cost would be minimum as 0 and 1 are the closest from this 1+2+2+3+1+3+2+2=16+3= 19 1+1+1+3+1+3+2+2= 14+3= 17 3+2+1+3+3+2+2=16+3=19 3+2+1+3+1+3+2+1+2=18+3=21

-- Aug 31 In-Class Exercise Thread

Goal | Initial

0 1 2 | 6 2 8

3 4 5 | 1 0 4

6 7 8 | 5 7 3

Move 2:

6 0 8

1 2 4

5 7 3

h = 2 + 2 + 3 + 1 + 3 + 2 + 0 + 2 = 15 , c = 4 , f = 15 + 4 = 19

Move 1:

6 2 8

0 1 4

5 7 3

h = 1 + 1 + 3 + 1 + 3 + 2 + 0 + 2 = 13 , c = 4 , f = 13 + 4 = 17

Move 4:

6 2 8

1 4 0

5 7 3

h = 2 + 1 + 3 + 0 + 3 + 2 + 0 + 2 = 13 , c = 4 , f = 13 + 4 = 17

Move 7:

6 2 8

1 7 4

5 0 3

h = 2 + 1 + 3 + 1 + 3 + 2 + 1 + 2 = 15 , c = 4 , f = 15 + 4 = 19

(Edited: 2022-08-31)

'''Goal ''' | '''Initial''' 0 1 2 | 6 2 8 3 4 5 | 1 0 4 6 7 8 | 5 7 3 '''Move 2:''' 6 0 8 1 2 4 5 7 3 h = 2 + 2 + 3 + 1 + 3 + 2 + 0 + 2 = 15 , c = 4 , f = 15 + 4 = 19 '''Move 1:''' 6 2 8 0 1 4 5 7 3 h = 1 + 1 + 3 + 1 + 3 + 2 + 0 + 2 = 13 , c = 4 , f = 13 + 4 = 17 '''Move 4:''' 6 2 8 1 4 0 5 7 3 h = 2 + 1 + 3 + 0 + 3 + 2 + 0 + 2 = 13 , c = 4 , f = 13 + 4 = 17 '''Move 7:''' 6 2 8 1 7 4 5 0 3 h = 2 + 1 + 3 + 1 + 3 + 2 + 1 + 2 = 15 , c = 4 , f = 15 + 4 = 19

-- Aug 31 In-Class Exercise Thread

Possible Moves:

 -moving tile2 down into the center space
      -f() = c + h = (4 move) + (heuristic function) = 15
      -1 2 3 4 5 6 7
       1 1 2 2 2 3 1 = 11
 
 -moving tile1 right into the center space
      -f() = c + h = (4 move) + (heuristic function) = 16
      -1 2 3 4 5 6 7
       2 0 2 2 2 3 1 = 12
 
 -moving tile4 left into the center space
      -f() = c + h = (4 move) + (heuristic function) = 14
      -1 2 3 4 5 6 7
       1 0 2 1 2 3 1 = 10
 
 -moving tile7 up into the center space
      -f() = c + h = (4 move) + (heuristic function) = 16
      -1 2 3 4 5 6 7
       1 0 2 2 2 3 2 = 12
 
 -the correct move would be moving tile4

Possible Moves: -moving tile2 down into the center space -f() = c + h = (4 move) + (heuristic function) = 15 -1 2 3 4 5 6 7 1 1 2 2 2 3 1 = 11 -moving tile1 right into the center space -f() = c + h = (4 move) + (heuristic function) = 16 -1 2 3 4 5 6 7 2 0 2 2 2 3 1 = 12 -moving tile4 left into the center space -f() = c + h = (4 move) + (heuristic function) = 14 -1 2 3 4 5 6 7 1 0 2 1 2 3 1 = 10 -moving tile7 up into the center space -f() = c + h = (4 move) + (heuristic function) = 16 -1 2 3 4 5 6 7 1 0 2 2 2 3 2 = 12 -the correct move would be moving tile4

-- Aug 31 In-Class Exercise Thread

 c = 4

moving 2:

 6 0 8
 1 2 4 
 5 7 3

 h = 2+2+3+1+3+2+0+2 = 15
 f = 15 + 4 = 19

moving 4:

 6 2 8
 1 4 0 
 5 7 3

 h = 2+1+3+0+3+2+0+2 = 13
 f = 13 + 4 = 17

moving 7:

 6 2 8
 1 7 4 
 5 0 3

 h = 2+1+3+1+3+2+1+2 = 15
 f = 15 + 4 = 19

moving 1:

 6 2 8
 0 1 4 
 5 7 3

 h = 1+1+3+1+3+2+0+2 = 13
 f = 13 + 4 = 17

 We should move either 4 or 7 as they both have the same fitness cost of 17.

c = 4 moving 2: 6 0 8 1 2 4 5 7 3 h = 2+2+3+1+3+2+0+2 = 15 f = 15 + 4 = 19 moving 4: 6 2 8 1 4 0 5 7 3 h = 2+1+3+0+3+2+0+2 = 13 f = 13 + 4 = 17 moving 7: 6 2 8 1 7 4 5 0 3 h = 2+1+3+1+3+2+1+2 = 15 f = 15 + 4 = 19 moving 1: 6 2 8 0 1 4 5 7 3 h = 1+1+3+1+3+2+0+2 = 13 f = 13 + 4 = 17 We should move either 4 or 7 as they both have the same fitness cost of 17.

-- Aug 31 In-Class Exercise Thread

the goal of this puzzle.

1 2 3

4 - 5

6 7 8

2 moves to the target location at the lowest cost. Since 2 does not move after 3 moves, the cost is 3.

f = c + h

1. 3+1=4

2. 3+0=3

4. 3+2=5

7. 3+1=4

(Edited: 2022-08-31)

the goal of this puzzle. 1 2 3 4 - 5 6 7 8 2 moves to the target location at the lowest cost. Since 2 does not move after 3 moves, the cost is 3. f = c + h 1. 3+1=4 2. 3+0=3 4. 3+2=5 7. 3+1=4

-- Aug 31 In-Class Exercise Thread

The four possible moves that can be done is moving 1, 2, 4, and 7. We have a previous cost of 3.

1: 3 + 1 + 1 + 3 + 1 + 3 + 2 + 0 + 2 + 1 = 17

2: 3 + 2 + 2 + 3 + 1 + 3 + 2 + 0 + 2 + 1 = 19

4: 3 + 2 + 1 + 3 + 0 + 3 + 2 + 0 + 2 + 1 = 17

7: 3 + 2 + 1 + 3 + 1 + 3 + 2 + 1 + 2 + 1 = 19

The move that would be chosen is 1 or 4

(Edited: 2022-08-31)

The four possible moves that can be done is moving 1, 2, 4, and 7. We have a previous cost of 3. 1: 3 + 1 + 1 + 3 + 1 + 3 + 2 + 0 + 2 + 1 = 17 2: 3 + 2 + 2 + 3 + 1 + 3 + 2 + 0 + 2 + 1 = 19 4: 3 + 2 + 1 + 3 + 0 + 3 + 2 + 0 + 2 + 1 = 17 7: 3 + 2 + 1 + 3 + 1 + 3 + 2 + 1 + 2 + 1 = 19 The move that would be chosen is 1 or 4