「最高のカレーを作れ」問題 https://codeiq.jp/ace/yuki_hiroshi/q210
面白いです。別の例に例えると、128人の集団を２つの組に分けます。仲のいいペアは、なるべく同じ組になるようにしたい、という問題。
128個の粒子を用意して、仲のいい同士が引き合い、それ以外は反発するようにして動かすと以下のようになりました。
なんとそういう設問でしたか。集団を二つに切るなら、左の太線で切れば11組の好き同士を分断するだけで済みます。これがおそらく最適解。右が12本でわずかに違うところが絶妙。
確実に最適解を求めるアルゴリズムも、複雑だけどあります。以前の自分の日記から引用
最大流/最小切断定理
たとえば東京都内から筑波に人が一斉に移動するというシチュエーションを考える。東京に核ミサイルが落ちてきて筑波にシェルターがあるとか。このとき何時間で避難可能か、という問題を解くには可能な東京から筑波への最大「流量」を求める必要がある。都内でいくら道路が広くても利根川あたりで橋が少なくて橋の交通量の合計が例えば車１００台/分だったらこれ以上の交通量が発生しないように都内で規制しないと渋滞になってしまう。ほかにボトルネックがない場合にはこの「車１００台/分」が求める最大流量となる。つまり出発点とゴールを分断する線をいろいろ引いてそれを横断する道路のキャパシティの合計を計算したとき、あらゆる線の引き方のうちでキャパシティが最小になる引き方のキャパシティ（最小切断）が最大の流量を与える。最大流を求める多項式時間のアルゴリズムが存在するので、逆に最小切断の問題は最大流の問題に置き換えて多項式時間で解くことが出来る。
このパワポが面白いです: http://www.c.csce.kyushu-u.ac.jp/~makiyama/rinkou/KINJI/kinji4.ppt
現在最速のアルゴリズムは以下で実装されているようです。
Hao-Orlin アルゴリズムのC++クラス: http://lemon.cs.elte.hu/pub/doc/0.6/a00225.html
