Mark: 13 revision(s)

2008-11-03T05:20:49Z

13 revision(s)

New page

== Q1 ==

Number of states is 9 factorial

9! = 362880

The edges represent the number of states which branch off a certain state.

If the empty space is at a corner, for each of those 4 states there are 2 possible "next" states.

If the empty space is at one of the sides, for each of those 4 states there are 3 possible "next" states.

If the empty space is in the middle, for that single state there are 4 possible "next" states.

The average number of "next" states for any state is
<Pre> 4/9 * 2 + 4/9 * 3 + 1/9 * 4 = 2.67</Pre>

Taking 2.67 * 9! and dividing by 2 because each edge is being counted from both sides(states)

number of edges = 483840
== Q2 ==

- Start and finish states are initialised

- Initialise a StateList containing the solution??

- Run the search function, if successful then print out the StateList solution, otherwise print out "Cannot solve"

- Print out the number of "moves made"

- Free the memory used by StateList

== Q3 ==

Wasn't sure if states could go back to a previous state. ie. have two edges leading to the same state

Asked Mark, he said I was dumb and the edges would override eachother.

The first state will have 2 edges, as the empty space is in the corner.

I tried the graph.c but it gave an error. Then I used rwan064's fix from lab 8

The graph drawn was a huge tree

I changed the code

<Pre>graph_state( &s, 7, "x.jpg" );
init_State( &s, "12345678." );</Pre>
to
<Pre> init_State( &s, "123456.78" );
graph_state( &s, 2, "x.jpg" );</Pre>

<html>
<img src="http://studwww.cs.auckland.ac.nz/~tlou006/x.jpg" width="500" height="500" alt="Tom's Task 3 Image" />
</html>

== Q4 ==

== Q5 ==

== Q6 ==

What i understood from the question, we want to search through the entire length(height) of a branch before starting on the next branch beside it??

in the search function

<Pre>int i, n_children;
State* cs = get_children( &s, &n_children );
for( i = 0; i < n_children; i++ )
if( add_to_StateSet( &visited, &cs[ i ] ) ) {
/* we have not yet seen this state */
put_StateMap( &path_map, &cs[ i ], &s );
add_to_OrderedStateList( &open, &cs[ i ] );
}
</Pre>

Take the last state off the list and read it.

Set that state as the current state, for each of the current state's children, if we have not visited this children state then add it to the StateList.

For each of the "current state"'s children we want to add each of the children's children to the list BEFORE adding the next children to the list and reading the next "current state"

That made no sense.

<Pre>int i, n_children;
State* cs = get_children( &s, &n_children );
for( i = 0; i < n_children; i++ )
if( add_to_StateSet( &visited, &cs[ i ] ) ) {
/* we have not yet seen this state */
put_StateMap( &path_map, &cs[ i ], &s );
add_to_OrderedStateList( &open, &cs[ i ] );
}
</Pre>

I think we need to repeat the for loop but setting State* cs = to &cs[ i ]

ie. the ith child of the "current state" we are looking at

We want to do this before i increments??

== Q7 ==

== Q8 ==

== Q9 ==

== Q10 ==

SE250:lab-X:tlou006 - Revision history

Mark: 13 revision(s)