Options

Exercise 15 - Chapter 4

Fill out the \(\textbf{Cost}\)-matrix:

$$ \begin{array}{c | c c c} \Phi & x & y & z \\ \hline A & ? & ? & 20 \\ B & 11 & ? & ? \\ C & ? & 17 & ? \\ D & ? & ? & ? \end{array} $$ Previous Next

$$ \textbf{Cost}\text{-profunctor } \Phi : X \nrightarrow Y $$ drawing

Comments

  • 1.

    $$ \begin{array}{c | c c c} \Phi & x & y & z \\ \hline A & 17 & 20 & 20 \\ B & 11 & 14 & 14 \\ C & 14 & 17 & 17 \\ D & 12 & 9 & 15 \end{array} $$ One way to compute this is to form a cost matrix (the same as an adjacency matrix, except with the costs in each entry where the identity counts as 0 and no link counts as \(\infty\)). Taking matrix products using tropical mathematics (sum instead of product and min instead of sum), one can find the least cost to go between two points in a specified number of link traversals. After finitely many powers, the matrix ceases to change on taking higher powers. At this point, one has a matrix containing the minimum cost to travel between two nodes regardless of the number of links traversed.

    For this particular system, two properties are helpful. One is that there are no links from \(\mathcal{Y}\) to \(\mathcal{X}\), so the corresponding part of the matrix is always \(\infty\). The other is that there is a minimum non-zero entry in the matrix (i.e., a minimum cost for traversing a link). This means that once an entry is less than or equal to the minimum cost times the number of powers of the matrix taken, it cannot change under taking higher powers.

    Comment Source:\[ \begin{array}{c | c c c} \Phi & x & y & z \\\\ \hline A & 17 & 20 & 20 \\\\ B & 11 & 14 & 14 \\\\ C & 14 & 17 & 17 \\\\ D & 12 & 9 & 15 \end{array} \] One way to compute this is to form a cost matrix (the same as an adjacency matrix, except with the costs in each entry where the identity counts as 0 and no link counts as \\(\infty\\)). Taking matrix products using tropical mathematics (sum instead of product and min instead of sum), one can find the least cost to go between two points in a specified number of link traversals. After finitely many powers, the matrix ceases to change on taking higher powers. At this point, one has a matrix containing the minimum cost to travel between two nodes regardless of the number of links traversed. For this particular system, two properties are helpful. One is that there are no links from \\(\mathcal{Y}\\) to \\(\mathcal{X}\\), so the corresponding part of the matrix is always \\(\infty\\). The other is that there is a minimum non-zero entry in the matrix (i.e., a minimum cost for traversing a link). This means that once an entry is less than or equal to the minimum cost times the number of powers of the matrix taken, it cannot change under taking higher powers.
Sign In or Register to comment.