いろいろ【まっち】んぐ

今日も土曜の休日出勤、終わりました。　でも　全部出来なかった。　ま　はじめからわかってたけど・・・　なので、月曜日の祭日も休日出勤です。　客先からメールも来てたし・・・

で、業務多忙のため、お返事、ご訪問コメが遅れております。　ご容赦！

まあ　世の中　不景気の様子なのに、仕事のあることはいいことです。　しかし、不景気なんかどこ吹く風　という人もいますが・・・　うらやましい限りですね。

ま　「うれし恥ずかし」で書いたように、自分だけ、家族だけ良ければいい　と言う風潮ですから・・・　自分が一番、家族が二番、他人は見て見ぬふり！　家庭が成り立たない人は仕事もできない。　

はいはい、アンタの言うことがすべて正しいんですよ。　それ以外の人は「バカ」
あ　「バカ」って言ったらいけないんだっけ！　これまた　しっつれいしました～

アンタが大将、アンタがすべて！
　「アンタが大将」←クリック

でも　日本全国、いや　全世界の家庭を守れなかった方々、これ　見たら傷つくだろーな。　あなたたちだって懸命にがんばったんだよね。　なんと「思いやり」のない表現だろーか。

　　-------------------------------------------------------------
日本経済新聞社が5日まとめた「社長100人アンケート」によると、国内景気が「悪化している」との回答が9割を超え、前回調査(6月)の3倍に急増した。株価急落を受け3日に実施した緊急質問では、米金融危機で自社の経営に「すでに悪影響が出ている」との回答が6割近かった。

同時に実施した「地域経済500調査」でも回答者の8割が景気は「悪化」していると答えた。

社長100人アンケートは国内主要企業の社長(会長、頭取などを含む)を対象に9月下旬までに実施、139社から回答を得た。　緊急質問は114社から、地域500は地元有力企業や事業所、団体のトップ408人から回答を得た。

社長100人では国内景気の現状認識として「悪化に転じた」「緩やかながら悪化している」「急速に悪化している」のいずれかを選んだ経営者が93.5％に達した。

「拡大している」は2004年の調査開始以来、初めてゼロになった。　前回は10.6％だった。(2008年10月06日 日本経済新聞)
　　-------------------------------------------------------------

麻生内閣、どこまで景気対策をやってくれるのか、お手並み拝見　ですな。　手始めに議員報酬の大巾ダウン　なんてのはいかがでしょうか？(絶対　やらんだろーな！)

公務員、それに準じる公社、公団、そして　民営化になったとはいえ、元官庁某企業、病院、学校などは景気に関係なく、給与、ボーナスが出ますからねぇ～(すべての部門ではないですが・・・)

まあ　あまり期待しないほうがいいようです・・・


ところで、「総当り方式」という計算方法をご存知ですか？

「巡回セールスマン問題」とも言われています。


ということで、本日のお題　「総当り方式」
尚、昨日のお題は　「おかず、ご飯」←ご覧になってない方はこちらもどうぞ


例えば、今　訪問すべき得意先が3軒の場合を考えてみます。


　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　1　　　　　　　　　　　　　1　　　　　　　2　　　　　　　
　　　選択肢は3　　　　　　　選択肢は2　　　　　　　　選択肢は1


最初に訪問する得意先は3軒の内の1軒ですから、3通りの選択肢があります。
2番目の訪問先は残った2軒のうちのどちらかになります。
選択肢は2になります。

3番目の訪問先は残された最後の1軒です。　選択肢は1です。

したがって巡回経路の数は、3x2x1＝6 ですから、全部で6通りあります。 　しかし、3軒の得意先をそれぞれA、B、C とすると、 巡回経路は A-B-C、A-C-B、B-A-C、B-C-A、C-A-B、C-B-A　の6種類です。

この中にはそれぞれ逆回りコースが含まれているため、 距離だけを考えるなら　(3x2x1)÷2＝3　でいいことになります。

訪問先が4軒ある場合は、(4x3x2x1)÷2＝12通り、 訪問先が5軒の場合は、(5x4x3x2x1)÷2＝60　通りの巡回経路があります。

このような、n x (n-1) x (n-2) x ・・・ x 2 x 1　という計算は、n！　と書き、「階乗」といいます。

訪問先が3軒の場合は 3！/2 ＝ 3通り、4軒の場合は 4！/2 ＝ 12通り、5軒場合は　5！/2 ＝ 60通りです。

コンピュータでこのような問題を解く場合、しばしば、すべての巡回経路の長さを計算して、 いちばん短かいものを選ぶという、総当たり式プログラムを作ります。

バカバカしいようですが、コンピュータは圧倒的な早さで計算し、疲れも知らず、プログラムは単純で、しかも結果が確実だからです。

では、訪問先が32軒の場合、何通りの巡回経路の長さを計算すればいいでしょうか？

この問題では、すでに１軒目の訪問先にいることになっているので、31！/2 でいいことになります。 これを計算すると、

31！＝ (31x30x29x ・・・ x4x3x2x1)/2 ≒ 4.11x10の33乗　通りになります。

これを「巡回セールスマン問題」と言います。
前回「赤い糸」で、同じ誕生日のいる人の確率を計算しましたが、これも同じ原理です。

このように「巡回セールスマン問題」が難問である理由は、その膨大な計算量にあります。

この計算をするのにはとうてい手計算ではできません。　当然　コンピュータを使いますが、この計算をするのにどれだけの時間がかかるでしょうか？

これ以上　計算式を書くと頭痛がする人もおられるかもしれませんので、省略して答えだけを・・・

32軒の巡回経路の長さを1秒間に1兆回 計算できるスーパーコンピュータでやったとして、 4.11 x 10の21乗　秒が必要です。

1年は　3.15 x 10の7乗　秒ですから、130兆年 かかることになります。

現在のコンピュータで、このような問題を総当たり方式で解くことは とうてい不可能なのです。

もちろん、近い将来、もっと高性能のコンピュータや、このような問題をまったく別の方法で、 短時間のうちに解いてしまうコンピュータが出現する可能性はあります。
　
しかし、それでも、コンピュータに巡回セールスマン問題を解かせたい場合があります。

これを使う例としては、コンピュータなどに使われているプリント基板には数千個もの小さい穴を開けなくてはなりません。

もちろん超高速の専用の機械を使いますが、穴は原則的に1個or数個づつドリルで開けます。　どういう順序で開けていくと、ドリルの移動時間を最短にできるかという問題は、この「巡回セールスマン問題」そのものなのです。

穴は数千個もありますから、コンピュータの総当り方式は論外です。　人間は直感的に効率的な経路を判断できますが、 何千箇所もの加工経路を指示するという単純作業は苦手です。　それに1箇所でも忘れると大変なことになります。

一般的には、コンピュータで近似解を求める方法が採られています。　必ずしも最短でなくてもいいから、できるだけそれに近いものを短時間で求めるために、様々な工夫がされています。


大切な命を守るためにご覧頂けると幸いです。　
　


<オマケ>　シリーズ化してしまった懐メロ　今日も運動会特集
「トランペット吹きの休日」、「クシコスポスト」、「ワシントンポスト」



なぜか大学からアクセスの多い別ブログ　　まったく更新してませんが・・・
●別ブログ9/10の新着は「北野・異人館街」
　　　　　　　　　　　前回は「A. KY」　こちらも見てね