本文へスキップ

最適とは その1Optimization




巡回セールスマン問題


JIMTOFなど大きな展示会の後などは特にそうなのですが、お越しいただいたお客様のフォローのため、ある程度まとまった件数を訪問しましょうよということになります。このとき、だれ彼をとわず締めのコメントは:

 
「ン、もっとも効率よく、効率よくね・・たのむよっ」







となるのはほぼ間違いありません。ご自身のキャリアで幾度となく聞いたであろうこの疑問をさしはさむ余地のない、まったくもって正論でありつつ、しかしながら結構な難問に内心「お、おぅ・・」と微妙に自分を励ますしかなかったご経験がおありでは?

ともかく気を取り直して、はたして最も効率のよい旅程ルートは?と先人の知恵を拝借してみるに、この問題を解き明かす手がかりとなるのが、「巡回セールスマン問題」なる「数学」の問題。もちろん「道徳」の問題ではありません。(巡回セールスマン問題、という意味ではありません。)シンプルな問い「複数の都市を巡回するのに最短のルートとなる旅程を組む」というもの。(最短のルート=移動コスト最小と考える)



きなのが、お客様が4箇所であれば3x2x1x1/2で3通り(逆周りも同じと考える。違うと考えれば6通り)で総当りでの距離比較計算が容易だったこの問題ですが、8箇所では(正逆ともカウントすれば)5040通りの組み合わせとなり、だんだん手におえなくなり、なんと32箇所では、8.22x10の33乗・・・・・の組み合わせとなり、これはこういったタスクに適任である知的タフネスの代表スーパーコンピュータをもってしても最短ルートの計算に数百兆かかるという事実・・・・・もちろん32枚のゲストカードを手にこのような説明で自分のスケジュールを正当化する方はいらっしゃいませんが。。。

この複雑な現実世界にあっては、めずらしいほど単純な想定、なおかつ解法が明確な問いでさえ、がくぜんとするほどの「不可能さ」を毅然と突きつけられてしまう、つまりいかなる単純作業でさえも最適な効率を求めることは多少の要素増大の前には、あえなく解読不能=実現不可能になってしまうようです。

それでは、「砥粒の種類」「砥粒の大きさ」「結合材の種類」「密度」「送りの速度」・・・・・加工条件でさえ数10種類の要素、さらにそれぞれに組み合わせが異なり、室温の変化、オペレータの違いなどの変動要因が加わる「精密加工」の最適化とは?・・・まさに「推して知るべし」です。巡回セールスマンの目的(旅程の最短化)とは比較にならない複数の要求を横目に、おそらく32拠点の旅程以上の項目を想定し、加えて納期という時間とにらめっこしながら最適を求めて格闘しなければならない。。たとえ単純なタスクでさえ、要素が増えるに従い、最適と言い切るにはスーパーコンピュータでもほぼ永遠に近い時間が必要になるかもしれないのに、です。(その2へ



バナースペース

エクストリーム株式会社

〒253-0105
神奈川県高座郡寒川町岡田3-22-16
TEL 0467-73-1425
FAX 0467-81-4836