I want to find optimal frettings for guitar scales, played one note at a time. In particular let's assign a metric $d$ that assings a distance between pairs $(s_1,f_1)$, $(s_2,f_2)$ of integer numbers representing string/fret coordinates on the fretboard. Given
- the signature of a scale, which is the list of intervals separating each pair of subsequent notes in the scale
- an initial fret
- an initial string
- a number of consecutive notes per string
What is the complexity of an algorithm that finds all the sequences $(s_1,f_1), \ldots, (s_n,f_n)$ with the property that
$\sum_{i=1}^{n-1} d((s_i,f_i), (s_{i+1},f_{i+1}))$ is minimum
the initial string and all strings physically below it are among the $s_i$'s
the prescribed number of consecutive notes per string is respected
What known optimization algorithm could be more easily adapted to solve this problem?
You can use dynamic programming, as shown for piano by Hart, Bosch and Tsai, Finding Optimal Piano Fingerings (2000). Searching for "dynamic programming" and "guitar fingering" yields several other papers.