wszystkie najkrótsze trasy

[NataliaAnna]

Na zajęciach przerabialiśmy poniższe zadanie, jednak wszystkie trasy wyznaczaliśmy ręcznie. Jest to jednak bardzo dużo roboty i zastanawiam się, czy istnieje szybszy sposób wyznaczenia takich tras(np jakiś wzór lub metoda)

Rozważmy kratę utworzoną z pięciu poziomych i czterech pionowych odcinków. Wyznacz wszystkie najkrótsze trasy z lewego górnego rogu do dolnego prawego roku tej kraty( ruch odbywa się jedynie w dół i w prawo)

[kerajs]

Każda trasa składa się z piecu odcinków w prawo P,P,P,P,P i czterech w dół D,D,D,D.
Ilość tras to ilość permutacji miedzy elementami P,P,P,P,P,D,D,D,D czyli: \(\displaystyle{ frac{9!}{5!4!}}\)


423490.htm

[pesel]

W prawo to będą chyba tylko trzy kroki.

[kerajs]

Ach, czyli chodzi o taką kratę!
\(\displaystyle{ \begin{tikzpicture}
\draw[red](0,0)--(3,0);
\draw[red](0,1)--(3,1);
\draw[red](0,2)--(3,2);
\draw[red](0,3)--(3,3);
\draw[red](0,4)--(3,4);
\draw[blue](0,0)--(0,4);
\draw[blue](1,0)--(1,4);
\draw[blue](2,0)--(2,4);
\draw[blue](3,0)--(3,4);
\end{tikzpicture}}\)
I o permutacje między elementami P,P,P,D,D,D,D których jest \(\displaystyle{ \frac{7!}{3!4!}=35}\)

Ja kratę z opisu zinterpretowałem całkowicie inaczej, bo tak:


\(\displaystyle{ \begin{tikzpicture}
\foreach \x in{0,1,...,3,4}
\foreach \y in{1,2,...,3,4}
{
\draw[](\x+0.1,\y-1)--(\x+0.9,\y-1);
\draw[](\x+1,\y-0.9)--(\x+1,\y-0.1);
}
\foreach \y in{0,1,...,2,3}
{
\draw[blue](0,\y+0.1)--(0,\y+0.9);
}
\foreach \x in{0,1,...,3,4}
{
\draw[red](\x+0.1,4)--(\x+0.9,4);
}
\end{tikzpicture}}\)