SDSC6007 - Assignment 1

#assignment #sdsc6007

Question 1

Ash Ketchum is preparing his next trip and packing up. His backpack has maximum weight capacity is z and he wants to fill it up with different quantities of N different items. Denote

• $v_{i}$ : the value of the i th type of item

• $w_{i}$ : the weight of i th item

• $x_{i}$ : the number of items of type i that are loaded in the backpack
  Ash Ketchum is trying to maximize the total value of all the items in his backpack, i.e. to maximize $\sum_{i=1}^{N} x_{i} v_{i}$ subject to the constraints $\sum_{i=1}^{N} x_{i} w_{i}\leq z$ and $x_{i}=0,1,\ldots$ Formulate this problem and state the corresponding DP algorithm. P.S. You don’t need to solve the problem.

Answer:

For the problem:

$$\begin{aligned} \text{maximize} \quad & \sum_{i=1}^{N} x_{i} v_{i} \\ \text{subject to} \quad & \sum_{i=1}^{N} x_{i} w_{i} \leq z, \\ & x_{i} \in \mathbb{N} \quad \forall i = 1, 2, \ldots, N, \end{aligned}$$

1. Definition:

   • $V(c)$ is the maximum total value when the backpack has remaining capacity $c$ ($c = 0, 1, \ldots, z$).
   • For $c = 0$, $V(0) = 0$
   • For $c > 0$, initially set $V(c) = 0$ (assuming non-negative value).

2. Establish the Bellman equation

   • For each capacity $c$ from 1 to $z$, compute:

     $$V(c) = \max_{\substack{i=1,\ldots,N \\ w_i \leq c}} \left\{ v_i + V(c - w_i) \right\}$$

     If all $w_i > c$, then $V(c) = 0$.

Thus, the maximum total value is $V(z)$.

Question 2

Ash Ketchum is currently staying in Hong Kong in order to capture a unique fierce creature,“Klint”; unfortunately, he run out of money and now he has to work in an inn to save up for the next trip. Everyday, he charges a different rate of a room as the day progresses, depending on the number of vacancies. His salary is proportional to the income during the day, and so his objective is to maximize the expected total income during the day. Denote

• x: the number of empty rooms at the start of the day

• y: the number of customers that will ask for a room during the day

After taking SDSC8004 during his free time, Ash Ketchum becomes a genius in statistics, and he now knows y with certainty. Upon arrival of a customer, Ash Ketchum quotes one of m prices $r_{i}$ $i=1,\ldots m$ , where $0<r_{1}\leq r_{2}\leq\cdots\leq r_{m}$ . A quote of a rate $r_{i}$ is accepted with probability $p_{i}$ and is rejected with probability 1-p2, in which case the customer departs, never to return during that day. Formulate this problem and state the corresponding DP algorithm. P.S. You don’t need to solve the problem.

Answer

1. Define the state space and transition policy:

• State: remaining number of empty rooms $s$ ($0 \leq s \leq x$) and remaining number of customers $k$ ($0 \leq k \leq y$)

• Decision: for each customer, quote a price $r_i$ ($i = 1, \ldots, m$)

• State transition:

  • If the quote $r_i$ is accepted (probability $p_i$): gain income $r_i$, state updates to $(s-1, k-1)$
  • If rejected (probability $1-p_i$): income 0, state updates to $(s, k-1)$

2. Define the optimal value function:

   • $V(s, k)$ = maximum expected total income when there are $s$ empty rooms and $k$ customers remaining

3. Boundary conditions:

   • $V(s, 0) = 0$ (no customers, income is 0)
   • $V(0, k) = 0$ (no empty rooms, income is 0)

4. Establish the Bellman equation (for $s \geq 1$, $k \geq 1$):

   $$V(s, k) = \max_{i=1,\ldots,m} \Big\{ p_i \cdot \left[ r_i + V(s-1, k-1) \right] + (1-p_i) \cdot V(s, k-1) \Big\}$$

The maximum expected total income is $V(x, y)$

Question 3

Find a shortest path from each node to node 6 for the graph of Figure 1 by using
the DP algorithm manually.

