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

ExcelのVBAでプログラムを作っているのですが、ある問題で
　　つまづいてしまいました。
　
　　問題は、３０個のデータ（＃１～＃３０とします）を円順列で
　　並べます。　（＃１＝10とか＃１８＝24などの数値が入ります）
　　その場合の組み合わせは２９！通りありますよね

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

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

　　
　　　　　　　　　

No.2 ベストアンサー 回答者： kaitou-man 回答日時： 2003/02/06 11:50

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

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

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

です。

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

この回答へのお礼

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

お礼日時：2003/02/06 21:19

No.1 回答者： kaitou-man 回答日時： 2003/02/06 01:25

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

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

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

この回答への補足

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

補足日時：2003/02/06 07:09