Assignment 1 - my thoughts

Just like to share my thoughts - If you have inputs - please share - i'd appreciate!

Q1: Just wondering about the definition of a Search Node, cant find the formal definition anywhere. However I would assume it is a node within the search tree corresponding to a state in the environment.

Q2:
a) Mathematical notation? Are there good examples of how to formulate this? The state space contains all reachable states (by sequence of actions): How do you define the statespace mathematical notation if you need to include states, actions and the transitional model?

b) Successor function - how much detail should we provide here? The successor returns the next state based on the current state / function. Thus result := GetSuccessor(aCurrentState, aAction);. This seems to trivial... should we be providing the body of the function in pseudo code as well..?

Question 3:
My understanding: In order to spend as little time as possible, we need to handle the people that have a long waiting time as little as possible. Meaning: we need to take them across only once. This means that the optimal solution would be to take someone across together with D. D will serve as the main torch carrier - as we will always wait only 1 minute / unit when returning across the bridge to the LEFT. Hence D takes someone (X) across at the cost of X and returns at a cost of 1. Then he takes someone new across (Y) at the cost of Y, and returns at a minimal cost of 1. We use D as the torch carrier as any other person would cost more on the return trip. This also results in all other people (A,B,C) to make the trip only once and thus their cost being minimal. The optimal path would be D&A go right, D goes Left, D&B go right, D goes left, D and C go right. Thus total minimal cost = 10 + 5 + 2 + (1 + 1) = 19.

Now, when we need to graphically represent the state space, there a a multitide of sequencial states - in actual fact I think 108 distinct states (using nCr x nCr x nCr etc etc). I assume we only need tod rsaw the first 2 -3 levels of this state space diagram. Your thoughts..

Many thanks.

Danie

Danie van Eeden
------------------------

Regading the checking of duplicate states in question 3:

No, states will never be repeated. Initial State will contain 4 people on the LEFT, of which 2 will move RIGHT. Only one of these two will return left, leaving 1 RIGHT and 3 LEFT. Now we move two more people right (leaving 3 on the right and 1 on the left). There after we move one person LEFT, leaving two people on both sides. No single state ever repeats - due to us forcing 2 people to move RIGHT and only 1 to return LEFT. If we had allowed the REVERSE of any of these moves, we would have to have checked for duplicate states.

Danie van Eeden
------------------------

Q1:
I came to the same conclusion, not really that clearly said in the book...

Q2:
a) I spent a long time on the same 'mathematical' statement, but if you read chap 3 the bulleted list is also referred to as a mathematical notation, I could be completely wrong
b) I wrote one in the same form as the book for the specific state space

Q3:
Just a quick observation, your Q3 solution is not optimal, it can be done in 17 minutes ...

vinkman100,

thx for the reply. Helps to get some insight from others.
a) I'll check again in chp3 for the bulleted list.
b) on q3, I'll seriously take a look again.. 17 steps you say... mmm.. (my thoughts are you need to go right 3 times and left 2 two times - the cheapest way to go left is by using D (1 minute), and every other still needs to go right (thus A + B + C). but I'll look again.

Danie van Eeden
------------------------

For Q3, the obvious solution is to shuttle the D guy back and forth but in fact that is not the most optimal solution... it has to do with the two slow pokes, have them go together...

mmm. yeah. got it.

Danie van Eeden
------------------------

Hi , me again. got some other thoughts / questions - if anyone is willing to discuss

Q3 - 1a -- Says to define a state using some notation - should this not be "define a statespace". If so, I think it would be ok if we drew only the first 3 levels or so, else it might become fairly big

Q4: Is an optimal algorithm efficient? If it is optimal, it will find the best cost path.. Like for instance A* which is optimal of the cost function is non decreasing. Thus if optimal, surely it must be efficient. What else could efficient mean? OR perhaps: efficiency has to do with the number of states visited? true?

Danie van Eeden
------------------------

It seems to me like for question 2 b was asked straight out of the second edition of the textbook.
I have a copy of the second and third editions and, while the third editions has a mention, the
second edition actually has a definition for the term, "successor function"

Wow... and they specifically say we need the 3rd edition!!! I had to make up my own definition...

I noticed some smallprint (footnote) on Successor Functions in the third edition (some page on the right, way down at the bottom), but that was about all.

Danie van Eeden
------------------------

Handy summary

http://www.cs.trincoll.edu/~ram/cpsc352/notes/search.html