As announced assignment # 1 consist of 3 parts: a self-explorartory on-line task, some paper and pencil work, and some programming.

Due date: Mo 17.11.2003

Please go to

http://www.ifi.unizh.ch/ddisold/Teaching/BI2003/Applets/CLspace/search/index.html

(page protected with the usual username & password)

alternatively go to:

http://www.cs.ubc.ca/labs/lci/CIspace/Version4/search/index.html

and try out all the search algorithms. Ask yourself whether you can find all the differences between the algorithms addressed in class.

Consider the following logic puzzle: In five houses, each with a different color, live 5 persons of different nationalities, each of whom prefer a different brand of cigarette, a different drink, and a different pet.

a) Given the following facts, the question to answer is “Where does the zebra live, and in which house do they drink water?”

• The Englishman lives in the red house.
• The Spaniard owns the dog.
• The Norwegian lives in the first house on the left.
• Kools are smoked in the yellow house.
• The man who smokes Chesterfields lives in the house next to the man with the fox.
• The Norwegian lives next to the blue house.
• The Winston smoker owns snails.
• The Lucky Strike smoker drinks orange juice.
• The Ukrainian drinks tea.
• The Japanese smokes Parliaments.
• Kools are smoked in the house next to the house where the horse is kept.
• Coffee is drunk in the green house.
• The Green house is immediately to the right (your right) of the ivory house.
• Milk is drunk in the middle house.

b) Formulate the problem in terms of variables, domains, and constraints.

c) Enter the problem into the applet that can be found and downloaded from here. Find the solution using the algorithm.

Please note:

1. You can also use another CSP solver
2. If you choose the applet, you might NOT want to use any string-set domains (but integers), as the number of constraint types is too limited with strings!

d) (optional for extra credit) Discuss different representations of this problem as a CSP. Why would one prefer one representation over another?

What to hand it:

• a) A textual description of the answer
• b) A textual definition of the problem (domains, variables, etc.)
• c) A creen-dump/output of the program
• d) a textual description of the answer

Please note: I might still make part c) optional, depending on the time it takes me to solve the problem (:-)

Overview

The goal of this assignment is to learn more about search algorithms by enhancing a simple depth search algorithm for faster performance and the ability to handle a huge amount of data, as shown in class.

As real-world example we simulate a query on the schedule of the public transport. The task is to find the fastest way from A to B. As data serves a simplified data set derived from the Verkehrsbetriebe Zürich (VBZ).

Introduction

An application has been written to provide an appropriate environment that allows direct implementation of algorithms. The java source code of the application can be downloaded as zip. Unpack the zip file in a directory that is defined in your CLASSPATH environment variable. More about installing java and environment variables can be found here (use Java 1.4 or later!).

The main method of this application is in the RouteFinder class and is called as follows:

  c:\java\src\bi\>java bi.RouteFinder <args[0]> <args[1]> <args[2]> <args[3]>

where the arguments are:

• <args[0]>: departure stop (mandatory)*
• <args[1]>: destination stop (mandatory)*
• <args[2]>: average time for changing bus or street car lines [s] (mandatory)
  (The average travel velocity has been set arbitrarily to 15m/s <=> 54km/h)
• <args[3]>: '-t' stands for the pruned data set (for testing), while no argument for the complete data set (optional).

  e.g. c:\java\src\bi\>java bi.RouteFinder Irchel ETH_Hoenggerberg 300 -t

It is strongly recommended to read the APIdoc to get more detailed information on this application.

* Attention: The characters 'ä', 'ö', 'ü' have to be replaced by 'ae', 'oe', 'ue' as shown in the example above. Additionally, spaces in stop names are replaced by '_'. The input is case sensitive!

Attention: There are two algorithms implemented. First, an heuristic depth search is executed followed by a non-heuristic depth search. Applied on the complete data set the non-heuristic depth search throws an 'StackOverflowError' because the search is very inefficient.
(A 'StackOverflowError' is always thrown when a stack overflow occurs because an application recurses too deeply.)

The Assignment

You have to create an algorithm analogous to the algorithm implemented by enhancing it with heuristic features or even more sophisticated methods like indexing, 'divide and conquer' strategies - whatever comes to your mind. The algorithm should find the optimal way from A to B with respect to short travelling time.

The assignment is fulfilled if your algorithm is at least twice as fast than the implemented simple depth seach algorithm and it is able to handle a query on the full data set, like:

  e.g. c:\java\src\bi\>java bi.RouteFinder Loewenplatz Dorflinde 300

Groups of 2-3 students are allowed. Please send your solution to vorburger@ifi.unizh.ch. Don't hesitate to write an email if questions or suggestions rise.

last modified: October, 31 2003, 11:53: bi.zip