This week's book giveaway is in the Jobs Discussion forum.
We're giving away four copies of Customer Requirements for Developers and have Marcho Behler on-line!
See this thread for details.
The moose likes Java in General and the fly likes Walksat algorithm implementation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Customer Requirements for Developers this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Walksat algorithm implementation" Watch "Walksat algorithm implementation" New topic

Walksat algorithm implementation

Ahmed Mohamed

Joined: Oct 25, 2004
Posts: 8
hi fellows.....
i am trying to write a program to solve class scheduling program....the problem is based on implementing the walksat algorithm or hill climbing algorithm.....i have looked at these algorithms but unfortunalely i was not be able to understand them and how to code them.......i was thinking that i can get some tips and ideas that will help me in solving this problem.....what functions i do i relate things together by coding ?.......the problem statement as follows:

Four files with the following information:
(class id, session id, type of activity (class, Tutorial) no. of hours, preferred room id)

(student id, class id)

(room id, size)

(faculty id, class id, session id)

No student has conflict (two activities) at the same time.
A student has to take more than one Tutorial per course
Faculty should not teach two consecutive courses. Two course without any break in between them.

The program should read the above information and create a schedule as follows:
(Class id, session id, type of activity, room id)

The schedule should not violate any of the above mentioned constraint. A generate and test or random walk algorithm such as Hill Climbing or WALKSAT could be used in implementation of this program.

thank you very much.
William Brogden
Author and all-around good cowpoke

Joined: Mar 22, 2000
Posts: 12982
Well, in general you will need to:
1. start with some method of describing a class schedule in sufficient detail from your inputs.
2. create method(s) for determining how close a given schedule comes to satisfying all the constraints
3. if you have satisfied all constraints - you won
4. keep a record of the datasets that have been best so far and use the best as a starting point for the next try. See the WALKSAT algorithm...

Note that any hill climbing algorithm has a built in danger that it may locate a "local optimum" (think foothill) that can't be improved by any simple change but is far from the best solution. To combat this tendency the program should be run with many different "starting positions."

If I had this problem I would look into genetic algorithms rather than any hill climbing algorithm. In any case this is not a trivial assignment, let us know how you do.
Ahmed Mohamed

Joined: Oct 25, 2004
Posts: 8 i understand so far....i have analyzed the problem..and i have come up with the following solution ...

1. FOUR FILES : for this there will be a class to read those files.
2. The Class Schedule: in this class all the methods that contains the logic of the algorithm will be implemented .
3. Class SchduleTest : the main method will go here.

is that the correct way?

William Brogden
Author and all-around good cowpoke

Joined: Mar 22, 2000
Posts: 12982
Your ClassSchedule object will somehow have to represent the classes, students, rooms and faculty in such a way that it can compute how many of the constraints are violated. It seems to me that your key decisions will be in how to create this representation, and to do it in such a way that it is easy to create alternate schedules.
Everything else will depend on that.
jQuery in Action, 3rd edition
subject: Walksat algorithm implementation
It's not a secret anymore!