Quantcast

Maximum PC

It is currently Fri Sep 19, 2014 6:54 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: A discussion about AI
PostPosted: Wed Feb 20, 2008 5:54 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
We don't really have a "theory section" and I don't think we should, because the PP isn't a horribly overrun section and it wouldn't hurt to keep them together... so I am going to start a thread on AI. On the homework that I just turned in lastnight, there was this question (With my answer) I am curious as to what everyone's thoughts are:

Q:Sometimes there is no good evaluation function for a problem, but there is a good comparison method: a way to tell whether one node is better than another, without assigning numerical values to either. Show that this is enough to do a best-first search. Is there an analog of A*?

A:The idea behind a best-first search is that it chooses each successor / child node based on some rule that defines which nodes are better than one another, typically a function f(n). As long as the comparison method provides a way to determine if one is better than another then a best-first search can be performed choosing each node in succession based on it being better than another. Due to A* being classified as a best-first search and there is a way to qualify a better node from a less ideal node; one could construct a function/method to track each paths overall status related to how “goodâ€


Top
  Profile  
 
 Post subject: Re: A discussion about AI
PostPosted: Fri Feb 22, 2008 2:09 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Not bad. You should probably scratch out a C with that answer. =)

Are you using the green someone and Norvig AI book? If so, which chapter and question number?

I should have some time on Saturday to get into it.


Top
  Profile  
 
 Post subject:
PostPosted: Fri Feb 22, 2008 6:57 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
http://aima.cs.berkeley.edu/

I think it was 4.12.

That wasn't the only one on the assignment. I will post my whole HW thing here (should be safe, it was due Wed, and he doesn't give partial credit/late credit...) 4.2, 4.3, 4.11, and the question above, 4.12. His biggest thing is mostly about demonstrating an understanding, after I talked to him... that seemed to be his biggest thing, even if our numbers/answers aren't quite right... although there isn't much in the way of partial credit, so either you get it or you don't.

4.2 wrote:
The heuristic path algorithm is a best-first search with the objective function: f(n)=(2-w)*g(n)+ w*h(n) For what values of w is this algorithm guaranteed to be optimal? What kind of search is performed for the following values for w?
w = 0 → f(n)=2*g(n)
w = 1 → f(n)=g(n)+ h(n)
w = 2 → f(n)=2*h(n)

This algorithm will be found to be optimal for any values of w that make the h(n) portion of the function negligible if it is not already admissible. If it is overestimating the distance from the goal it would be made optimal for w = 0. This happens because w = 0 removes h(n) from the decision function removing the effect of overestimating the distance. This also makes it most like a uniform-cost search, which is optimal by its definition. For w = 1 it will also be optimal provided that h(n) is admissible. If h(n) is admissible it will also be optimal for w = 2 as it is going to choose the nodes who are closest to the goal and the factor of two out in front will not change the order they are expanded in.

For w = 0 :: f(n)=2*g(n)
This removes the “estimated distance from the goalâ€


Top
  Profile  
 
 Post subject:
PostPosted: Tue Mar 11, 2008 9:04 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
I am dying to get into this... but life keeps throwing up road blocks... :\


Top
  Profile  
 
 Post subject:
PostPosted: Tue Mar 11, 2008 12:10 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24224
Location: Granite Heaven
Gadget wrote:
I am dying to get into this... but life keeps throwing up road blocks... :\


Ditto. :(

I love having great conversations in this folder, and I bitch about their absence when I have the time to participate. Then, when they pop up, I find I don't have time to contribute. :|

Sorry Crash ...


Top
  Profile  
 
 Post subject:
PostPosted: Fri Mar 14, 2008 11:01 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Jipstyle wrote:
Sorry Crash ...


Don't worry, this class has given me plenty of ammo. Fortunately, I figured out his trick, or at least a trick, to get a decent grade on the HW.

He is kind of stingy.

I have my A* in LISP written... :)


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group