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

特徴


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


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

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

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

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

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

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

Scala


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package GreedyAlgorithm

import java.time.LocalTime

object GreedyAlgorithm extends App {

case class Lesson(subject: String, start: LocalTime, end: LocalTime)

val startTime = LocalTime.of(9,0)
val endTime = LocalTime.of(12,0)

val lessons: List[Lesson] = List(
Lesson("Art", LocalTime.of(9,0), LocalTime.of(10,0)),
Lesson("NationalLanguage", LocalTime.of(9,30), LocalTime.of(10,30)),
Lesson("Mathematics", LocalTime.of(10,0), LocalTime.of(11,0)),
Lesson("Computer", LocalTime.of(10,30), LocalTime.of(11,30)),
Lesson("Music", LocalTime.of(11,0), LocalTime.of(12,0))
)

val firstLesson = lessons.minBy(_.end)
val result = findNextLesson(firstLesson, lessons, List(firstLesson))
println(result)

def findNextLesson(currentLesson: Lesson, lessons: List[Lesson], answer: List[Lesson]): List[Lesson] = {
val maybeNextLesson = lessons.filter(_.start.compareTo(currentLesson.end) >= 0)
if (maybeNextLesson.isEmpty) {
answer
} else {
val nextLesson = maybeNextLesson.minBy(_.end)
findNextLesson(nextLesson, lessons, answer :+ nextLesson)
}
}

}

/*
List(Lesson(Art,09:00,10:00), Lesson(Mathematics,10:00,11:00), Lesson(Music,11:00,12:00))
*/

参考書籍


なっとく! アルゴリズム