140 lines
3.9 KiB
Markdown
140 lines
3.9 KiB
Markdown
|
---
|
|||
|
|
date: 11.09.2024
|
|||
|
|
type: theoretical
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
|
|||
|
|
**travelling salesperson**
|
|||
|
|
|
|||
|
|
## Definition
|
|||
|
|
- Approach to design algorithms
|
|||
|
|
- Optimal solution in polynomial time
|
|||
|
|
- Usually used alongside [Divide and Conquer](Divide%20and%20Conquer.md)
|
|||
|
|
- Used to better the time [complexity](Complexity.md), but usually worsens the space complexity
|
|||
|
|
|
|||
|
|
|
|||
|
|
### How do we create a DP soluton?
|
|||
|
|
- Characterize optimal solution
|
|||
|
|
- Recursively define the value of an optimal solution
|
|||
|
|
- Compute the value
|
|||
|
|
- Construct an optimal solution **from the computed information**
|
|||
|
|
|
|||
|
|
## Problem discussion
|
|||
|
|
|
|||
|
|
### Calculating Fibonacci numbers
|
|||
|
|
|
|||
|
|
- Recursion is extremely bad -> PF was wrong
|
|||
|
|
- Because the branches are too many
|
|||
|
|
- We compute f(x) where f(x) has already been computed
|
|||
|
|
- Memoization!
|
|||
|
|
|
|||
|
|
|
|||
|
|
#### Approaches
|
|||
|
|
- Linear time $\mathcal{O}(n)$ - **Bottom to top**
|
|||
|
|
```pseudo
|
|||
|
|
F[0] = 1
|
|||
|
|
F[1] = 1
|
|||
|
|
for i in {2, .., n} do
|
|||
|
|
F[i] = F[i − 1] + F[i − 2]
|
|||
|
|
end for
|
|||
|
|
return F[n]
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Compute the entire array and just return the result.
|
|||
|
|
|
|||
|
|
- Memoization $\mathcal{O}(n)$ - **Top to bottom**
|
|||
|
|
```javascript
|
|||
|
|
function fibMemo(index, cache) {
|
|||
|
|
cache = cache || [];
|
|||
|
|
if (cache[index]) return cache[index];
|
|||
|
|
else {
|
|||
|
|
if (index < 3) return 1;
|
|||
|
|
else {
|
|||
|
|
cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return cache[index];
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### [Rod cutting](https://www.geeksforgeeks.org/problems/rod-cutting0840/1)
|
|||
|
|
Given a rod of length N inches and an array of prices, price[]. price[i] denotes the value of a piece of length i. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
|
|||
|
|
|
|||
|
|
#### Optimal solution
|
|||
|
|
- Let the left part have a length $l$
|
|||
|
|
- Then $R[n] = P[l] + R[n-l]$
|
|||
|
|
- Where $P[l]$ is the price
|
|||
|
|
- First cut of length should be the maximal one
|
|||
|
|
|
|||
|
|
|
|||
|
|
### Knight Collecting Rewards
|
|||
|
|
>Knight Collecting rewards
|
|||
|
|
Input: Integers $n, m$, table of rewards of size $n \times m$
|
|||
|
|
Question: What is the maximum reward that the knight can get for its journey.
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
#### Strategy
|
|||
|
|
- We look at the bounds defined by the problem statement
|
|||
|
|
- We know that the knight can get into the cell $(n-1, m-1)$ either from $(n-2,m-3)$ or $(n-3,m-2)$
|
|||
|
|
- Hence, we have to know the most rewarding path to these two points from $(0,0)$
|
|||
|
|
|
|||
|
|
#### Approaches
|
|||
|
|
|
|||
|
|
- $\mathcal{O}(n*m)$
|
|||
|
|
```
|
|||
|
|
Reward(int n, int m, matrix A)
|
|||
|
|
Create matrix R of size n × m with −∞ values
|
|||
|
|
R[0, 0] = A[0, 0]
|
|||
|
|
for i in {0, .., n − 1} do
|
|||
|
|
for j in {0, .., m − 1} do
|
|||
|
|
R[i, j] = A[i, j] + max R[i − 1, j − 2], R[i − 2, j − 1]
|
|||
|
|
end for
|
|||
|
|
end for
|
|||
|
|
return R[n-1, m-1]
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
This doesn't tell us how we got there, but it does give us max rewards.
|
|||
|
|
We can easily include path memory by making elements be a linked list or create a separate table blah blah.
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
### [Longest common non-contiguous sequence](https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/)[^1]
|
|||
|
|
|
|||
|
|
> LCS
|
|||
|
|
Input: Two sequences X = [x1, x2, . . . xm], Y = [y1, y2, . . . , Yn].
|
|||
|
|
Question: Longest common subsequence
|
|||
|
|
|
|||
|
|
#### Strategy
|
|||
|
|
![[LCS.png]]
|
|||
|
|
|
|||
|
|
Or this formula:
|
|||
|
|
$$
|
|||
|
|
|
|||
|
|
c[i,j] = \begin{cases}
|
|||
|
|
0, & \text{if } i=0 \text{ or } j=0\\
|
|||
|
|
c[i-1,j-1]+1, & \text{if } i,j>0 \text{ and } x_i = y_i\\
|
|||
|
|
max\{c[i,j-1], c[i-1], j\}, & \text{if } i,j>0 \text{ and } x_i \neq y_i\\
|
|||
|
|
|
|||
|
|
\end{cases}
|
|||
|
|
$$
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
### [Dominating set](https://www.geeksforgeeks.org/dominant-set-of-a-graph/)[^2] in a path
|
|||
|
|
|
|||
|
|
>Input: A path $P$ with a specified positive cost for each vertex.
|
|||
|
|
Output: Choose a subset of vertices $S$ with a minimum cost such that for each $v \in P$: either $v \in S$ or there is u such that $u \in S$ and $u, v$ are neighbors.
|
|||
|
|
|
|||
|
|
|
|||
|
|
#### Strategy
|
|||
|
|
- Identify some subproblems
|
|||
|
|
- $A[i]$ cost of the cheapest set $S_i \subset P_i$ which dominates all vertices in $P_i$ <- not great
|
|||
|
|
- $A[i,0]$ equals the cost of the cheapest $S_i$ which dominates $P_i$ and $v_i \notin S_i$
|
|||
|
|
- $A[i,1]$ equals the cost of the cheapest
|
|||
|
|
|
|||
|
|
|
|||
|
|
[^1]: **contiguous** - next or near in time or sequence
|
|||
|
|
[^2]: [Subset of the vertices of the graph $G$, such that any vertex of $G$ is in it, or has a neighbor in it](https://en.wikipedia.org/wiki/Dominating_set)
|