quiz : 解答編 : Concurrent Clean : 思考の軌跡

プログラミング

まず、最初にトライしたのは「incremental」な手法でした。
２頂点までは自明なグラフになるので、最初の２頂点をそのように決め、そこから先は頂点を１つずつ増やしていくという方向で頂点を追加するときのグラフの変換パターンを探したのですが・・・
グラフがツリーならすぐに解けるのですが、複雑なグラフはちょっと無理でした。
で、次にトライしたのは「緩和法」的な手法でした。
条件を少し緩めて、「辺が頂点に重ならなければよい」という条件にすると、次のように頂点を並べる解が自明解になります。（左下の三角形に辺が集中します）

1
 2
  3
   4
    ..

これを初期値として、先に頂点の上下の位置を適切な位置に再配置して、その後、各頂点を左寄せするという方法を考えました。
ここでの肝は、頂点の上下の配置をどうやって決めるかということで、前後の頂点との関係のパターンであれこれ考えていったのですが、最初は上手くいきそうだと思っていたものの、あれこれ考えていくうちにパターンが複雑になっていって、断念。
しかし、頂点の上下の位置にさえ注目すればよいというアイデアは採用できそうなので、そこに焦点を絞って別のアイデアを探すことに。
最終的に、「探索」と「ラベル付け」という、いかにもアルゴリズムな方法でいけるということに気づいて、実装。私は、コードを短くする趣味はないので、これにて終了。