跳到主要内容

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

标签：

Author​

祭音Myyura, sure (#76956)

Description (English)​

Q.1​

We have the following weighted directed acyclic graph (DAG) that has seven nodes named . The weight of all edges is equal to 1.

(1) List all of the shortest paths from to .

(2) Answer the number of directed paths from to .

Suppose we have a simple connected weighted DAG with a set of nodes and a set of edges . The weight of all edges is equal to 1. For any node , let . Note that indicates an edge from to . We suppose is the only node whose is an empty set.

(3) For any node , let denote the number of paths from to , and let . Express using elements of .

(4) For any node , let denote the length of the shortest path from to , and let . Express using elements of .

Q.2​

Let be the set of all non-negative integers and . We define a total order of two elements in as if and only if or the rightmost non-zero component of is negative. For example, , , and .

For a given , consider the task of listing all elements in following the order , that is, listing all elements in as so that holds for all .

Both Algorithm 1 and Algorithm 2 on the next page are for accomplishing the task with a min-heap for keeping elements in , where "min" means minimum in the order . Note that "Insert into " means to insert into as its root and to maintain so that it keeps the heap property. Also, "Extract from " means to remove from and to maintain so that it keeps the heap property.

(1) Draw the heap of Algorithm 1 as a tree, not an array, obtained after executing the part ① for the case . Also illustrate step by step how is maintained in the first repetition of the while loop.

(2) Fill blank in Algorithm 2 so that the size of is no more than in the while loop.

(3) For the case , illustrate step by step how is maintained in the first and second repetitions of the while loop in Algorithm 2.

(4) Let . Explain the reason why Algorithm 2 with your answer for (2) works as requested.

Kai​

Q.1​

(1) A shortest path must use the edge , because reaching through requires at least edges.​

There are two length- paths from to :

(2) Number of directed paths from v1 to v7​

Let s(vi) denote the number of directed paths from v1 to vi. Set s(v1) = 1.

For every other vertex, sum the numbers of paths reaching its immediate predecessors:

s(v1) = 1
s(v2) = s(v1) = 1
s(v3) = s(v1) + s(v2) = 1 + 1 = 2
s(v4) = s(v2) + s(v3) = 1 + 2 = 3
s(v5) = s(v3) = 2
s(v6) = s(v4) + s(v5) = 3 + 2 = 5
s(v7) = s(v4) + s(v6) = 3 + 5 = 8

Hence, the number of directed paths from v1 to v7 is 8.

(3) General recurrence for the number of paths​

For any v ∈ V - {vs}, every path from vs to v must end with one incoming edge (v', v) where v' ∈ N(v). Therefore

s(v) = Σ_{v' ∈ N(v)} s(v').

with the base value

s(vs) = 1.

(4) General recurrence for the shortest-path length​

Since every edge has weight 1, a shortest path to v must come from one predecessor v' ∈ N(v) and then use one extra edge. Therefore

d(v) = 1 + min_{v' ∈ N(v)} d(v').

with the base value

d(vs) = 0.

Q.2​

The order ≼ compares triples by

  1. increasing k,
  2. then increasing j,
  3. then increasing i.

This is because the rightmost non-zero component is checked first.

(1) Heap of Algorithm 1 for N = 2​

The inserted elements are

(0,0,0), (1,0,1), (2,0,4),
(0,1,1), (1,1,2), (2,1,5),
(0,2,4), (1,2,5), (2,2,8).

A min-heap after part ① can be drawn as

                    (0,0,0)
                 /           \
           (1,0,1)           (2,0,4)
          /       \         /       \
     (0,1,1)   (1,1,2)  (2,1,5)   (0,2,4)
      /    \
 (1,2,5)  (2,2,8)

Now perform the first repetition of the while loop.

Step 1: extract the root (0,0,0) and move the last element (2,2,8) to the root.

                    (2,2,8)
                 /           \
           (1,0,1)           (2,0,4)
          /       \         /       \
     (0,1,1)   (1,1,2)  (2,1,5)   (0,2,4)
      /
 (1,2,5)

Step 2: compare (2,2,8) with its children and swap with the smaller child (1,0,1).

                    (1,0,1)
                 /           \
           (2,2,8)           (2,0,4)
          /       \         /       \
     (0,1,1)   (1,1,2)  (2,1,5)   (0,2,4)
      /
 (1,2,5)

Step 3: compare (2,2,8) with its children and swap with (0,1,1).

                    (1,0,1)
                 /           \
           (0,1,1)           (2,0,4)
          /       \         /       \
     (2,2,8)   (1,1,2)  (2,1,5)   (0,2,4)
      /
 (1,2,5)

Step 4: compare (2,2,8) with its child (1,2,5) and swap once more.

                    (1,0,1)
                 /           \
           (0,1,1)           (2,0,4)
          /       \         /       \
     (1,2,5)   (1,1,2)  (2,1,5)   (0,2,4)
      /
 (2,2,8)

This is the heap after the first extraction.

(2) Fill in the blank of Algorithm 2​

After extracting (i', j', (i')^2 + (j')^2), the next candidate with the same j' should be the successor in the same sorted list for fixed j'. Therefore the blank is

(i' + 1, j', (i' + 1)^2 + (j')^2)

(3) Algorithm 2 for N = 2​

Initial heap after the for every j from 0 to N part:

        (0,0,0)
       /       \
  (0,1,1)   (0,2,4)
First repetition​

Extract the root (0,0,0).

Move the last element (0,2,4) to the root:

        (0,2,4)
       /
  (0,1,1)

Heapify down by swapping with (0,1,1):

        (0,1,1)
       /
  (0,2,4)

Since i' = 0 < 2, insert

(1,0,1).

After insertion and heap maintenance:

        (1,0,1)
       /       \
  (0,2,4)   (0,1,1)
Second repetition​

Extract the root (1,0,1).

Move the last element (0,1,1) to the root:

        (0,1,1)
       /
  (0,2,4)

This already satisfies the heap property.

Since i' = 1 < 2, insert

(2,0,4).

After insertion:

        (0,1,1)
       /       \
  (0,2,4)   (2,0,4)

This is the heap after the second repetition.

(4) Why Algorithm 2 works​

For each fixed j, define the sequence

Lj = (0, j, j^2), (1, j, 1 + j^2), ..., (N, j, N^2 + j^2).

For fixed j, this sequence is already sorted by ≼, because the third component i^2 + j^2 strictly increases as i increases.

Algorithm 2 initially inserts only the first element of each sequence Lj, so the heap size is exactly N + 1.

Whenever the minimum element (i', j', (i')^2 + (j')^2) is extracted, the only new candidate from the same sequence that can possibly come next is

(i' + 1, j', (i' + 1)^2 + (j')^2),

and this successor is inserted only if i' < N.

Therefore:

  • at any moment the heap contains at most one not-yet-output candidate from each Lj;
  • the heap size is never more than N + 1;
  • the root of the heap is always the smallest not-yet-output element in all of S_N.

Hence Algorithm 2 is exactly a k-way merge of the N + 1 sorted sequences L0, L1, ..., LN, so it outputs all elements of S_N in the required order.

目录