貪欲法(Greedy Algorithm)について。

特徴


  • 常に最適を選び続ける
  • 最適解を得られるかどうかがわからない
  • 得られない場合は近似解になる


下記のような授業があるとする。

授業開始終了
美術9:0010:00
国語9:3010:30
算数10:0011:00
コンピュータ10:3011:30
音楽11:0012:00

引用元: なっとくアルゴリズムより

これらの授業を一つの教室でできるだけ多く行いたい。貪欲法を使って解く場合は常に最適を選び続けるとよいので…

  • 最も早く終わる授業を選択する
  • 選択した授業の終了時間と同じ授業を選ぶ

これを繰り返す。例の場合だと、美術 → 算数 → 音楽になる。

Scala


流石にこれくらいはScala片手間IT事務員おじさんでも解くことができる。

1
package GreedyAlgorithm
2
3
import java.time.LocalTime
4
5
object GreedyAlgorithm extends App {
6
7
  case class Lesson(subject: String, start: LocalTime, end: LocalTime)
8
9
  val startTime = LocalTime.of(9,0)
10
  val endTime = LocalTime.of(12,0)
11
12
  val lessons: List[Lesson] = List(
13
    Lesson("Art", LocalTime.of(9,0), LocalTime.of(10,0)),
14
    Lesson("NationalLanguage", LocalTime.of(9,30), LocalTime.of(10,30)),
15
    Lesson("Mathematics", LocalTime.of(10,0), LocalTime.of(11,0)),
16
    Lesson("Computer", LocalTime.of(10,30), LocalTime.of(11,30)),
17
    Lesson("Music", LocalTime.of(11,0), LocalTime.of(12,0))
18
  )
19
20
  val firstLesson = lessons.minBy(_.end)
21
  val result = findNextLesson(firstLesson, lessons, List(firstLesson))
22
  println(result)
23
24
  def findNextLesson(currentLesson: Lesson, lessons: List[Lesson], answer: List[Lesson]): List[Lesson] = {
25
    val maybeNextLesson = lessons.filter(_.start.compareTo(currentLesson.end) >= 0)
26
    if (maybeNextLesson.isEmpty) {
27
      answer
28
    } else  {
29
      val nextLesson = maybeNextLesson.minBy(_.end)
30
      findNextLesson(nextLesson, lessons, answer :+ nextLesson)
31
    }
32
  }
33
34
}
35
36
/*
37
List(Lesson(Art,09:00,10:00), Lesson(Mathematics,10:00,11:00), Lesson(Music,11:00,12:00))
38
 */

参考書籍


なっとく! アルゴリズム