Basic Search Methods $[19$ points$]$

$[$Warning: Facts and numbers used in the following problem are historically incorrect. Some

are pure $$ction$.$ Stick to the problem as formulated below, not to history$]$

Sergio Lopez was a rich ship owner living in Spain in the $17$th century. In $1650,$ one of his

ships was sunk in the Caribbean Sea with a huge cargo of gold. In $2008,$ an international

company, Gold$-$Retriever, found the wreckage of the ship and brought back the gold worth

$ $50$ million. A month later, a Spanish citizen, named Alberto Lopez claimed that he was

a direct descendent of Sergio and that, therefore, he was the owner of the gold. To prove

his point he hired an attorney and asked him to collect all birth certi$$cates showing that

he is a direct descendant of Sergio.

We will assume that Spain has kept archives of all birth certi$$cates during the last four

centuries and that all Alberto's ancestors up to Sergio lived in Spain. We will also assume

that the population of Spain between Sergio's birth and the present time has monotonically

increased from about $6$ million people to about $41$ million today.

Let Parents$($x$)$ be the function that returns the two parents of an individual x $($and their

dates of birth$)$ and Children$($y$)$ the function that returns the children of an individual y

$($and their dates of birth$).$ We will $$nally assume that a birth certi$$cate can be retrieved

as easily by either knowing the name of a child or the name of one of his$/$her parents. In

other words, it will cost the attorney the same amount of time to evaluate either function

Parents$()$ or function Children$().$

$($a$)[7$ points$]$ Formulate the Attorney's task to prove that Alberto is a descendant of

Sergio as a search problem:

i$.[2$ points$]$ Give a state representation for this problem.

ii$.[1$ points$]$ What is the initial state in your formulation?

iii. $[3$ points$]$ What are the available actions from a state and how does each modify

the state in your formulation?

iv$.[1$ points$]$ What is the goal state in your formulation?

$($b$)[4$ points$]$ Is your formulation the only one possible for this problem? If your answer

is $`$yes$\text{'},$ the explain why there is only one. If your answer is $`$no$\text{'},$ then give another

one.

$($c$)[4$ points$]$ What would be the easier way for the attorney to proceed: with an initial

state of Alberto, or an initial state of Sergio? Why?

$($d$)[4$ points$]$ Which search technique: breadth$-$rst$,$ depth$-$rst$,$ bi$-$directional, depth$-$

limited$,$ iterative deepening, etc. would you recommend to the attorney? Justify your

answer. $[$There might not be a clear$-$cut answer.$]$