Welcome! Log In Create A New Profile

Advanced

Mock Exam Q3 (Francs and Pounds)

Posted by Sanoz0r 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Mock Exam Q3 (Francs and Pounds)
November 10, 2008 02:33PM
Hey

Here is my answer for question3. I'm not entirely sure if my queue orders are correct when f is the same amoungst nodes. Please check my answer!!

f(1) = g(1) + h(1) = 1 + 4 = 5
Open Queue = {1}

Expand node 1:
f(2) = g(2) + h(2) = 2 + 4 = 6
f(3) = g(3) + h(3) = 2 + 4 = 6
f(4) = g(4) + h(4) = 2 + 4 = 6
f(5) = g(5) + h(5) = 2 + 4 = 6
Open Queue = {2, 3, 4, 5}

Expand node 2:
No fringe

Expand node 3:
f(6) = g(6) + h(6) = 3 + 4 = 7
f(7) = g(7) + h(7) = 3 + 3 = 6
Open Queue = {7, 4, 5, 6}

Expand node 7:
f(10) = g(10) + h(10) = 4 + 2 = 6
f(11) = g(11) + h(11) = 4 + 3 = 7
Open Queue = {10, 4, 5, 11, 7}

Expand node 10:
Stop: Node with depth = 4 selected.

Cheers
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 10, 2008 02:34PM
Give the rest of us working crowd a break.....sad smiley
Re: Mock Exam Q3 (Francs and Pounds)
November 10, 2008 04:30PM
I got preety much the same thing @ San0zor...but what I found confusion in is what does A* do when two nodes on different or the same depths with the same or not the same parent have the same h(n) value???

Does it act like breadth-first or depth-first or what happens?
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 10, 2008 09:59PM
Good question. I think it would choose the first node.

BTW: a Heuristic is admissible, when it never overestimates the cost to reach the goal. (p97 prescribed text)
ll
Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 02:51AM
Hi Sanoz0r

After Expanding node 7, why do you still have 7 in your queue? Is there something I am not understanding perhaps? I would have thought that your queue would be without 7 since it is the node that we expanding, and we are more interested in the children of 7.

LLsad smiley
Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 11:05AM
Oops, you are right. It should be 6.

Expand node 7:
f(10) = g(10) + h(10) = 4 + 2 = 6
f(11) = g(11) + h(11) = 4 + 3 = 7
Open Queue = {10, 4, 5, 11, 6}
Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 03:16PM
Hey there SanozOr,tell me something.Is the depth of an initial state(i.e. Node 1) equal to 1 or equal to 0?With depth we are talking about levels right?
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 03:19PM
It shouls start at 0, but does it realy matter?
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 03:19PM
It should start at 0, but does it realy matter?
Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 03:26PM
Yeah, it should be 0... I remember there was a good reason why I chose 1 - can't for the life of me figure out why.
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 09:11PM
The question says to stop when depth 4 is reached. if you start at zero you will not reach 4 without adding states, wich you also may not do.
Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 09:27PM
Are you guys sure after expanding Node3 you would go to Node7? Shouldnt in the case of a tie the earlier nodes be expanded first? (breadth first)
Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 09:30PM
Yeah I read somewhere the new nodes will be placed in the priority queue after nodes with lesser or equal f(n) values. So I think it should be breadth first. Although I suppose if you specify your assumption the lecturer wont penalize you.
Re: Mock Exam Q3 (Francs and Pounds)
November 11, 2008 10:25PM
Christiaan Wrote:
-------------------------------------------------------
> Are you guys sure after expanding Node3 you would
> go to Node7? Shouldnt in the case of a tie the
> earlier nodes be expanded first? (breadth first)

Good question, I would also like to know the answer to this ...
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 09:20AM
Following the same A* as show  in 2007 tut 202 q7, you missed some nodes, mainly due to ordering of queue positions:

start: 			1[0+4=4]
expand 1(first in queue):	2[1+4=5],3[1+4=5],4[1+4=5],5[1+4=5]
expand 2(first in queue):	3[1+4=5],4[1+4=5],5[1+4=5]
expand 3(first in queue):	4[1+4=5],5[1+4=5] + 6[2+4=6],7[2+3=5]
	now order them by heuristic, then sequence added to get:
			4,5,7,6
expand 4(first in queue):	5[1+4=5],7[2+3=5],6[2+4=6] + 8[2+3=5],9[2+4=6]
	now order them by heuristic, then sequence added to get:
			5,6,8,6,9
expand 5(first in queue):	7,8,6,9
expand 7(first in queue):	8[2+3=5],6[2+4=6],9[2+4=6],10[3+2=5],11[3+3=6]
	new order:		8,10,6,9,11

Stop because first node at depth 4 has been reached
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 09:23AM
ps. to get a great graphical representation, go to applets and draw this tree. Select A* search and make sure you specify neighboring ordering strategies as "f function".
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 09:27AM
Yes, as christiaan mentioned it uses a priority queue. first 4, and 5 then 7.
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 09:34AM
4.2:
"When is a heuristic admissible":
A heuristic is admissible with respect to a search method if it guarantees finding the optimal solution first, even when its value is only an estimate.

Not sure how to answer "Why is an admissible heuristic required for A* search"
Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 09:38AM
Shot Liezl.

An admissible heuristic ensures that the A* search is optimal.
avatar Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 09:40AM
a Heuristic is admissible, when it never overestimates the cost to reach the goal. (p97 prescribed text)

If it overestimates the cost to reach the goal, the A* search will continue searching past a goal depth, and will waiste valueble time, and as such will not be optimal.
Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 12:01PM
Liezl-Mia, thanks for that nice explanation !

* edited * all text removed, mistake found.
Re: Mock Exam Q3 (Francs and Pounds)
November 12, 2008 12:03PM
Question:

"I just wanted to know what does A* do when two nodes on different or the same depths with the same or not the same parent have the same h(n) value?

Does it act like breadth-first or depth-first or what happens?"

Answer from the lecture:

"A* is a greedy BEST-FIRST search. The choice of node is determined by the sequence in which the elements of the Open and Closed sets are evaluated. It does not make sense to try and define A* in terms of breadth-first or depth-first, as they are in fact special cases of A*. For example, breadth-first search is the case where h(n)=0, i.e. f(n) = g(n) + 0. In this case the next "best" node is next node at the same depth"
Sorry, only registered users may post in this forum.

Click here to login