最適円順列を求めるアルゴリズムについて教えてください

質問

ExcelのVBAでプログラムを作っているのですが、ある問題で
　　つまづいてしまいました。

　　問題は、３０個のデータ（＃１～＃３０とします）を円順列で
　　並べます。　（＃１＝10とか＃１８＝24などの数値が入ります）
　　その場合の組み合わせは２９！通りありますよね

　　そして、この組み合わせそれぞれである計算をさせます。
　　（ベクトル計算のようなものです）
　　その答えのもっとも最適な結果（今回の場合最小）が出る
　　組み合わせを見つけ出したいのです。

　　最適結果を導き出すアルゴリズムをご指導下さいお願いします。

回答No.2

kaitou-man

データは円周上に等間隔で配置されるということでいいんですね？部分問題に分割できるなら分枝限定法や動的計画法の適用が考えられるんですが、どうも私にはうまい分割方法がわかりません。

むしろ、重心を中心になるべく近づけるという問題は、貪欲法でもうまくいきそうな気がします。この場合の貪欲法は、

1. まず適当にならべる。
2. すべてのデータのペアについて、それを交換したらどれだけ重心のずれが減るか求める。
3. どのペアを交換しても減らなければ終了。そうでなければ最もずれの減るペアを交換。
4. 2にもどる。

です。

もっとも、この方法で常に真の最適解が得られることを保証するには、ペアの交換では改善できなくて、3個以上のローテートで改善できるような例が存在しないことを証明しないといけませんが、私には荷が重いので他の方に譲ります。このカテゴリではなく数学あたりのカテゴリで、それなりのタイトルと定式化をすれば、回答があるかもしれません。

お礼

ありがとうございました。
回答していただいた内容から非常に
難しいことがよくわかりました
　本人もっと簡単に考えていました…(^^ゞ
ご指摘いただいたように、ほかのカテゴリで
質問してみます。

回答No.1

kaitou-man

29!通りの組み合わせのうち、最適なものをみつけたいということですね？

どんな計算をして最適かどうかを決定するかがわかりませんが、一般には効率のよい方法はありません。最悪の場合、しらみつぶしということになり、人類が存在するうちに計算が終わらないでしょうね。

その最適を判断する計算の内容によっては、効率のよい方法や近似的な方法があるかもしれません。計算内容や近似解の可否を補足してもらえれば、なんらかのアドバイスもできるかもしれませんが。

補足

そうですね、しらみつぶしに探すとなると非常に大変です。
計算する内容は、たとえば、それぞれのデータが重さだったとします
それを円形に並べた時に、それぞれの重さのバラつきによって重心が
円の中心からずれますよね、このずれが一番小さいものはどの組み合わせ
なのか見つけ出すというような問題です。
どうかよろしくお願いします。