COMPARISON OF THE VARIOUS METHODS : Tiles in Place : --------------- -------------------------------------------------- | Initial |Solution |Total |Graph | Nodes |CPU | | State | Moves |Moves |Depth |Expnded |Time | -------------------------------------------------- | | | | | | | |*sample1*| 12 | 127 | 12 | 72 |28.1 | | | | | | | | |*sample2*| 4 | 7 | 4 | 4 | 1.0 | | | | | | | | |*sample3*| 8 | 13 | 8 | 8 | 1.7 | | | | | | | | -------------------------------------------------- Manhattan Distance -------------------------------------------------- | | | | | | | |*sample1*| 12 | 29 | 12 | 16 | 4.1 | | | | | | | | |*sample2*| 4 | 7 | 4 | 4 | 0.9 | | | | | | | | |*sample3*| 8 | 13 | 8 | 8 | 2.2 | | | | | | | | -------------------------------------------------- Dumb Heuristic (Breadth First) -------------------------------------------------- | | | | | | | |*sample1*| 12 |1729 | 12 |1037 |80.9$| | | | | | | | |*sample2*| 4 | 24 | 4 | 12 | 0.1$| | | | | | | | |*sample3*| 8 | 224 | 8 | 128 |62.2 | | | | | | | | -------------------------------------------------- $ : Run on Andrew in compiled form to save time, hence time cannot be compared. Conclusions : Manhattan is better for *sample1* over tiles in place and same for others. I think Manhat -tan is better over all. Dumb shows poorer performance compared to either of the methods for all the problems. (set-tile-mode) TILES-PLACE-COST (time (a-star *sample1*)) Solution Found after trying 127 moves. Maximum graph depth searched reached is 12. Number of nodes expanded is 72. The solution takes 12 moves. +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 6 ! 7 ! 3 ! +---+---+---+ ! 4 ! 5 ! ! +---+---+---+ Move LEFT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 6 ! 7 ! 3 ! +---+---+---+ ! 4 ! ! 5 ! +---+---+---+ Move UP +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 6 ! ! 3 ! +---+---+---+ ! 4 ! 7 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! ! 6 ! 3 ! +---+---+---+ ! 4 ! 7 ! 5 ! +---+---+---+ Move DOWN +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 4 ! 6 ! 3 ! +---+---+---+ ! ! 7 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 4 ! 6 ! 3 ! +---+---+---+ ! 7 ! ! 5 ! +---+---+---+ Move UP +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 4 ! ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move UP +---+---+---+ ! ! 1 ! 2 ! +---+---+---+ ! 8 ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! ! 2 ! +---+---+---+ ! 8 ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! 2 ! ! +---+---+---+ ! 8 ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move DOWN +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! 4 ! ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ cpu time (non-gc) 22600 msec user, 967 msec system cpu time (gc) 1233 msec user, 67 msec system cpu time (total) 23833 msec user, 1034 msec system real time 45795 msec T *cost-mode* TILES-PLACE-COST (time (a-star *sample2*)) Solution Found after trying 7 moves. Maximum graph depth searched reached is 4. Number of nodes expanded is 4. The solution takes 4 moves. +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! 4 ! 5 ! +---+---+---+ ! ! 7 ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! 4 ! 5 ! +---+---+---+ ! 7 ! ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! 4 ! 5 ! +---+---+---+ ! 7 ! 6 ! ! +---+---+---+ Move UP +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! 4 ! ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ cpu time (non-gc) 967 msec user, 17 msec system cpu time (gc) 0 msec user, 0 msec system cpu time (total) 967 msec user, 17 msec system real time 1040 msec T *cost-mode* TILES-PLACE-COST (time (a-star *sample3*)) Solution Found after trying 13 moves. Maximum graph depth searched reached is 8. Number of nodes expanded is 8. The solution takes 8 moves. +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! ! 7 ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! 7 ! ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! 7 ! 6 ! ! +---+---+---+ Move UP +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move UP +---+---+---+ ! 2 ! 3 ! ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 2 ! ! 3 ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! ! 2 ! 3 ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move DOWN +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ cpu time (non-gc) 1733 msec user, 100 msec system cpu time (gc) 0 msec user, 0 msec system cpu time (total) 1733 msec user, 100 msec system real time 3270 msec T (set-dumb-mode) DUMB-COST (time (a-star *sample3*)) Solution Found after trying 224 moves. Maximum graph depth searched reached is 8. Number of nodes expanded is 128. The solution takes 8 moves. +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! ! 7 ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! 7 ! ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! 7 ! 6 ! ! +---+---+---+ Move UP +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move UP +---+---+---+ ! 2 ! 3 ! ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 2 ! ! 3 ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! ! 2 ! 3 ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move DOWN +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ cpu time (non-gc) 58083 msec user, 3668 msec system cpu time (gc) 4100 msec user, 66 msec system cpu time (total) 62183 msec user, 3734 msec system real time 82742 msec T *cost-mode* MANHATTAN-COST (time (a-star *sample3*)) Solution Found after trying 13 moves. Maximum graph depth searched reached is 8. Number of nodes expanded is 8. The solution takes 8 moves. +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! ! 7 ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! 7 ! ! 6 ! +---+---+---+ Move RIGHT +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! 5 ! +---+---+---+ ! 7 ! 6 ! ! +---+---+---+ Move UP +---+---+---+ ! 2 ! 3 ! 4 ! +---+---+---+ ! 1 ! 8 ! ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move UP +---+---+---+ ! 2 ! 3 ! ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 2 ! ! 3 ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! ! 2 ! 3 ! +---+---+---+ ! 1 ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move DOWN +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! ! 8 ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ cpu time (non-gc) 1883 msec user, 49 msec system cpu time (gc) 133 msec user, 34 msec system cpu time (total) 2016 msec user, 83 msec system real time 2210 msec T (set-manhattan-mode) MANHATTAN-COST (time (a-star *sample1*)) Solution Found after trying 29 moves. Maximum graph depth searched reached is 12. Number of nodes expanded is 16. The solution takes 12 moves. +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 6 ! 7 ! 3 ! +---+---+---+ ! 4 ! 5 ! ! +---+---+---+ Move LEFT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 6 ! 7 ! 3 ! +---+---+---+ ! 4 ! ! 5 ! +---+---+---+ Move UP +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 6 ! ! 3 ! +---+---+---+ ! 4 ! 7 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! ! 6 ! 3 ! +---+---+---+ ! 4 ! 7 ! 5 ! +---+---+---+ Move DOWN +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 4 ! 6 ! 3 ! +---+---+---+ ! ! 7 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 4 ! 6 ! 3 ! +---+---+---+ ! 7 ! ! 5 ! +---+---+---+ Move UP +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! 4 ! ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 8 ! 1 ! 2 ! +---+---+---+ ! ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move UP +---+---+---+ ! ! 1 ! 2 ! +---+---+---+ ! 8 ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! ! 2 ! +---+---+---+ ! 8 ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move RIGHT +---+---+---+ ! 1 ! 2 ! ! +---+---+---+ ! 8 ! 4 ! 3 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move DOWN +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! 4 ! ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ Move LEFT +---+---+---+ ! 1 ! 2 ! 3 ! +---+---+---+ ! 8 ! ! 4 ! +---+---+---+ ! 7 ! 6 ! 5 ! +---+---+---+ cpu time (non-gc) 4033 msec user, 233 msec system cpu time (gc) 117 msec user, 0 msec system cpu time (total) 4150 msec user, 233 msec system real time 6499 msec T