Figure 4.8 -- The Eight Puzzle Table
- I have a couple questions about Figure 4.8, which shows the search cost of
the A* algorithm for the Eight-Puzzle problem.
First, what is search cost? In the text, it says that "Figure 4.8 gives
the average number of nodes expanded". However, the search cost for both
heuristicsfor problems with solutions of length 2 is 6. For both
heuristics, the number of nodes that the expand function is called on
should always be 2 for such problems. There should be an average of 6
nodes generated for such problems, the ~3 children of the start node and
the ~3 children of the node and the ~3 children of the node whose state is
one away from the goal. I'd guess that the table actually shows the
number of nodes generated, i.e. number of nodes expanded plus the number
of nodes in the queue.
Second, how were the random problems generated? I have found that the
number of nodes generated increases with the solution length faster than
the numbers in the table. My results were
d Nodes generated Nodes expanded
A*(h1) A*(h2) A*(h1) A*(h2)
2: 6.020000 5.800000 2.000000 2.000000
4: 11.720000 11.620000 4.020000 4.000000
6: 24.690000 18.130000 8.490000 6.290000
8: 55.240000 28.870000 19.610000 10.310000
10: 207.230000 88.260000 74.050000 32.220000
12: 1849.293333 171.324675 661.666667 62.662338
[Note that d = 12 was done with 75 and 79 tests, not 100]. For high d,
these numbers do not compare to those in the table. For the table, is the
*minimum* solution length of a problem with solution length d actually d?
Has anyone been able to replicate these results?
On Fri, 16 Jan 2004, Kristin Mara BRANSON wrote:
> Date: Fri, 16 Jan 2004 09:02:05 -0800 (PST)
> From: Kristin Mara BRANSON <kbranson@...>
> To: Charles Elkan <elkan@...>
> Cc: Piotr DOLLAR <pdollar@...>, Anjum GUPTA <a3gupta@...>
> Subject: search cost = number of nodes expanded?
> 1 Shown 46 lines Text
> 2 31 KB Application, ""
> Although the text says "Figure 4.8 gives the number of nodes expanded", it
> says that the average search cost for problems with solution length 2 is
> 6. Using either of the two heuristics, you should always expand 2 nodes
> when the solution length is 2. You should, however, have generated
> somewhere around 6 nodes: the ~3 children of the start node, and the ~3
> children of the node whose state is one away from the goal. I'd guess
> that the table actually shows the number of nodes generated.
> Do you know of any students who have actually got numbers near those in
> the table? I don't totally trust it. I implemented the eight puzzle
> stuff this morning, and my numbers grow faster than those in the table:
> d Nodes generated Nodes expanded
> A*(h1) A*(h2) A*(h1) A*(h2)
> 2: 6.020000 5.800000 2.000000 2.000000
> 4: 11.720000 11.620000 4.020000 4.000000
> 6: 24.690000 18.130000 8.490000 6.290000
> 8: 55.240000 28.870000 19.610000 10.310000
> 10: 207.230000 88.260000 74.050000 32.220000
> 12: 1849.293333 171.324675 661.666667 62.662338
> Note that d = 12 was done with 75 and 79 tests, not 100. I'm not
> guaranteeing that my code is correct, since I wrote it rather fast, but I
> am wondering if maybe the numbers in the book are generated from problems
> that had a solution of length d, but might have had a solution of d' < d
> (i.e. they started from the goal configuration and moved the tiles d times
> randomly, or something a bit smarter than randomly). I also have a very
> high variance for the search cost for high d. Here are the variances for
> h1 and nodes generated:
> 2: 1.009697
> 4: 0.789495
> 6: 100.902929
> 8: 1006.527677
> 10: 38149.128384
> 12: 9082827.318198
> Most d = 12 problems that are easy but a few are hard. Maybe they only
> used easy ones?
> I'll let you know if I notice a bug in my code, but otherwise let me know
> if you find anyone who was actually able to reproduce the table, pref
> before section today.
> If any of you want to play with my messy, slow code, I attached it.
> There are 2 .mat files with the results. the variables save_nodes_* have
> the results summarized in the table.
> [ Part 2, "" Application/OCTET-STREAM (Name: "kristins_astar.tar") ]
> [ 42KB. ]
> [ Cannot display this part. Press "V" then "S" to save in a file. ]