Consider $n$ distinct points $(x_1,y_1), \dots ,(x_n,y_n)$. From these points, let the starting point be $(x_s,y_s)$, and let the final point be $(x_f,y_f)$. We need to find the minimum distance from $(x_s,y_s)$ to $(x_f,y_f)$ passing through at least $k$ points other than $(x_s,y_s)$ and $(x_f,y_f)$ with $(0 \le k \le n-2)$.
Note: starting point and final point need not necessarily be distinct.
My attempt was not efficient at all: I listed all possible paths one by one and calculate the distnace using the formula $d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ and the sum all of these distances. However, more points will be much more waste of time.
Consider these as examples:
A person likes to visit the cities $A, B, C, D, E, F, G,$ and $H$. Currently he is in $A$, and he wants $H$ to be his final destination, but he wants to visit at least two cities (other than $A$ and $H$).
A person likes to visit the cities $A, B, C, D, E, F, G,$ and $H$. Currently he is in $A$, and he wants $A$ to be his final destination, but he wants to visit at least three cities (other than $A$).
Your help would be really appreciated. Thanks!
Closely related problems where you need not visit all points are optimal subtour problem, orienteering problem, are prize-collecting TSP. Like with the TSP, you can solve the problem via a branch-and-cut algorithm where you dynamically introduce (generalized) subtour elimination constraints when they are violated, as in the Dantzig-Fulkerson-Johnson formulation. For small enough $n$, you can get by with a variant of the weaker but compact Miller-Tucker-Zemlin formulation.
Let $s$ and $t$ be the source and sink nodes, respectively. Let binary decision variable $x_{ij}$ indicate whether directed arc $(i,j)$ is traversed. In both formulations, the traditional assignment constraints from TSP are \begin{align} \sum_j x_{ij} &= 1 &&\text{for all $i$}\\ \sum_i x_{ij} &= 1 &&\text{for all $j$} \end{align} and should be replaced with \begin{align} \sum_j x_{ij} &= 1 &&\text{for $i=s$}\\ \sum_i x_{ij} &= 1 &&\text{for $j=t$}\\ \sum_j x_{ij} &\le 1 &&\text{for $i\not= s$}\\ \sum_i x_{ij} &\le 1 &&\text{for $j\not= t$}\\ \sum_{i,j} x_{ij} &\ge k && \end{align}