# Algorithms DIY - Minecart
*B12901148 Kuan-Yu, Chou*
## Scenario
Mike is a lazy miner who wants to maximize efficiency in mining with minimal effort. Recognizing that necessity is the mother of invention, Mike has created an automated mining cart. This minecart is capable of entering caves and mining independently. However, the cart's operation is constrained by its limited battery life, meaning it cannot mine indefinitely. To maximize the value of his investment, Mike needs help in planning the optimal mining route for the minecart.

## Setup Details
Since the minecart is the result of Mike’s lifelong dedication and hard work, he only allows it to operate in familiar territory. Therefore, the map of the cave network, including all paths and resource distributions, is already known. The following details are relevant to the problem:

1. Battery Life:
The minecart has a limited amount of battery energy, and its consumption rate is constant over time. This determines the maximum operation time before requiring a recharge.

2. Cave Network:
The caves are interconnected through a network of paths. Each path has a specific length (distance), and the minecart consumes battery energy based on the travel time between caves.

3. Mining Value:
Each cave contains a certain amount of mineral resources (value). The time required to fully extract these resources varies from cave to cave. Mining operations also contribute to the battery consumption. Note that

4. Starting Point:
The minecart begins at a designated cave (the base) and must return there to recharge after completing its operation.

5. Optimization Goal:
Plan the minecart's route to maximize the total value of resources mined while ensuring it does not exceed its battery life constraints.

## Solution
### Data Structures
We model the problem using an undirected weighted graph $G = (V, E, w)$, where:

- $V = \{s, c_1, c_2, \dots, c_n, v_1, v_2, \dots, v_n\}$, with $s $ representing the starting point, $c_i$ being the vertices corresponding to the caves that need to be mined, and $v_i$ representing virtual vertices used to model the routes between caves.
- $E$ is the set of edges, which includes:
- $\{(c_i, v_i) \mid \forall i = 1, 2, \dots, n\}$, connecting each cave to its corresponding virtual vertex.
- $\{(v_i, v_j) \mid \text{if there is a road connecting cave } i \text{ and cave } j, i \neq j\}$, representing the direct paths between caves.
- $w(v_i, v_j)$ is the time required to travel between virtual vertices $v_i$ and $v_j$, which corresponds to the travel time between caves.
- $w(c_i, v_i)$ represents half of the mining time required in cave $i$, as both entering and leaving the cave consumes time. Thus, the total mining time for cave $i$ is the sum of $w(c_i, v_i)$ and its corresponding return time.
- An array $U = [u_1, u_2, \dots, u_n]$ stores the mining value of each cave, with $u_i$ representing the value of the resources in cave $i$.

### Algorithm
1. Use Floyd-Warshall to compute all the distance (required time) between each pair of caves.
2. For each permutation of $c_1, c_2, ..., c_n$ plus $s$ representing the order of the caves to visit and come back to $s$, use dynamic programming to solve the total length (total required time) and total value of each. Note that if the length of some subpath has exceeded the maximum time, there is no need to find the length of further extension of the path. For example, if the visit order $s \rightarrow c_1\rightarrow c_2\rightarrow c_3$ requires time over the limit, we don't find the length and value of $s \rightarrow c_1\rightarrow c_2\rightarrow c_3 \rightarrow c_4$, ... etc.
3. For the details of the dynamic programming, use a tree rooted by $s$ to store all the paths. If we want to solve the subtree rooted by, for example, $c_1$, we can copy paste the other subtree also rooted by $c_1$ and then delete the nodes that have been visited.
4. Choose the order of maximum total value.

#### Time complexity
1. Floyd-Warshall: $\Theta(n^3)$
2. Passimistically, we need to consider all the permutations of the caves, which requires considerations on $n!$ different routes. By dynamic programming, the tree size is $n!$. The time complexity is about $O(n!)$.
3. The total time complexity is pessimistically $O(n!)$.
4. However, this pessimistic condition probably cannot happen, or this minecart can get all the values once. Assume the time limit is about $O(log_2(n))$. (Maybe Mike will upgrade the battery by $O(log_2(n))$.) Then the tree height can be reduced to $O(log_2(n))$. The tree size would be $n^{lg(n)}$, which is much smaller than $n!$.
5. Further more, if the time limit is a constant, the tree size would be reduced to polynomial, which means that it can be solved in polynomial time.

## NP-Complete
- By the time complexity analysis, we find that our algorithm cannot solve this problem in polynomial time if we didn't have any information about the time limit.
- As a result, we now try to explain it.
### Decision Problem
1. Define the decision problem:
- Given the time limit $T$, is it possible to retrieve total value more than $k$?
2. Decision to optimal:
- The maximum total value can be found in $O(lg(u))$ times of decision problem by binary search, where $u$ is the sum of all the values of caves.
- The result of decision problem can be derived directly by finding the optimal solution once.
### NP:
- The decision problem can be verified by running Floyd-Warshall once and then go through the path to check the total length and retrieved total value.
- The above can be completed in polynomial time.
### Reduce from 0-1 Knapsack:
#### The 0-1 Knapsack problem can be reduced to this minecart problem by the following:
1. Setting the time limit to the backpack limit.
2. The required time of each cave is the weight of each items, and the value is the profits of each.
3. The time consumption between all pairs of caves is zero.
4. Try to retrieve total value of $k$.
#### 0-1 Knapsack true iff minecart true:
- If decision in minecart is true, which means that we can choose some caves that the required total time for mining is in the limit and total value over $k$ can be retrieved. Therefore, there are some corresponding items whose total weight is under the backpack's limit while the total profits is over $k$.
- If the decision in 0-1 Knapsack is true, because the time required between caves is 0, the ordering between caves is negligible. Then, the total time to mine in the corresponding caves is within the limit while the total value is over $k$.
#### Reduction function in polynomial time
- The reduction is done by setting the limits and the required time as well as the values of each caves.
- Done in $O(n^2)$

*By the above, the minecart problem is NP-complete.*

## Summary
This general minecart problem is proved to be a NP-complete problem. However, if we have some information about the time limit related to $n$, we can have some more positive inference on the time complexity to retrieve the maximum total value.

## Reference
The idea of this minecart problem is originated from the midterm project of the course, *"Cornerstone EECS Design and Implementation."*