方 1 AからBへの経路は, C地点を通る場合と通らない場合の 2つのバターンがある。 融点に最短経路で行くとき, 次のような道順は全部 「右の図のような格子状の道路網がある.A地点から 最短経路の問題2) 202 間のような格子状の道路網がある.A地点から B 何通りあるか C地点を通らない場合 C地点もD地点も通らない場合 D C よう A そこで,n(C)=n(U)-n(C) を利用して、 (Cを通らない道順)= (AからBへの全道順)-(Cを通る道順) と考える。 0 coD=CUD より, n(CND)=n(CUD)=n(U)-n(CUD) を利用。 (CもDも通らない道順)3D(AからBへの全道順)- (CまたはDを通る道順) ここで, n(CUD)=n(C)+n(D)-n(CnD)より, (CまたはDを通る)=(Cを通る)+(Dを通る)- (CかつDを通る) w ■ 1) A地点からB地点へのすべての道順は, B -=462 (通り) 6!5! B |AC C地点を通る道順は, 4! 6! 2!2! -=120 (通り) 3!3! よって, 求める道順は, (2) D地点を通る道順は, A 462-120=342 (通り) 3! 1!2! 7! C地点を通る道順 =105(通り) 4!3! (A→Aの道順) 4! 通り C地点かつD地点を通る道順は, 2!2! 4! -X 2!2! 2! 3! (A'→B'の道順)1通り -=36 (通り) 1!2! 第6 したがって, C地点またはD地点を通る道順は, 120+105-36=189(通り) 6! 通り 3!3! (B'→Bの道順) よって,求める道順は, Focus (1)より,C地点を通る道 順は 120 通り 462-189=273 (通り)