Graph Golfに挑戦 - アクセル工房

NII(国立情報学研究所)主催の競プロGraph Golfに参加して，うまくいかなかったので報告です．

問題概要

与えられた頂点数Nと次数dから，次で定義するスコアが小さいレギュラーグラフ(すべての頂点の次数が同じ)Gを求める問題です．

${\displaystyle \textrm{score} = 10000 \times \textrm{diam}(G) + \textrm{aspl}(G) }$

ここで，diamはグラフの直径（最長の距離）， asplは平均経路長（全頂点間の距離の平均）のことです．

詳しくは，大会サイトまたは問題の解説 (pdfをダウンロードします)をご覧ください．

問題概要
アルゴリズム概要
枝刈り
- 1.ノードに目印
- 2.頂点間距離テーブル
  - 補足アンドメモ：高速に更新する実装（Python,NumPy）
スコア予測
結果
問題点1(予測が悪い)
問題点2（初期状態が悪い）

アルゴリズム概要

最良優先探索（探索で，高評価の状態を優先的に展開）を使いました．

初期状態：平衡木
次の状態：次数d未満の頂点同士を結んでできたグラフ
評価関数：スコアの下限
終了条件：すべての頂点の次数がd

この中で，平衡木から作るのは，ムーアバウンドを参考にしたためです．これは，次数直径問題の用語で，直径diamと次数dが定められたときの，最大の頂点数を表します．その中身は，

根はd個の子を持つ
枝はd-1個の子を持つ

ような，深さdiamの平衡木のノードの総数を表します．また，何もない状態から作る考え方に比べて，木から作る方が実装が簡単で，なおかつ探索範囲を小さくできると考えました(根拠はありませんが)．

例としてN=10,d＝3の場合の初期状態の木を示します．また，そこから辺を一つ加えたグラフを示します．

f:id:leichtrhino:20161015224446p:plain:w400

枝刈り

このままでは組合せ爆発で現実的な時間内で解が得られません．簡単な解決法のひとつに，次の方法があります．

頂点間を結ぶときに，どちらか片方の頂点を，次数がd未満で添字が最小の頂点とする．

こうすることで，結ぶ順番だけが異なる状態がなくなり，展開する状態の重複を削減できます．加えて，次の2点に着目して枝刈りをしました．

1.ノードに目印

初期状態（木）で次数がd未満の頂点に対して，次のmarkリストをつけてグラフの同型判定に役立てました．

$$ \textrm{descendants}(v) = \left\{ \begin{array}{lr} \textrm{degree}(v) & (\textrm{degree}_0(v) < d) \\ 1 + \sum_{c\in\textrm{children}(v)}\textrm{mark}(c) & (\textrm{otherwise}) \end{array} \right. \\ \textrm{mark}(v) = \left\{ \begin{array}{lr} [\textrm{descendants}(v)] & (v\,\textrm{is root}) \\ \textrm{mark}(v) = \textrm{cons}(\textrm{descendants}(v),\,\textrm{mark}(\textrm{parent}(v)) & (\textrm{otherwise}) \end{array} \right. $$

ここで，consは，要素をリストの先頭に加える操作を言います．

例えば，N=10,d＝3で，現在，(4,6)に辺がある場合，

f:id:leichtrhino:20161015224445p:plain:w400

で，辺を切り株として表す(辺を切って頂点のようにする)と，

f:id:leichtrhino:20161015224444p:plain:w400

となり，descendants関数の値は，

f:id:leichtrhino:20161015224443p:plain:w400

となります．結局，初期状態で次数がd未満の頂点(4,5,6,7,8,9)のｍａｒｋ関数の結果のリストを集めた集合は， {[2, 4, 12], [1, 4, 12], [1, 3, 12]}です．

同様にして，(4,7)に辺がある場合のdescendants関数の値は，

f:id:leichtrhino:20161015224442p:plain:w400

これのmark関数値の集合は， {[2, 4, 12], [1, 4, 12], [1, 3, 12]}で，(4,6)と同型と判定されます．

また，(4,5)に辺がある場合のdescendants関数の値は，

f:id:leichtrhino:20161015224441p:plain:w400

これのmark関数値の集合は， {[2, 5, 12], [1, 3, 12]}で，(4,6)と同型でないと判定されます．

しかし，次のふたつのグラフは，同型でないにもかかわらずmark関数リストの集合は同じです．

f:id:leichtrhino:20161015224447p:plain:w400 f:id:leichtrhino:20161015224439p:plain:w400

この問題は，次節の方法とこの方法を併用して解決します．

2.頂点間距離テーブル

初期状態で次数がd未満の頂点間の距離の表です．この表の総和を，同型判定に使います．例えば，このグラフの距離テーブルは，

f:id:leichtrhino:20161015224447p:plain:w400


	4	5	6	7	8	9
4	0	2	1	3	4	4
5	2	0	3	1	4	4
6	1	3	0	2	4	4
7	3	1	2	0	4	4
8	4	4	4	4	0	2
9	4	4	4	4	2	0

で，総和は92です．

また，このグラフの距離テーブルは，

f:id:leichtrhino:20161015224439p:plain:w400


	4	5	6	7	8	9
4	0	1	4	4	4	4
5	1	0	4	4	4	4
6	4	4	0	1	4	4
7	4	4	1	0	4	4
8	4	4	4	4	0	2
9	4	4	4	4	2	0

で，総和は104となり，先のグラフと同型でないと判定できます．

これらの考え方を使って，適切に枝刈りし，探索範囲を絞ります．

補足アンドメモ：高速に更新する実装（Python,NumPy）

辺(u,v)を追加したときのノードxy間の距離は，

$$ \textrm{new_distance}_{xy} = \textrm{min}( \textrm{distance}_{xu} + 1 + \textrm{distance}_{vy},\, \textrm{distance}_{xv} + 1 + \textrm{distance}_{uy},\, \textrm{distance}_{xy}) $$

で表されます．これを，NumPyを使ってPythonでも速くなるように実装しました．

def _apply_edge_to_dist(edge, nodes, distance_table):
    u, v = edge
    i, j = u - nodes[0], v - nodes[0] # ノード番号->テーブルの添字
    d_ij = distance_table[i, j]
    distance_table[i, j] = 1
    _tmp_distance_table = distance_table +\
                          np.transpose(distance_table)

    dist_xi = _tmp_distance_table[:, i].reshape((-1, 1))
    dist_jy = _tmp_distance_table[j, :]
    dist_xj = _tmp_distance_table[:, j].reshape((-1, 1))
    dist_iy = _tmp_distance_table[i, :]
    dist_ij = np.ones((distance_table.shape), dtype=int)
    dist_ji = dist_ij
    new_distance_table = np.minimum(
        distance_table,
        np.minimum(dist_xi + dist_ij + dist_jy,
                   dist_xj + dist_ji + dist_iy))

    distance_table[i, j] = d_ij
    return new_distance_table