2

每个人都熟悉计算机科学中的进度问题。
我不是要求解决这个问题的算法。

我只是想为学校的一个学期创建我的个人日程表

你可以假设：

  • 我大学的某个人已经创建了课程，分配了教师，房间等。因此，课程已经存在，可以选择。
  • 我只有一小部分课程可供我使用。说25节课。
  • 我每学期必须上 5 节课（可能或多或少，但让我们保持简单）

    我想要的只是一些关于如何创建有效时间表的提示/线索，更重要的是，最佳时间表。
    想一想，什么是最佳时间表？
    就我个人而言，这些课程来自 2 个不同的学院，但我已经能够创建一个包含如下信息的 csv 文件：

    米               
16:35:00 17:25:00 菲尔 375 存在主义。
14:35:00 15:55:00 COMP 350 数值计算。
14:35:00 15:55:00 COMP 208 工程计算机。
14:35:00 15:25:00 PHIL 306 心灵哲学。
14:35:00 15:25:00 PHIL 200 哲学导论
..ETC

    如您所见，所有内容均按开始时间（倒置）排序，但存在冲突。一周中的所有其他日子都一样。
    如何创建有效/最佳时间表？我应该考虑什么？

    更多信息：

    这是我最初认为我应该考虑的事情：

  • 对我来说，一个优先事项是尽可能晚上课。所以我会选择周一、周三和周五的 3 个最新可能的课程，以及周二、周四的 2 个课程。[请参阅评论，了解我认为我可以如何实现这一点]
  • 另一种解决方案是在课程之间（或相反）获得最少的“休息”
  • 另一个可能是最早的课程
  • 另一个优先事项是在同一天为 1 位教员安排所有课程，然后为 A 教员安排 1 节课，然后为 B 教员安排 1 节课，以此类推。
    遗漏了什么？

    • 4

    1 回答 1

    2

    对于这个规模 - 我不会太努力地避免简单的编程蛮力解决方案。

    从 25 门课程中选择 5 门课程有25!/(20!*5!)=53130不同的可能性。只需检查所有课程，并获得最好的 - 保证最佳解决方案。对于任何现代机器来说，这种规模的运行时间也不是问题。

    回溯解决方案很简单——“猜测”要添加的课程，递归调用直到你有一个完整的列表，评估解决方案。当您从递归中返回时 - 检查选择课程的不同可能性。

    伪代码：

    best = 0
bestSol = nil
findCalendar(courses,candidate,i):
  if (take.size() == 5):
      t = evaluate(candidate)
      if (t > best):
          best = t
          bestSol = copy(candidate)
      return
  else if (i == courses.size()):
      //another stop clause, for non-feasible solutions (less then 5 were selected)
      return 
  for each j in range(i,courses.size()):
      candidate.add(courses[j]) //add this course to the candidate
      fidnCalendar(courses,candidate,j+1) //recurse to find the next courses for this candidate
      candidate.removeLast() //cklean up environment before next candidates

    调用 with findCalendar(myCourses,[],0)，当算法完成时 -bestSol将保存最好的日历，它的值将是best

    于 2012-08-30T06:11:20.930 回答