複数都市を一番安く巡るには、どうすればいいか?

身の回りを見渡すと、日常は不思議なほどに美しい「数」の法則にあふれている。そんな「日常にひそむ うつくしい数学」を、京都大学物理学専攻の著者が、小学生でもわかる平易な文章で解説。難しい数式は読み飛ばしても大丈夫。本連載は「日常にひそむ うつくしい数学」(朝日新聞出版)よりお届けいたします。

複数都市を一番安く巡るには、どうすればいいか?


サラリーマンの仕事の中でも、営業職は、とりわけノルマが厳しい職種です。今月いくつの企業を訪問して、 何件契約を取ったのか?それによって、営業部長が天使になったり、悪魔になったりします。

昨今では、「ブラック企業」という言葉が定着しつつあるように、あまりに過酷な労働環境は是正される方向へ社会が動いているようですが、未だに昭和の価値観を持つ熱血上司は、今日も日本のどこかで部下を叱咤激励していることでしょう。

さてここで、ちょっとした思考遊びをしてみましょう。ここは、とあるブラック企業のオフィスです。営業部員の冨島さんは、残業を終えて帰ろうとしたところ、とつぜん営業部長に呼び出されました。そして、明日の始発で家を出て、20カ所の都市を回って在庫商品を売ってこい。それまでは家にも会社にも帰ってくるな!もちろん、交通費はお前の自腹だと言われてしまいました。

妻に財布を握られている冨島さんは、自分のお小遣いの中から交通費を捻出して、20 都市を回らなければなりません。 冨島さんを助けるつもりで、最小の交通費でミッションを達成する方法を一緒に考えていきましょう。ここでは、状況を簡単にするために、交通費は移動距離に比例すると考えます。

つまり、同じ距離を飛行機で移動するのか、新幹線で移動するのかといった違いによらず、単純に移動距離に比例して交通費が増えていくことにします。そうすると、交通費を最小限に抑えるためには、20都市全てを最短距離で1回ずつ訪問できればよいことになります。このように、複数の都市を最短距離で1回ずつ訪問する方法を求める問題を「巡回セールスマン問題」と呼びます。

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

この連載について

初回を読む
日常にひそむうつくしい数学

冨島佑允

身の回りを見渡すと、日常は不思議なほどに美しい「数」の法則にあふれている。知っているようで知らなかった日常の不思議。身の回りに隠された数の神秘。そんな「日常にひそむうつくしい数学」を、京都大学物理学専攻の著者が、小学生でもわかる平易な...もっと読む

この連載の人気記事

関連記事

関連キーワード

コメント

PagannPoetry 複数都市を巡って、一番交通費を浮かせるにはどうすればいいのか問題。今回は冨島さんの文章が面白すぎる…! https://t.co/WNvA6xIZQF 3ヶ月前 replyretweetfavorite