Answer

Iteration	Node	Open	1	2	3	4	5	6
0	-	6	$+\infty$	$+\infty$	$+\infty$	$+\infty$	$+\infty$	0
1	6	1, 3, 4, 5	8(P=6)	$+\infty$	9(P=6)	2(P=6)	5(P=6)	0
2	1, 6	3, 4, 5	8(P=6)	$+\infty$	9(P=6)	2(P=6)	5(P=6)	0
3	1, 3, 6	4, 5	8(P=6)	$+\infty$	9(P=6)	2(P=6)	5(P=6)	0
4	1, 3, 4, 6	2, 5	7(P=4)	3(P=4)	9(P=6)	2(P=6)	5(P=6)	0
5	1, 2, 3, 4, 6	5	7(P=4)	3(P=4)	9(P=6)	2(P=6)	5(P=6)	0
6	1, 2, 3, 4, 5, 6	-	7(P=4)	3(P=4)	9(P=6)	2(P=6)	5(P=6)	0

• State definition: $J_k(i)$ represents the minimum cost from node $i$ to the target node $t$ with remaining $k$ steps.

• Initialization ($k=0$): $J_0(t) = 0$ (target node cost is 0), $J_0(i) = \infty$ ($i \neq t$, meaning unreachable).

• Recurrence relation ($k \geq 1$):

  $$J_k(i) = \min_{j \in \text{neighbor nodes}} \left\{ a_{ij} + J_{k-1}(j) \right\}$$

• Convergence condition: stop when $J_k(i)$ does not change for all $i$ (converges within $k = N-1$ steps, where $N$ is the number of nodes).

1. $k=0$:

• $J_0(6) = 0$

• $J_0(i) = \infty$ for $i = 1,2,3,4,5$

2. $k=1$:

Compute $J_1(i) = \min_j \{ a_{ij} + J_0(j) \}$:

• $J_1(1)$: edge to 6 $\to$ $\min\{8 + 0\} = 8$ (path: $1 \to 6$)

• $J_1(2)$: no edge to 6 $\to$ $\infty$

• $J_1(3)$: edge to 6 $\to$ $\min\{9 + 0\} = 9$ (path: $3 \to 6$)

• $J_1(4)$: edge to 6 $\to$ $\min\{2 + 0\} = 2$ (path: $4 \to 6$)

• $J_1(5)$: edge to 6 $\to$ $\min\{5 + 0\} = 5$ (path: $5 \to 6$)

• $J_1(6) = 0$
  Result: $J_1 = [1:8, 2:\infty, 3:9, 4:2, 5:5, 6:0]$

3. $k=2$:

Compute $J_2(i) = \min_j \{ a_{ij} + J_1(j) \}$:

• $J_2(1)$: edges to 2,3,4,6 $\to$ $\min\{4 + \infty, 1 + 9, 5 + 2, 8 + 0\} = \min\{\infty, 10, 7, 8\} = 7$ (path: $1 \to 4 \to 6$)

• $J_2(2)$: edge to 4 $\to$ $\min\{1 + 2\} = 3$ (path: $2 \to 4 \to 6$)

• $J_2(3)$: edges to 5,6 $\to$ $\min\{5 + 5, 9 + 0\} = \min\{10, 9\} = 9$ (path: $3 \to 6$)

• $J_2(4)$: edge to 6 $\to$ $\min\{2 + 0\} = 2$

• $J_2(5)$: edges to 3,6 $\to$ $\min\{0 + 9, 5 + 0\} = \min\{9, 5\} = 5$ (path: $5 \to 6$)

• $J_2(6) = 0$
  Result: $J_2 = [1:7, 2:3, 3:9, 4:2, 5:5, 6:0]$

4. $k=3$:

Compute $J_3(i) = \min_j \{ a_{ij} + J_2(j) \}$:

• $J_3(1)$: edges to 2,3,4,6 $\to$ $\min\{4 + 3, 1 + 9, 5 + 2, 8 + 0\} = \min\{7, 10, 7, 8\} = 7$ (path: $1 \to 4 \to 6$ or $1 \to 2 \to 4 \to 6$)

