京都大学 情報学研究科 知能情報学専攻 2024年8月実施 情報学基礎 F2-1

标签：

• Kyoto-University
• Shortest-Path-Problem
• Mandatory-Vertex-in-All-Shortest-Paths
• Set-Cover-Problem
• Greedy-Set-Cover
• Order-Sensitivity-of-Greedy-Algorithms

Author

itsuitsuki

Description (English)

Q.1

In the undirected graph shown below, the numbers attached to the edges represent their lengths. The edge length $x$ between nodes $a$ and $b$ is a positive real number. Among all paths between two nodes $s$ and $t$, those with the minimum total edge length are called the shortest paths between $s$ and $t$. The total edge length in a shortest path is referred to as the distance between $s$ and $t$. A path is represented as a sequence of nodes in which no node appears more than once.

(1) Derive the distance between $b$ and $j$, and identify all shortest paths, each represented as a sequence of nodes.

(2) Derive the condition on $x$ under which $b$ is included in all shortest paths between $a$ and $j$.

Q.2

Given a set $U = \{1, 2, \dots, n\}$ and a set $S = \{S_1, S_2, \dots, S_m\}$ where each $S_i$ is a subset of $U$, the set cover problem is to identify a set $\mathcal{C} = \{S_{c_1}, S_{c_2}, \dots, S_{c_k}\} \subseteq S$ with the minimum $k$ such that $S_{c_1} \cup S_{c_2} \cup \dots \cup S_{c_k} = U$ holds. Note that $n$ and $m$ are positive integers and it is assumed that $S_1 \cup S_2 \cup \dots \cup S_m = U$ holds. The following pseudo-code describes a greedy algorithm that computes an approximate solution to this problem.

Note that $\#(X)$, $\max(X)$, and $\min(X)$ denote the number of elements, the maximum element, and the minimum element of a set $X$, respectively. Note also that $X \setminus Y$ denotes the set difference, which is the set obtained by deleting the elements belonging to both $X$ and $Y$ from $X$. For example, $\{1, 3, 4, 5\} \setminus \{2, 3, 5\} = \{1, 4\}$ holds.

This algorithm may output different solutions even for the same $S$, depending on the ordering of their elements. For example, suppose that $U = \{1, 2, 3, 4, 5\}$ and $S = \{\{1, 3, 5\}, \{2, 4\}, \{2, 3, 5\}\}$. This algorithm outputs $\mathcal{C} = \{\{1, 3, 5\}, \{2, 4\}\}$ if $S_1 = \{1, 3, 5\}, S_2 = \{2, 4\}$, and $S_3 = \{2, 3, 5\}$, whereas it outputs $\mathcal{C} = \{\{2, 3, 5\}, \{2, 4\}, \{1, 3, 5\}\}$ if $S_1 = \{2, 3, 5\}, S_2 = \{2, 4\}$, and $S_3 = \{1, 3, 5\}$.

When considering all possible orderings of the elements of $S$ (i.e., all permutations of the elements of $S$) for given $U$ and $S$, among all solutions $\mathcal{C}$ outputted by this algorithm, let $A_{\min}(U, S)$ denote the cardinality of $\mathcal{C}$ with the smallest cardinality, and let $A_{\max}(U, S)$ denote the cardinality of $\mathcal{C}$ with the largest cardinality. Note that for the case of $(U, S)$ given above, $A_{\min}(U, S) = 2$ and $A_{\max}(U, S) = 3$ hold. Answer the following questions where reasons must be given for all answers.

(1) Let $U = \{1, 2, \dots, 10\}$ and $S = \{\{i, i+1\} \mid i = 1, 2, \dots, 9\}$. Derive $A_{\min}(U, S)$ and $A_{\max}(U, S)$.

(2) Let $U = \{1, 2, \dots, 100\}$ and $S = \{\{i, j\} \mid \text{all integers } i, j \text{ satisfying } 1 \le i < j \le 100\}$. Derive $A_{\min}(U, S)$ and $A_{\max}(U, S)$.

(3) Let $U = \{1, 2, \dots, 63\}$ and $S = \{\{i, 2i\}, \{i, 2i+1\} \mid i = 1, 2, \dots, 31\}$. Derive $A_{\min}(U, S)$.