情報科学と離散数学 大学課題

質問

画像は大学で出された課題なのですが、一ミリもわかりません。考え方と「経路を選んだ理由」の書き方の例を教えてください！出来れば専門用語的なのはなしでお願いします。

問
goal pointに到達した時の値の最大値を求　　める.
ただし、その経路(配布用紙)を添付し、その
経路を選んだ理由も述べること。

1. 左上のstart pointから右下のcheck pointを
経由して左上のgoal pointまで辺を通り進
む.
2. Startの時に初期値 1が与えられ, 辺を通る
ごとに辺に振られた演算を行った値に変化
する.
3. 各辺は2度通ることができない(頂点は2度
通ってよい).

回答No.2

maskoto · ベストアンサー

題意を、勘違いしてました

この問題は、コンピュータでプログラムを組んで、全数計算してやらなければ、なかなか大変だと思われます…

人間(貴方)が全数を計算しても良いですが
相当苦労しそうです…

そこで、以下の方針で経路を絞ってみると良いかも

高い持ち点に掛け算したほうが値がより大きくなる
移動の後半のほうが持ち点は高いはず
ということから、掛け算の辺を通過するのは
できるだけ後半に取っておく
この方針でルートを決めて行くのです

(逆算して、(1、-3)地点から、左、上、右、上、上、左と進んでゴールする経路だと
2倍、3倍を何度も行えて、高ポイントになることが予想されますから、スタート時はこの経路を避けるために、下、右、右と進み(2、-1)へ到達するのが最善かもしれません
また、チェックポイントを通過するときは
マイナス5→×3とするよりは、×3→マイナス5とする方が持ち点が高くなりますから
(3、-7)から右へ進んでチェックポイントを通過するのが最善と思われます
そして、×5が2箇所ありますが、これをより後半に通過するという方針から、チェックポイント通過後、×5の辺を通る、というのが良いと思われます。
これらを踏まえて、貴方自身でさらに細かいルートを考えて見てください

ちなみに、完全な正解が得られなくても、考え方があっていれば、それなりの部分点を与える…そう言うつもりでの出題なのかもしれませんね…)
〜以上参考まで〜

回答No.1

maskoto

解説の都合上
スタート地点を(0、0)
その真下の点を(0、-1)
ゴール地点を(4、-7)
と言うように、座標を設けます
そしたら、点を一つ移動することにする
各地点到達時の最大値をもとめると
当然ながら(0、-1)max＝1+5＝6
(1、0)max＝1×2＝2
これらを元に、更に一つ移動する時の各地点での最大値をもとめる
(0、-2)max＝6+4＝10
(2、0)max＝2+2＝4
(1、-1)については経路が２つある
(-1、0)を経由した場合は
(-1、1)＝(-1、0)max+2＝6+2＝8
もう一つの経路では
(-1、１)＝(0、１)max+3＝5
ゆえに、(-1、1)max＝8
→(-1、1)maxの値と経路を覚えておいて
(1、-1)に関しては、以後これを採用する

さらに1地点移動することを考える
ここまでと同じ要領で
(0、-3)max
(1、-2)max
などを求める
(1、-2)などは、この地点での最大値と
ここまでの経路を記憶しておく

さらに1地点移動
以下この繰り返してでゴール地点を目指し
ゴール地点での値の最大値を調べます

補足

(1、-1)までの最大値は8なんですか？一度(4、0)をまでいき(4、-1)を通って(1、-1)にいったら19になりませんか？