• $J_3(2)$: edge to 4 $\to$ $\min\{1 + 2\} = 3$

• $J_3(3)$: edges to 5,6 $\to$ $\min\{5 + 5, 9 + 0\} = \min\{10, 9\} = 9$

• $J_3(4)$: edge to 6 $\to$ $2$

• $J_3(5)$: edges to 3,6 $\to$ $\min\{0 + 9, 5 + 0\} = \min\{9, 5\} = 5$

• $J_3(6) = 0$
  Result: $J_3 = [1:7, 2:3, 3:9, 4:2, 5:5, 6:0]$ (same as $k=2$, converged)

Optimal results

• Node 1 $\to$ 6: minimum cost 7 (path: $1 \to 4 \to 6$ or $1 \to 2 \to 4 \to 6$)

• Node 2 $\to$ 6: minimum cost 3 (path: $2 \to 4 \to 6$)

• Node 3 $\to$ 6: minimum cost 9 (path: $3 \to 6$)

• Node 4 $\to$ 6: minimum cost 2 (path: $4 \to 6$)

• Node 5 $\to$ 6: minimum cost 5 (path: $5 \to 6$)

• Node 6 $\to$ 6: minimum cost 0

Question 4

Find a shortest path from node 1 to node 5 for the graph of Figure 2 by using (any) label correcting method manually.

Label correcting algorithm calculation table

Iteration	Node	Open	1	2	3	4	5
0	-	1	0	$+\infty$	$+\infty$	$+\infty$	$+\infty$
1	1	2,3	0	2(P=1)	2(P=1)	$+\infty$	$+\infty$
2	1, 2	3,4,5	0	2(P=1)	2(P=1)	3(P=2)	2(P=2)
3	1, 2, 3	4,5	0	2(P=1)	2(P=1)	3(P=2)	2(P=2)
4	1, 2, 3, 4	5	0	2(P=1)	2(P=1)	3(P=2)	2(P=2)
5	1, 2, 3, 4, 5	-	0	2(P=1)	2(P=1)	3(P=2)	2(P=2)

Question 5.(a)

Confirm your answer in Question 3 by using Python to solve the shortest path problem. Please submit your Python code as part of your submission. You can submit either a .py or a .txt file. If you are using other formats, you can copy and paste your code to a .txt file for submission.

def shortest_path_to_destination(graph, destination, max_steps=5):
    nodes = set(graph.keys()) | {destination}
    max_steps = len(nodes)
    J = {node: float('inf') for node in nodes}
    J[destination] = 0  # Target node cost is 0

    # Reverse iteration (k = 0,1,...,N-1)
    for k in range(max_steps):
        updated = False
        J_next = J.copy()  # Save current state

        for node in nodes:
            if node == destination:
                continue

            # Traverse all neighbor nodes, update minimum cost
            min_cost = float('inf')
            for neighbor, weight in graph.get(node, {}).items():
                if J[neighbor] != float('inf'):  # Ensure neighbor is reachable
                    candidate = weight + J[neighbor]
                    if candidate < min_cost:
                        min_cost = candidate

            # Update minimum cost
            if min_cost < J_next[node]:
                J_next[node] = min_cost
                updated = True

        J = J_next
        if not updated:
            break

    return J

graph = {
    1: {2: 4, 3: 1, 4: 5, 6: 8},
    2: {4: 1},
    3: {5: 5, 6: 9},
    4: {6: 2},
    5: {3: 0, 6: 5},
    6: {}
}

destination = 6
shortest_costs = shortest_path_to_destination(graph, destination)
print("Shortest path cost from each node to target node 6:")
for node in sorted(shortest_costs.keys()):
    print(f"Node {node} → 6: {shortest_costs[node]}")

Output:

Shortest path cost from each node to target node 6:
Node 1 → 6: 7
Node 2 → 6: 3
Node 3 → 6: 9
Node 4 → 6: 2
Node 5 → 6: 5
Node 6 → 6: 0