public · concluded

The Shortest Path

AndreyOwlette

The shortest path gets us directly to the destination. So then we can take more journeys - all of them shortest paths?

Move 7
Andrey

Inversion of Move 6 — Beyond an intersection, we must turn the page. Just as the seasons shift, we are embarking on new paths some journeys are long and spiritual, while others are grounded and direct. Yet, the end of every path is simply the start of the next.

And so with the sunshine and the great bursts of leaves growing on the trees, just as things grow in fast movies, I had that familiar conviction that life was beginning over again with the summer.

F. Scott Fitzgerald, The Great Gatsby
Move 8
Owlette

Development of Move 7 — Indeed an optimized path might allow more time for random or spiritual exploration on other paths

min⁡∑i=1n∑j=1,j≠incijxijs.t.∑j=1,j≠inxij=1,∀i∈{1,…,n}∑i=1,i≠jnxij=1,∀j∈{1,…,n}ui−uj+nxij≤n−1,2≤i≠j≤nxij∈{0,1},ui∈Z\begin{aligned} &\min \sum_{i=1}^n \sum_{j=1, j \neq i}^n c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{j=1, j \neq i}^n x_{ij} = 1, \quad \forall i \in \{1, \dots, n\} \\ & \sum_{i=1, i \neq j}^n x_{ij} = 1, \quad \forall j \in \{1, \dots, n\} \\ & u_i - u_j + n x_{ij} \le n - 1, \quad 2 \le i \neq j \le n \\ & x_{ij} \in \{0, 1\}, \quad u_i \in \mathbb{Z} \end{aligned}
Move 9
Andrey

Resonance of Move 8 — We may never find that optimal sequence of paths, that balance of the spiritual and the earthly; perhaps that is the point.

HAM-CYCLE≤pTSP-DEC  ⟹  TSP is NP-hard\text{HAM-CYCLE} \le_p \text{TSP-DEC} \implies \text{TSP is NP-hard}
Move 10
Owlette

Synthesis of Move 9 — Maybe all our journeys are within us, the world throws challenges at us and the paths we choose or don't choose perhaps makes us the individuals we are. There's no perfect path or shortest path, there are just paths

It is not the mountain we conquer, but ourselves.

Edmund Hillary, attributed

The dialogue is concluded

The shortest path is back to us.