なっとくアルゴリズムでは「集合カバー問題」となっていたのですが、どうも日本語だと「集合被覆問題」の方が一般的なようなので、そんなタイトルにしました。

集合と論理演算


基本情報とかでやるアレ。

集合論理演算
積集合論理積(AND)$A∩B$
和集合論理和(OR)$A∪B$
補集合否定(NOT)$\overline{ A }$
-否定論理積(NAND)$\overline{ A*B }$
-排他的論理和(XOR)$\overline{ A } * B+A * \overline{ B }$

このへんScalaでは下記のように書くことができる。

1
2
3
4
5
6
7
8
9
10
11
12
13
//積集合
val i = List(1, 3, 8, 10) intersect List(1, 2, 8, 10, 11)
println(i) // List(1, 8, 10)

//和集合
val u = List(1, 3, 8, 10) union List(1, 2, 8, 10, 11)
println(u) // List(1, 3, 8, 10, 1, 2, 8, 10, 11)

//差集合
val d = List(1, 3, 8, 10) diff List(1, 2, 8, 10, 11)
val d2 = List(1, 2, 8, 10, 11) diff List(1, 3, 8, 10)
println(d) // List(3)
println(d2) // List(2, 11)

部分集合


$A \subset B$

2つの集合A,Bで集合Aの要素の全てがBの要素になってる(含まれている)やつ。逆も然り。ベン図でいうと、丸の中に丸があるやつ。

べき集合


例えば集合Aが下記の時に…(レンダリングでエラーでたのでシンタックスハイライトで書いてます)

A = { 1, 2 }

この集合Aの部分集合は下記のとおりになる。

  • $\varnothing$ (空集合)
  • {a}
  • {b}
  • {a,b}

これは $2^A$ として表すことができる。

集合被覆問題


集合被覆問題は集合とその部分集合の組み合わせが与えられたときにその組み合わせで最もコストが少ないものを求める問題。

例えば上図のように県と放送局(①~⑤)があるときに、全ての県をカバーする最もコストの低い放送局の組み合わせを求める。(なっとくアルゴリズムのサンプルはアメリカの州で解り辛かったので関西圏の県にしました)

全ての部分集合を洗い出すには $O(2^n)$ かかる。ので、前回書いた貪欲法を用いて、ある程度近い結果を求める。これを近似アルゴリズムという。厳密解の計算に時間がかかる場合は近似アルゴリズムを使うとよいらしい。(これ、どっちでやるかとっさに判断できるもんなんですか…???)

考え方


前述の図を例にすると…

  • まだカバーされていない県を取得
  • その件をカバーしている放送局のうち、最もカバー率の高い放送局を選ぶ(この時に積集合を使う)
  • 放送局をリストに追加し、未カバーの県のリストを更新する

これを繰り返す。

Scalaでの実装


IT事務員おじさんがそれっぽくScalaで書いたコードが下記になる。今回は結構Scalaっぽく書けたのではないかという気がする。

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
object CoveringProblem extends App {

case class Station(name: String, state: List[String])

//カバー対象の県のリスト
val neededPrefectures : List[String] = List("三重", "岡山", "和歌山", "兵庫", "大阪", "京都", "滋賀", "香川")

//各放送局がカバーしている県
val stations: List[Station] = List(
Station("放送局1", List("兵庫", "大阪", "京都")),
Station("放送局2", List("岡山", "兵庫", "三重")),
Station("放送局3", List("和歌山", "大阪", "滋賀")),
Station("放送局4", List("大阪", "京都")),
Station("放送局5", List("滋賀", "香川")),
)

val result = search(neededPrefectures, stations, List())
println(result)

def search(neededPref: List[String], stations: List[Station], result: List[String]): List[String] = {
if (neededPref.isEmpty) {
result
} else {
// カバー対象の県のリストを順次処理する。積集合で処理対象の県を含めて最もカバー率の高い放送局を取得する
val s = stations.map(s => Station(s.name, List(neededPref.head) intersect s.state)).maxBy(_.state.length)

// カバー済みになった県と放送局を除外して続けて調べる
search(neededPref diff stations.filter(_.name == s.name).head.state, stations.filter(_.name != s.name), result :+ s.name)
}
}

}

/*
結果
List(放送局2, 放送局3, 放送局1, 放送局5)
*/

その他


Scalaで書くと結局非関数型言語のコードとは変わってしまうので、一通り終わったら一度JSかC#辺りで全部やり直してみるのもありかなと思っている。

参考


下記の記事を参考にさせていただきました。ありがとうございました。

図書館員のコンピュータ基礎講座: 論理演算
集合の記号の意味まとめ

参考書籍


なっとく! アルゴリズム