|
Post by stephan on Jan 22, 2013 8:28:24 GMT -5
This thread is for discussing the first programming assignment. Post the stats of your implementations here for comparison. Of course, you can also use this board to ask questions regarding the assignment and discuss any problems you might have with the assignment or the implementation.
|
|
|
Post by arnthorsnaer on Feb 6, 2013 5:18:26 GMT -5
Hi Stephan
Can you give us a hint as to how to keep track of the path to the goal state? The easiest solution to me seems to keep track of this information in the state itself, but that will affect our space complexity.
-A
|
|
|
Post by michael on Feb 9, 2013 18:55:38 GMT -5
You could use the decorator pattern, du attach the path-information to it. When doing so, make sure to implement the comperable-interface, that the PriorityQueue works. Clean One more class More work If you want to save your self from this "mess", you might just add it in the State-Class, but don't use it as a property to distinguish them (Don't check for equalness of the paths in the states equal-method). Simple No work Ugly hack Of course you could extend it via inherritance, too. But seriously, it won't bring you benefit over the second solution. Would be just for the fun of it, as so you can say: Here is my state, and here is how I use it. You can see, result in the same: You have a class with all the information about the state, and about the path. Why the first one would be the cleanest is, as so you do not need to argue, two objects with different content should be the same. ------------------ Other methods: Build a container for pairs of Key and Value without being in a set. (Like the C++-Pair-Class) It should implement the comparable-interface. Use the Path as Key, so to compare-method would need to use the path-length + the heuristic together - so it will be sorted well in the PriorityQueue for A* Otherwise use an Integer that is already the solution of heuristic+pathlength, and just compare this in the compare-method. So you need to aditionaly store the path. Do this in a HashMap<State, LinkedList<Action>> for example. I think I will use this solution, as it is at least as clear as the first one. If you want to hide the container, use it, together with the PriorityQueue to build your own PriorityQueue. Would look nicer, but is more work.
|
|
|
Post by stephan on Feb 11, 2013 4:58:37 GMT -5
Hi Stephan Can you give us a hint as to how to keep track of the path to the goal state? The easiest solution to me seems to keep track of this information in the state itself, but that will affect our space complexity. -A For the search algorithms you should have two data structures, one for states and one for nodes. The search algorithms search a tree of nodes. Each node has a reference to a state and some information about how you got to that node (e.g., a reference to the parent node and the action that was executed to get to the node). The node may also contain the path cost to it from the initial node, if you need the path costs. When you have found a goal node, you can simply follow the nodes backwards (using the parent references) to get the sequence of actions. You can in principle also keep the same information in the data structure for states, but that is not a clean solution and causes trouble when you try to discard nodes with repeated states. Note, that these are more or less the two solutions that Michael suggested, too. However, I would opt for the cleaner solution, because you should learn how to do it right before doing ugly hacks. If you use the stack-based version of DFS you don't need that. When you found a solution you could simply return the sequence of actions: List<Action> dfs(state) { if state.isGoal return emptyList foreach action in state.legalMoves() { list = dfs(state.nextState(action)) if (list != null) { list.insertAtFront(action) return list } } return null // no solution found here }
However this approach only works for DFS and not for BFS/A* and the like.
|
|
|
Post by gudni11 on Feb 11, 2013 10:20:58 GMT -5
einarss11, gudni11, jonao11 test results:
world 1: estimated goal cost: 61 ASearch ran in: 104 with 4071 expansions and maximum frontier size 447 and cost: 89 That is 42 moves
world 2: estimated goal cost: 71 ASearch ran in: 139 with 5296 expansions and maximum frontier size 305 and cost: 99 That is 46 moves
world 3: estimated goal cost: 5443 ASearch ran in: 1118 with 26128 expansions and maximum frontier size 738 and cost: 669 That is 312 moves
world 4: estimated goal cost: 5449 ASearch ran in: 441 with 14555 expansions and maximum frontier size 596 and cost: 449 That is 212 moves
world 5: estimated goal cost: 1420 ASearch ran in: 1202 with 24071 expansions and maximum frontier size 1016 and cost: 423 That is 202 moves
world 6: estimated goal cost: 1477 ASearch ran in: 346 with 12541 expansions and maximum frontier size 481 and cost: 370 That is 177 moves
world 7: estimated goal cost: 3696 ASearch ran in: 659 with 19617 expansions and maximum frontier size 513 and cost: 485 That is 228 moves
world 8: ASearch ran in: 1926 with 21308 expansions and maximum frontier size 578 and cost: 566 That is 265 moves
world 9: estimated goal cost: 4950 ASearch ran in: 2441 with 21436 expansions and maximum frontier size 628 and cost: 591 That is 276 moves
world 10: estimated goal cost: 5263 ASearch ran in: 1737 with 19432 expansions and maximum frontier size 629 and cost: 592 That is 277 moves
|
|
|
Post by Vojta Zrust on Feb 11, 2013 19:00:35 GMT -5
|
|
|
Post by Jan Straka on Feb 11, 2013 19:22:18 GMT -5
A* results: GAME1 search time: 405 max frontier size: 331 result cost: 43 number of expansions: 5807
GAME2 search time: 489 max frontier size: 340 result cost: 47 number of expansions: 5347
GAME3 search time: 122445 max frontier size: 58886 result cost: 287 number of expansions: 4592002
GAME4 search time: 254954 max frontier size: 158966 result cost: 203 number of expansions: 8639650
GAME5 search time: 186430 max frontier size: 113407 result cost: 171 number of expansions: 6105598
GAME6 no solution exists
GAME7 search time: 6249 max frontier size: 3974 result cost: 223 number of expansions: 306360
GAME8 search time: 11817 max frontier size: 7071 result cost: 260 number of expansions: 586530
GAME9 search time: 24515 max frontier size: 13952 result cost: 271 number of expansions: 1178576
GAME10 search time: 58798 max frontier size: 28791 result cost: 272 number of expansions: 2353708
|
|
|
Post by gunnarv11 on Feb 12, 2013 18:20:32 GMT -5
A* results: GAME1 search time: 0.363 s max frontier size: 1661 result cost: 42 number of expansions: 7152
GAME2 search time: 0.42 s max frontier size: 1697 result cost: 46 number of expansions: 7285
GAME3 search time: 100.563 s max frontier size: 1535902 result cost: 290 number of expansions: 7231972
GAME4 search time: 15.08 s max frontier size: 514268 result cost: 210 number of expansions: 2338789
GAME5 search time: 18.475 max frontier size: 619268 result cost: 174 number of expansions: 2822441
GAME6 no solution exists
GAME7 search time: 1.939 max frontier size: 79600 result cost: 222 number of expansions: 371134
GAME8 search time: 4.455 s max frontier size: 201729 result cost: 263 number of expansions: 951477
GAME9 search time: 9.278 s max frontier size: 1984023 result cost: 278 number of expansions: 1984023
GAME10 search time: 18.867 s max frontier size: 729494 result cost: 275 number of expansions: 3429951
|
|