this is for holding javascript data
Jeremy Ting edited q2.tex
almost 10 years ago
Commit id: c8f5356530477877c84652573492eaed51e64397
deletions | additions
diff --git a/q2.tex b/q2.tex
index eeea1f6..6569576 100644
--- a/q2.tex
+++ b/q2.tex
...
So we can solve the traveling salesman problem using dynamic programming.
Subproblems will be subsets of the vertices $S$ from
${1,2,....,n}$ $(1,2,....,n)$ that includes the origin and a specific node j. Let $C(S,j)$ be the length of the shortest path visiting each node in S starting at 1 and stopping at $j$.
So $C(S,j)$ = $min(C(S-j,i)+d_{ij})$ for each $i$, where $i$ are all the neighbors of $j$.