public · concluded

The Shortest Path

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

Move 2
Move 3

Contrast of Move 2 — And yet to find something we need to optimize our path with some direction - otherwise we may oscillate

def a_star(start, goal, neighbors, h):    open_set = {start}    came_from = {}    g_score = {start: 0}    f_score = {start: h(start)}
    while open_set:        current = min(open_set, key=lambda n: f_score.get(n, float('inf')))        if current == goal:            path = []            while current in came_from:                path.append(current)                current = came_from[current]            path.append(start)            return path[::-1]
        open_set.remove(current)        for neighbor, cost in neighbors(current):            tentative_g = g_score[current] + cost            if tentative_g < g_score.get(neighbor, float('inf')):                came_from[neighbor] = current                g_score[neighbor] = tentative_g                f_score[neighbor] = tentative_g + h(neighbor)                open_set.add(neighbor)    return None
Move 4

Question of Move 3 — What is the destination that we seek?

We shall not cease from exploration And the end of all our exploring Will be to arrive where we started And know the place for the first time.

T. S. Eliot, Little Gidding
Move 5

Contrast of Move 4 — Consider both spiritual and physical searches - they are distinct. We can pursue an eternal and circular search for spiritual meaning while optimizing our earthly paths.

Plato (left): Points upward, representing the spiritual search for eternal truth. Aristotle (right): Points downward, representing the physical search for earthly, material knowledge.
Plato and Aristotle in The School of Athens, by Raphael Sanzio
Move 6

Development of Move 5 — Indeed the search for the spiritual and earthly can be distinct, yet they might intersect and influence one another

Where the spiritual and earthly intersect
04fig-venn-001
Move 7

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

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

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

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.