砂漠の横断

砂漠の横断

【問題】
歩いて横断するのにＮ日間かかる砂漠があります。
探検家は何人かのポーターを連れて、この横断に挑戦します。
一人の持てる食料は最大四日分です。
さあ、何人のポーターを雇えばいいでしょう。
もちろん、遭難者は出してはダメですよ！
http://www.geocities.co.jp/Berkeley-Labo/6317/bouken.htm
[未菜実の数理パズル入門]より引用

【問題補足】
　問題にはかかれていない条件で、この種の問題でよく設定される条件として、食料を放置可能かという設定があります。
通常は盗賊などがいるので放置できないとされることが多いようです。ここでも放置禁止とします。
実際、未菜実さんの解答は放置禁止条件下での最少値が示されています。

　さらにここでは未菜実さんの解答と矛盾しない条件として、ポーターは１日単位で常に移動（前進｜後退）するとします。移動せず大量の食料を見張る手もありますが、複雑になるのと、留まると狙われやすい等と屁理屈をつけて禁止とします。
このため、下図に見えるように前進と後退のダイアグラムはチェッカーボード状になります。

　半日単位で動いた場合は、下図のようにＮ＝９の場合、最少値は１１人ではなく、少なくとも１０人になります。（最少かどうかは確かめていません。）

なお、この種の問題は兵站の問題としてよく出る問題です。簡単な例はとして
http://www.wing21.comlink.ne.jp/freetime/math/q0088.htmlなどがあります。

【解説】
　　必要最少限の人数を到着点から出発点に向けて決めて行きます。
下図（１）までは冒険家一人が前進します。到着５日前では食料が５必要で一人では運べませんからここにポーターが余分に一人必要です。この時ポータの帰りの分も含めると、食料は最低７日分必要ですが、２人なので８日分運ぶことも可能です。

　（２）の位置の場合、８日分運んだほうがポーターの数を減らすことができます。これはある位置に食料を運び上げる際、選択の余地がある場合に常に少ない方選ぶようすると、必要とするポーターの数のピークがその運び上げたい日付と同じところに来るからです。即ち、この場合は食料運び上げを前倒しして、ピークを分散させることができるからです。
　またそのことから、常に少ない方選ぶようする方法で最後まで求めた場合のポーター数がピークとなる日付より後では、前倒しをするとピーク値を上昇させるだけなので、前倒し（多いほう)の選択はするべきではありません。

　さらに、ポーター数ピークの日付の最も始めの日を通る４５度ラインより前日では、ピーク値への影響がないので、現在のピーク値を上回る可能性のある前倒しをするべきではありません。
　従って、下図の青３線で挟まれた間の食料運搬量の選択肢をしらみつぶしに探索することにより、最少値が得られると考えられます。
　以上何れも数学的証明ではなく、実験的事実の積み重ねによるものであり、絶対に最少かといわれると、実は怪しいことを断っておきます。

【Ｃ＋＋ソース】　
以上の考え方で探索するソフトを次に添付します。
ＶＣ＋＋　Console Applicationです。

【解答】
　以上の結果をＮ＝３週間まで求めました。結果は下表（最少ポーター数）です。
なお、合わせて５日前（２）のみ前倒しし、他は探索せずに全部食料の少ない方にした場合の結果を（近似最少ポーター数）として示します。Ｎが大きくなれば１％以下の誤差です。

Ｎ（日)	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
最少ポーター数	1	2	4	6	11	19	35	67	125	238	447	862	1640	3176	6086	11831	22802
近似最少ポーター数	1	2	4	6	11	19	36	68	126	241	454	868	1654	3195	6130	11897	22955
近似値誤差	1.0000	1.0000	1.0000	1.0000	1.0000	1.0000	1.0286	1.0149	1.0080	1.0126	1.0157	1.0070	1.0085	1.0060	1.0072	1.0056	1.0067

【結果詳細】
詳細なポーターと食料の動きは下記をご覧下さい。
Ｎ＝　　　５　６　７　８　９　１０　１１　１２　１３　１４　１５　１６　１７　１８　１９　２０　２１