Python implementation of a solver for the desert crossing, Python Programming

Assume you have a truck which has to travel across a desert from the base camp at position 0 (left) to the target camp at position 4 (right). The intermediate positions 1,2, and 3 are desert camps, and have at the beginning of the process no fuel.

The truck is able to take 3 units of fuel with it. Each move 1 field to the right (towards the target camp, Figure) or 1 field to the left (towards the base camp) uses up 1 unit of fuel. If not all fuel is used up in a move, and the move has not reached the target camp, the remaining fuel is dropped at the current position for later use.

1384_BFS.png

Figure: Desert Travel Example

There is arbitrary amount of fuel at the base camp (of which the truck can take at most 3 units), and when the truck has reached position 4 (target camp), the puzzle is completed. However, when the truck is at one of the positions 1,2,3, it can take only as much fuel with it as there is present at the given position.

The goal is to allow the truck to travel through the desert to the target camp.

The Formal Rules for the Desert Crossing Task

The following are the rules for the movement of the truck.

1. In the base camp (position 0), the truck can load as much fuel as its carrying capacity (i.e. 3).

2. In the target camp (position 4), the truck has nothing more to do. The task is solved.

3. Arriving in a desert camp (position 1,2 or 3) the truck will unload whatever fuel was remaining from the trip. For instance, if the truck started at base camp (0), with 3 units of fuel, arriving at 1, it will unload 2 units.

4. Leaving from a desert camp (position 1,2 or 3), the truck will choose how much fuel it will pick up from there. It will then make a move (left or right), at most as far as the fuel picked up permits. As the move is completed, it proceeds according to rule 1,2 or 3.

The Task

Based on the search algorithms covered in the lecture, write a Python program that starts from the starting state (truck in base camp) and moves according to the rules until it reaches the goal state (truck in target camp).

For this, you have to adapt the search algorithms introduced in the lecture presented in the lecture and apply it to a Desert class which you have to write.

A pure depth-first-search will not be sufficient and you will have to use at least a breadth-first-search for this scenario (or enhance your search such as to remember and not repeat past positions). You can use the breadth-first-search program from the lecture for this.

Detailed Instructions and Marking Scheme

Core Tasks You need to write a class Decant and define for it (at least) the following class methods:

1. start(self): returns the starting state for the desert task. In particular, this task defines the data structure you are going to use for a puzzle state.

Hint: There are different ways of representing the puzzle state | whatever you choose to do, make sure you comment clearly how you decided to represent the state. You will be marked down if the data structure is not clear or clearly commented.

2. goal(self, state): returns True if the configuration state is a goal configuration, i.e. if the truck reached the target camp.

3. succ(self, state): yields successively all the successors of state.

Furthermore, you will have to write

4. the code importing the various modules

5. the code running the search and printing the results

Advanced Tasks Once you have successfully implemented the breadth-first-search solution for the desert crossing task, you can proceed to implement best-first solutions for additional marks. You can use the best-first search algorithm from the lecture for this.

6. for the best-first search, you will need to write a specialized Desert_Path class which derives from path.Path. It implements at least a __le__(self, path2) method (required for best-first search! ) returning True if the self path cost is less or equal the path cost of path2 (also of class Decant_Path), and False otherwise.

7. you will also have to modify the code running the search and printing the results accordingly

Posted Date: 3/19/2013 3:27:23 AM | Location : United States







Related Discussions:- Python implementation of a solver for the desert crossing, Assignment Help, Ask Question on Python implementation of a solver for the desert crossing, Get Answer, Expert's Help, Python implementation of a solver for the desert crossing Discussions

Write discussion on Python implementation of a solver for the desert crossing
Your posts are moderated
Related Questions
Define a function that draws a pentagon of a size you provide when you call the function. Include a ''''''docstring'''''' as the first line of the function''s body — it tells the p

Every programming language has to have  some method for indicating grouping of operations. Here is how you execute an if-then-else structure in Java:   if (s == 1){ s = s

Programs and Data Object-oriented programming is a popular way  of managing programs, which  groups together data  with  the procedures that  works on them,  thus  facilitatin

protocol rdt2.2 considers there is a bit errors between sender to receiver and also from receiver to sender. So now we have to consider checking bit errors introduced in reply from

Write a Python program to accomplish the following. Use modular design. Include at least 3 functions: one that returns zero values, one that returns one value, and one that retu

For this assignment, you are to: 1.    Modify the output format of your Python script from Assignment 1 to match the input format of your C program from Assignment 2. 2.    W

Python Programs You must submit the source code and samples of output for each program.Please do not provide python file (eg. Filename.py). Copy all source code to one word fi

There are three seating categories at a stadium. For a softball game, Class A seats cost $15, Class B seats cost $12, and Class C seats cost $9. Write a program that asks how many

Write a program that will take price data for stocks and print it graphically to the screen. Your program should begin by asking the user for the file name. It should then create a

In Python, the fundamental abstraction of a computation is as a procedure (other  books call them "functions" instead; we will end  up  using  both  values).   A function that  tak