This graph contains six vertices and ten edges. An example of a shortest path through this graph is that from vertex 2 to vertex 8.
Starting vertex: 2
Ending vertex: 8
Shortest path:
Vertex 2 to vertex 13 (edge weight of 3)
Vertex 13 to vertex 5 (edge weight of 4)
Vertex 5 to vertex 8 (edge weight of 5)
Total weight: 12
Note that the shortest path in this case was not the path with the fewest edges, but the least total edge weight. For instance, there is an edge that directly connects vertices 2 and 8, but this edge has a weight of 16, which means it is not the shortest path. There is also another path (from 2-13-1-8), but this has an even greater total weight of 35.
This graph contains ten vertices and seventeen edges. Two examples of shortest paths through this graph are as follows.
Total weight: 28
There are other paths that have greater total weights (such as from 0-8-3-2-15-1-6 with weight 29 and 0-8-3-2-1-6 with weight 36).
Total weight: 19
There are numerous other paths (I counted seven) between these vertices, but this path is the shortest, and coincidentally, the most direct.
In this assignment, the blank space is represented by the number 0. A convenient way to consider the steps to the solution is the apparent movement of the blank space as pieces are moved; this metaphor will be provided as one interpretation of the solution here. The solutions to the puzzles that are shown here were generated using a search algorithm.
.
The text file for this puzzle can be found here. (Hold down shift and click to save)
The solution to this puzzle takes six moves. First, the two is moved up, the six is moved left, the five is moved down, the four is moved down, the three is moved right, and the two is moved up. If you consider that the space is moving, its moves are: down, right, up, up, left, down.
The intermediate states with the movement of the space look like this:
Current board layout: ._______. | 1 3 4 | "FIRST, from here, move DOWN." | 8 0 5 | | 7 2 6 | --------- Current board layout: ._______. | 1 3 4 | "SECOND, from here, move RIGHT." | 8 2 5 | | 7 0 6 | --------- Current board layout: ._______. | 1 3 4 | "THIRD, from here, move UP." | 8 2 5 | | 7 6 0 | --------- Current board layout: ._______. | 1 3 4 | "NEXT, from here, move UP." | 8 2 0 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 0 | "THEN, from here, move LEFT." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 0 3 | "THEN, from here, move DOWN." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 2 3 | "Done." | 8 0 4 | | 7 6 5 | --------- And thus we are finished, with path (D R U U L D).
.
The text file for this puzzle can be found here. (Hold down shift and click to save)
This puzzle also requires six moves to solve. These steps are to move the seven to the left, the six down, the two to the left, the four down, the three left, and the two up. The solution, in terms of the movement of the space, is thus right, up, right, up, left, down. The solution looks like this:
Current board layout: ._______. | 1 3 4 | "FIRST, from here, move RIGHT." | 8 6 2 | | 0 7 5 | --------- Current board layout: ._______. | 1 3 4 | "SECOND, from here, move UP." | 8 6 2 | | 7 0 5 | --------- Current board layout: ._______. | 1 3 4 | "THIRD, from here, move RIGHT." | 8 0 2 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 4 | "NEXT, from here, move UP." | 8 2 0 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 0 | "THEN, from here, move LEFT." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 0 3 | "THEN, from here, move DOWN." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 2 3 | "Done." | 8 0 4 | | 7 6 5 | --------- And thus we are finished, with path (R U R U L D).
.
The text file for this puzzle can be found here. (Hold down shift and click to save)
The solution to this puzzle requires 11 moves. These steps are to move the one left, the six down, the three right, the one up, the eight up, the seven left, the six down, the two left, the four down, the three right, and the two up. In terms of the movement of the space, the solution is: right, up, left, down, down, right, up, right, up, left, down. The solution is shown below.
Current board layout: ._______. | 3 6 4 | "FIRST, from here, move RIGHT." | 0 1 2 | | 8 7 5 | --------- Current board layout: ._______. | 3 6 4 | "SECOND, from here, move UP." | 1 0 2 | | 8 7 5 | --------- Current board layout: ._______. | 3 0 4 | "THIRD, from here, move LEFT." | 1 6 2 | | 8 7 5 | --------- Current board layout: ._______. | 0 3 4 | "NEXT, from here, move DOWN." | 1 6 2 | | 8 7 5 | --------- Current board layout: ._______. | 1 3 4 | "THEN, from here, move DOWN." | 0 6 2 | | 8 7 5 | --------- Current board layout: ._______. | 1 3 4 | "THEN, from here, move RIGHT." | 8 6 2 | | 0 7 5 | --------- Current board layout: ._______. | 1 3 4 | "THEN, from here, move UP." | 8 6 2 | | 7 0 5 | --------- Current board layout: ._______. | 1 3 4 | "THEN, from here, move RIGHT." | 8 0 2 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 4 | "THEN, from here, move UP." | 8 2 0 | | 7 6 5 | --------- Current board layout: ._______. | 1 3 0 | "THEN, from here, move LEFT." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 0 3 | "THEN, from here, move DOWN." | 8 2 4 | | 7 6 5 | --------- Current board layout: ._______. | 1 2 3 | "Done." | 8 0 4 | | 7 6 5 | --------- And thus we are finished, with path (R U L D D R U R U L D).
(hold Shift and click to save)
| Classification | How many made? | How old is coin? | How much wear is on the coin? |
| Positive | Rare | New | Low |
| Positive | Rare | Old | Low |
| Positive | Common | Old | Low |
| Negative | Rare | Old | High |
| Negative | Common | New | Low |
| Negative | Common | New | High |
From the above table, it should be apparent that the wear on the coin contains the most information for the first classification, as the value for wear is "low" in all of the positive cases. The actual information calculation looks like this:
First, I(p/(p+n), n/(p+n)) can be calculated as I(3/6, 3/6) = -0.5*lg(0.5) - 0.5*lg(0.5) = 1. For the case of I(1, 0) (where 0 is the logarithmic singularity), I() goes to zero.
Next, the gain from each attribute can be computed as:
| Gain(Rarity) = | 1 - [(3/6)*I(2/3, 1/3) + (3/6)*I(1/3, 2/3)] | = 0.0817 |
| Gain(Age) = | 1 - [(3/6)*I(2/3, 1/3) + (3/6)*I(1/3, 2/3)] | = 0.0817 |
| Gain(Wear) = | 1 - [(4/6)*I(3/4,1/4) + (2/6)*I(0,1)] | = 0.4591 |
As expected, we choose Wear to be the first branch of our decision tree. Since the test data both have high wear, they will be classified as Negative, meaning that they do not have much collector's value. The tree should branch again to handle any test cases that have a low wear attribute (using one of the remaining attributes); however, since there are no other possible data that are not already in the training or data sets, this will not be shown here. The next example will show that next step.
| Classification | Bind type | Style of book | Color pictures? | Is the book well known? | Length of book |
| Positive | Hardcover | Novel | Nocolor | Popular | Long |
| Positive | Softcover | Textbook | Nocolor | Popular | Long |
| Negative | Softcover | Novel | Nocolor | Popular | Short |
| Positive | Hardcover | Textbook | Color | Popular | Short |
| Positive | Hardcover | Photojournal | Color | Unknown | Short |
| Negative | Softcover | Textbook | Nocolor | Unknown | Short |
| Positive | Hardcover | Photojournal | Color | Popular | Long |
| Negative | Softcover | Novel | Color | Unknown | Short |
The calculation of the gain from each attribute is just as it was above. First, I(p/(p+n), n/(p+n)) can be computed as -(5/8)*lg(5/8) - (3/8)*lg(3/8) = 0.954434
Next, each the gain from each attribute can be computed:
| Gain(Bind) = | 0.954434 - [(4/8)*I(1, 0) + (4/8)*I(3/4, 1/4)] | = 0.54879494 |
| Gain(Style) = | 0.954434 - [(3/8)*I(1/3, 2/3) + (3/8)*I(2/3, 1/3) + (2/8)*I(1, 0)] | = 0.265712 |
| Gain(Color) = | 0.954434 - [(4/8)*I(2/4, 2/4) + (4/8)*I(3/4, 1/4)] | = 0.04879494 |
| Gain(Popularity) = | 0.954434 - [(5/8)*I(4/5, 1/5) + (3/8)*I(1/3, 2/3)] | = 0.158868 |
| Gain(Length) = | 0.954434 - [(3/8)*I(1, 0) + (5/8)*I(2/5, 3/5)] | = 0.34758988139 |
Based on these computed gains for each attribute, the bind is chosen as the first branch in the decision tree. Looking at the training data, a hardcover binding always leads to a Positive classification. To deal with the remaining softcover cases, we must eliminate the hardcover cases and start over.
| Classification | Bind type | Style of book | Color pictures? | Is the book well known? | Length of book |
| Positive | Softcover | Textbook | Nocolor | Popular | Long |
| Negative | Softcover | Novel | Nocolor | Popular | Short |
| Negative | Softcover | Textbook | Nocolor | Unknown | Short |
| Negative | Softcover | Novel | Color | Unknown | Short |
Here, I(p/(p+n), n/(p+n)) = -(1/4)*lg(1/4) - (3/4)*lg(3/4) = 0.8112781
As above, the gains for the remaining attributes is computed:
| Gain(Style) = | 0.8112781 - [(2/4)*I(1/2, 1/2) + (2/4)*I(0, 1)] | = 0.3112781 |
| Gain(Color) = | 0.8112781 - [(3/4)*I(2/3, 1/3) + (1/4)*I(0, 1)] | = 0.1225562 |
| Gain(Popularity) = | 0.8112781 - [(2/4)*I(1/2, 1/2) + (2/4)*I(0, 1)] | = 0.3112781 |
| Gain(Length) = | 0.8112781 - [(1/4)*I(1, 0) + (3/4)*I(0, 1)] | = 0.8112781 |
From these new gains, it should be obvious that the length of the book is the next branch in our tree. As it turns out, out of all of the training data, short books get a negative classification and long books get a positive classification. Since all data are classified at this level, no further decision branches are needed. If there were any cases that were not categorized by this tree, then this process would repeat.
Now, consider the test data:
| Softcover | Photojournal | Color | Popular | Short |
| Hardcover | Novel | Nocolor | Unknown | Long |
| Hardcover | Textbook | Nocolor | Unknown | Long |
The first book, as a softcover, will be categorized by its length. Since it is short, its classification will be negative. The second and third books, as hardcovers, will have positive classifications.
Click here (shift and click to save) for a sample text file that contains training and test data for the negated conjunction function. This file contains six training sets and three test sets, one of which is identical to an element of the training set.
The test data from this file are:
1 0 0, which should trigger an output of 1,
1 1 1, which should trigger an output of 0,
0 0 1, which should trigger an output of 1.
Click here (shift and click to save) for a sample text file that contains training and test data for the disjunction function. This file contains five training sets and three test sets, one of which is identical to an element of the training set.
The test data from this file are:
1 0 1, which should trigger an output of 1,
0 0 0, which should trigger an output of 0,
1 1 1, which should trigger an output of 1.