• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Walksat algorithm implementation

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 need....how do i relate things together by coding ?.......the problem statement as follows:


Input:
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)


Constraint:
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.

Requirement:
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.
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
Bill
 
Ahmed Mohamed
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
well....as 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?

thnkx
 
William Brogden
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
Bill
 
I didn't like the taste of tongue and it didn't like the taste of me. I will now try this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic