solver.cpp

linux下面一个简单的求解课程表安排的程序利用了Easylocal++的类库

// File solver.cpp
#include "solver.hpp"

void TT_State::Allocate()
{
  Timetable::Allocate();
  room_lectures.resize(fp->Rooms() + 1, vector<unsigned>(fp->Periods()));
  course_daily_lectures.resize(fp->Courses(), vector<unsigned>(fp->Days()));
  working_days.resize(fp->Courses());	
}

ostream& operator<<(ostream& os, const TT_State& as)
{
  unsigned i, j;
  os << "TT_State: " << endl;
  for (i = 0; i < as.T.size(); i++)
    {
      for (j = 0; j < as.T[i].size(); j++)	
	os << setw(3) << as.T[i][j];
      os << endl;
    }
  os << endl;

  os << "Course daily lectures (redundant) " << endl;
  for (i = 0; i < as.course_daily_lectures.size(); i++)
    {
      for (j = 0; j < as.course_daily_lectures[i].size(); j++)	
	os << as.course_daily_lectures[i][j];
      os << endl;
    }
  os << endl;

  os << "Room lectures (redundant) " << endl;
  for (i = 0; i < as.room_lectures.size(); i++)
    {
      for (j = 0; j < as.room_lectures[i].size(); j++)	
	os << as.room_lectures[i][j] << ' ';
      os << endl;
    }
  os << endl;

  os << "Working days (redundant) " << endl;
  for (i = 0; i < as.working_days.size(); i++)
    os << as.working_days[i] << ' ';
  os << endl;
  return os;
}

TT_MoveTime::TT_MoveTime()
{
  course = 0;
  from = 0;
  to = 0;
}

TT_MoveTime::TT_MoveTime(unsigned c, unsigned f, unsigned t)
{
  course = c;
  from = f;
  to = t;
}

bool TT_MoveTime::operator==(const TT_MoveTime& c) const
{
  return course == c.course 
      && from == c.from
      && to == c.to;
}

bool TT_MoveTime::operator!=(const TT_MoveTime& c) const
{
  return course != c.course 
      || from != c.from
      || to != c.to;
}

istream& operator>>(istream& is, TT_MoveTime& c)
{
  char ch; 
  return is >> c.course >> ch >> c.from >> ch >> ch >> c.to;
}

ostream& operator<<(ostream& os, const TT_MoveTime& c)
{
  return os << c.course << ':' << c.from << "->" << c.to;
}

TT_MoveRoom::TT_MoveRoom()
{
  course = 0;
  period = 0;
  old_room = 0;
  new_room = 0;
}

TT_MoveRoom::TT_MoveRoom(unsigned c, unsigned p, unsigned o, unsigned n)
{
  course = c;
  period = p;
  old_room = o;
  new_room = n;
}

bool TT_MoveRoom::operator==(const TT_MoveRoom& c) const
{
  return course == c.course 
    && period == c.period
    && old_room == c.old_room
    && new_room == c.new_room;
}

bool TT_MoveRoom::operator!=(const TT_MoveRoom& c) const
{
  return course != c.course 
    || period != c.period
    || old_room != c.old_room
    || new_room != c.new_room;
}

istream& operator>>(istream& is, TT_MoveRoom& c)
{
  char ch; 
  return is >> ch >> c.course >> ch >> c.period >> ch 
	    >> c.old_room >> ch >> ch >> c.new_room;
}

ostream& operator<<(ostream& os, const TT_MoveRoom& c)
{
  return os << '[' << c.course << ':' << c.period 
	    << ']' << c.old_room << "->" << c.new_room;
}

// ***************************************************************************
//                               Helpers
// ***************************************************************************


// constructor
TT_StateManager::TT_StateManager(Faculty* pin) 
  : StateManager<Faculty,TT_State>(pin) 
{} 


// initial state builder (random rooms)
void TT_StateManager::RandomState(TT_State& as) 
{
  ResetState(as); // make all elements of as equal to 0
  for (unsigned c = 0; c < p_in->Courses(); c++)
    {
      unsigned lectures = p_in->CourseVector(c).Lectures();
      for (unsigned j = 0; j < lectures; j++)
	{
	  unsigned p;
	  do // cycle until the period is free and available
	    p = Random(0,p_in->Periods()-1);
	  while (as(c,p) != 0 || !p_in->Available(c,p));
	  as(c,p) = Random(1,p_in->Rooms());
	}
    }
  UpdateRedundantStateData(as);
} 

void TT_StateManager::ResetState(TT_State& as)
{
  for (unsigned c = 0; c < p_in->Courses(); c++)
    for (unsigned p = 0; p < p_in->Periods(); p++)
      as(c,p) = 0;
}

void TT_StateManager::UpdateRedundantStateData(TT_State& as) const
{
  unsigned p, c, r, d;
  
  for (r = 1; r < p_in->Rooms() + 1; r++)
    for (p = 0; p < p_in->Periods(); p++)
      as.ResetRoomLectures(r,p);

  for (c = 0; c < p_in->Courses(); c++)
    {
      for (p = 0; p < p_in->Periods(); p++)
	{
	  r = as(c,p);
	  if (r != 0)
	    as.IncRoomLectures(r,p);
	}
    }

  for (c = 0; c < p_in->Courses(); c++)
    {
      as.ResetWorkingDays(c);
      for (d = 0; d < p_in->Days(); d++)
      {
	as.ResetCourseDailyLectures(c,d);
	for (p = d * p_in->PeriodsPerDay(); 
	     p < (d+1) * p_in->PeriodsPerDay(); p++)
	  {
	    if (as(c,p) != 0)
	      as.IncCourseDailyLectures(c,d);
	  }
	if (as.CourseDailyLectures(c,d) >= 1)
	  as.IncWorkingDays(c);
      }
    }
} 

// cost function components

// violations
fvalue TT_StateManager::Violations(const TT_State& as) const 
{
  return Conflitcs(as) + RoomOccupation(as);
} 

fvalue TT_StateManager::Objective(const TT_State& as) const 
{
  return RoomCapacity(as) + MinWorkingDays(as);
} 

unsigned TT_StateManager::Conflitcs(const TT_State& as) const
{
  unsigned c1, c2, p, cost = 0;
  for (c1 = 0; c1 < p_in->Courses(); c1++)
    for (c2 = c1+1; c2 < p_in->Courses(); c2++)
      if (p_in->Conflict(c1,c2))
	{
	  for (p = 0; p < p_in->Periods(); p++)
	    if (as(c1,p) != 0 && as(c2,p) != 0)
	      cost++;
	}
  return cost;
}
          
unsigned TT_StateManager::RoomOccupation(const TT_State& as) const
{
  unsigned r, p, cost = 0;
  for (p = 0; p < p_in->Periods(); p++)
    for (r = 1; r <= p_in->Rooms(); r++)
      if (as.RoomLectures(r,p) > 1)
	cost += as.RoomLectures(r,p) - 1;
  return cost;
}

unsigned TT_StateManager::MinWorkingDays(const TT_State& as) const
{
  unsigned c, cost = 0;
  for (c = 0; c < p_in->Courses(); c++)
    if (as.WorkingDays(c) < p_in->CourseVector(c).MinWorkingDays())
      cost += p_in->CourseVector(c).MinWorkingDays() - as.WorkingDays(c);
  return cost;  
}

unsigned TT_StateManager::RoomCapacity(const TT_State& as) const
{
  unsigned c, p, r, cost = 0;
  for (c = 0; c < p_in->Courses(); c++)
    for (p = 0; p < p_in->Periods(); p++)
      {
	r = as(c,p);
	if (r != 0 && p_in->RoomVector(r).Capacity() < p_in->CourseVector(c).Students())
	  cost++;
      }
  return cost;
}


// print cost function components

// violations
void TT_StateManager::PrintViolations(ostream& os, const TT_State& as) const 
{
  PrintConflitcs(os,as);
  PrintRoomOccupation(os,as);
  PrintRoomCapacity(os,as); 
  PrintMinWorkingDays(os,as);
} 

void TT_StateManager::PrintConflitcs(ostream& os, const TT_State& as) const
{
  unsigned c1, c2, p;
  for (c1 = 0; c1 < p_in->Courses(); c1++)
    for (c2 = c1+1; c2 < p_in->Courses(); c2++)
      if (p_in->Conflict(c1,c2))
	{
	  for (p = 0; p < p_in->Periods(); p++)
	    if (as(c1,p) != 0 && as(c2,p) != 0)
	      os << "Courses " << p_in->CourseVector(c1).Name() << " and " 
		 <<  p_in->CourseVector(c2).Name() << " have both a lecture at " 
		 << p_in->PeriodVector(p).Name() << endl;
	}
}
          
void TT_StateManager::PrintRoomOccupation(ostream& os, const TT_State& as) const
{
  unsigned r, p;
  for (p = 0; p < p_in->Periods(); p++)
    for (r = 1; r <= p_in->Rooms(); r++)
      if (as.RoomLectures(r,p) > 1)	
	os << as.RoomLectures(r,p) << " lectures in room " 
	   << p_in->RoomVector(r).Name() << " the period " << p_in->PeriodVector(p).Name() << endl;
}

void TT_StateManager::PrintMinWorkingDays(ostream& os, const TT_State& as) const
{
  unsigned c;
  for (c = 0; c < p_in->Courses(); c++)
    if (as.WorkingDays(c) < p_in->CourseVector(c).MinWorkingDays())
      os << "The course " << p_in->CourseVector(c).Name() << " has only " << as.WorkingDays(c)
	 << " days of lecture" << endl;
}

void TT_StateManager::PrintRoomCapacity(ostream& os, const TT_State& as) const
{
  unsigned c, p, r;
  for (c = 0; c < p_in->Courses(); c++)
    for (p = 0; p < p_in->Periods(); p++)
      {
	r = as(c,p);
	if (r != 0 && p_in->RoomVector(r).Capacity() < p_in->CourseVector(c).Students())
	  os << "Room " << p_in->RoomVector(r).Name() << " too small for course " 
	     << p_in->CourseVector(c).Name() << " the period " 
	     << p_in->PeriodVector(p).Name() << endl;
      }
}

/*****************************************************************************
 * Output Manager Methods
 *****************************************************************************/

void TT_OutputManager::InputState(TT_State& as, const Timetable& tt) const 
{
  for (unsigned i = 0; i < p_in->Courses(); i++)
    for (unsigned j = 0; j < p_in->Periods(); j++)    
      as(i,j) = tt(i,j);
  p_sm->UpdateRedundantStateData(as);
}

void TT_OutputManager::OutputState(const TT_State& as, Timetable& tt) const 
{
  for (unsigned i = 0; i < p_in->Courses(); i++)
    for (unsigned j = 0; j < p_in->Periods(); j++)    
      tt(i,j) = as(i,j);
}

void TT_OutputManager::PrettyPrintOutput(const Timetable& tt, string dir_name) const
{
  unsigned i, j, c, r, p, days = p_in->Periods()/ p_in->PeriodsPerDay();
  string day_names[5] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
  string file_name;
  ofstream os;
  
  //  os << "<center><h1 class=\"title\">Orario studenti</h1></center>" << endl;
  for (i = 0; i < p_in->Groups(); i++)
    {
      file_name = dir_name + '/' + p_in->GroupVector(i).Name() + ".html";
      os.open(file_name.c_str());
      assert(!os.fail());
      os <<  "<!DOCTYPE HTML PUBLIC \"-//IETF//DTD HTML//EN\">\n<html>\n<head>\n"
	 << "<link rel=\"stylesheet\" href=\"tt_style.css\" type=\"text/css\"></link>\n"
	 << "</head>\n\n  <body>\n<br><br>\n"     
	 << "<table BORDER CELLPADDING=6 WIDTH = \"100%\">\n<tr>\n<td COLSPAN=\"6\" class=\"header\">" 
	 << "<p class=\"course_group\"> " << p_in->GroupVector(i).LongName() << "</p>"
	 << "</td>\n</tr>\n\n"
	 << "<tr>" << endl
	 << "<td width = \"15%\" class=\"header\"><div class=\"hours\" align=\"right\">periods</div>"
	 << "<div class=\"days\" align=\"left\">days</div></td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">9-11</center></td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">11-13</center></td>\n"
	 << "<td width = \"5%\" class=\"header\">&nbsp;</td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">14.30-16.30</center></td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">16.30-18.30</center></td> \n</tr>";      
      for (j = 0; j < days; j++)
	{
	  os << "<tr>\n<td class=\"header\"><center class=\"days\">" + day_names[j] + "</center></td>\n";
	  for (p = j * p_in->PeriodsPerDay(); p < (j+1) * p_in->PeriodsPerDay(); p++)
	    {
	      if (p % p_in->PeriodsPerDay() == 2)
		os << "<td class=\"empty\">&nbsp;</td>\n";
	      if (GroupLecture(tt,i,p,c,r)) 
		{
		  os << "<td class=\"full\"><p class=\"subject\">" 
		     << p_in->CourseVector(c).LongName() << "<p class=\"teacher\">(" 
		     << p_in->CourseVector(c).Teacher() << ")<div class=\"room\">\n" 
		     << p_in->RoomVector(r).Name() << "</div></td>\n";
		}
	      else
		os << "<td class=\"empty\">&nbsp;</td>\n";
	    }
	  os << "</tr>\n\n";
	}
      os << "</table><br></br>\n</body>\n</html>\n";
      os.close();
    }

  for (r = 1; r <= p_in->Rooms(); r++)
    {
      file_name = dir_name + '/' + "Room" + p_in->RoomVector(r).Name() + ".html";
      os.open(file_name.c_str());
      assert(!os.fail());
      os <<  "<!DOCTYPE HTML PUBLIC \"-//IETF//DTD HTML//EN\">\n<html>\n<head>\n"
	 << "<link rel=\"stylesheet\" href=\"tt_style.css\" type=\"text/css\"></link>\n"
	 << "</head>\n\n  <body>\n<br><br>\n"     
	 << "<table BORDER CELLPADDING=6 WIDTH = \"100%\">\n<tr>\n<td COLSPAN=\"6\" class=\"header\">" 
	 << "<p class=\"room\"> Room " << p_in->RoomVector(r).Name() << " (" << p_in->RoomVector(r).Capacity() << " seats)</p>"
	 << "</td>\n</tr>\n\n"
	 << "<tr>" << endl 
	 << "<td width = \"15%\" class=\"header\"><div class=\"hours\" align=\"right\">periods</div><div class=\"days\" align=\"left\">days</div></td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">9-11</center></td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">11-13</center></td>\n"
	 << "<td width = \"5%\" class=\"header\">&nbsp;</td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">14.30-16.30</center></td>\n"
	 << "<td width = \"20%\" class=\"header\"><center class=\"hours\">16.30-18.30</center></td> \n</tr>";      
      for (j = 0; j < days; j++)
	{
	  os << "<tr>\n<td class=\"header\"><center class=\"days\">" + day_names[j] + "</center></td>\n";
	  for (p = j * p_in->PeriodsPerDay(); p < (j+1) * p_in->PeriodsPerDay(); p++)
	    {
	      if (p % p_in->PeriodsPerDay() == 2)
		os << "<td class=\"empty\">&nbsp;</td>\n";
	      for (c = 0; c < p_in->Courses(); c++)
		if (tt(c,p) == r)
		{
		  os << "<td class=\"full\"><p class=\"subject\">" 
		     << p_in->CourseVector(c).LongName() << "<p class=\"teacher\">(" 
		     << p_in->CourseVector(c).Teacher() << ")"
		     << "</td>\n";
		  break;
		}
	      if (c == p_in->Courses()) // no lecture found
		os << "<td class=\"empty\">&nbsp;</td>\n";
	    }
	  os << "</tr>\n\n";
	}
      os << "</table><br></br>";
      os << "</body>\n</html>\n";
      os.close();
    }

  // file of empty rooms
  file_name = dir_name + "/EmptyRooms.html";
  os.open(file_name.c_str());
  assert(!os.fail());
  os <<  "<!DOCTYPE HTML PUBLIC \"-//IETF//DTD HTML//EN\">\n<html>\n<head>\n"
     << "<link rel=\"stylesheet\" href=\"tt_style.css\" type=\"text/css\"></link>\n"
     << "</head>\n\n  <body>\n<br><br>\n"