2
$\begingroup$

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions :

(x, y) to (x+1, y), (x-1, y), (x, y+1), (x, y-1), (x-1, y-1), (x+1, y+1), (x-1, y+1), (x+1, y-1)

You are given a sequence of points. Give the minimum number of steps in which you can cover all of them. You start from the first point.
Example:

Input : [(0, 0), (1, 1), (1, 2)] Output : 2

My approach:

  1. For each pair $0\le i\le N-1$ in the list find its subtraction with $\forall{j}$ except $i\neq{j}$.
  2. Sort the list of resultant subtractions.
  3. Selection of each pair in the list corresponds to the subtraction in increasing order & keep counting $\max(x_{2}-x_{1},y_{2}-y_{1})$ till the end.

Now,

  • If it is correct it's complexity is $\Theta(n^{2}\log n)$ because of subtraction between $\frac{n(n-1)}{2}$ pairs + sorting in $n^{2}\log n$. Is there any better efficient algorithm? (Updated from Prateek's answer)
Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ I am not sure if I understand you approach correctly, but you mean first compute all distances between each pair of points, then sort that distances, and finally how do you select the optimal path according to your points and their order? Sorting may not give you an optimal path with respect to the given points. $\endgroup$ Commented Jul 30, 2017 at 10:47
  • $\begingroup$ I do not understand the precise question. It seems the order of the route is fixed and there are no obstacles. Does that mean the main problem is to compute the number of steps to go from consecutive points $(x_1,y_1)$ to $(x_2,y_2)$? $\endgroup$ Commented Jul 30, 2017 at 12:50
  • 1
    $\begingroup$ But there is a formula for that distance. Compute $|x_2-x_1|$ and $|y_2-y_1|$ and then some addition and $\max$ and or $\min$.That would leave linear complexity? $\endgroup$ Commented Jul 30, 2017 at 13:14
  • 1
    $\begingroup$ This problem is basically Hamiltonian path (or metric traveling salesman problem) in the 2D plane, with a metric derived from the Manhattan norm; does Sec 3.4 of [Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey ](pure.tue.nl/ws/files/2373438/Metis148543.pdf) imply that it is NP-hard? See also cs.stackexchange.com/q/1749/755, cs.stackexchange.com/q/76908/755, cs.stackexchange.com/q/13267/755, cs.stackexchange.com/q/43549/755, en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP. $\endgroup$ Commented Jul 30, 2017 at 17:27
  • 2
    $\begingroup$ I see, I interpreted it as "sequence" and posted $O(K)$ solution. $\endgroup$ Commented Jul 30, 2017 at 17:56

2 Answers 2

Reset to default
0
$\begingroup$

Actually I did not get exactly what you are trying to do in Step 1 but complexity of this algorithm should be $O(n^{2} log(n))$ because you will get $(n*(n-1)/2)-c$ elements i.e $O(n^{2})$ elements and then to sort them you will get $O(n' log(n'))$ complexity where $n'=O(n^{2})$.

Their is a full proof solution for this problem and it also has complexity of $O(n^2 log(n))$.

Step 1. Lets assume all co-ordinates are nodes from 1,2.....N.First find distance b/w all the vertices in O(n^2). Step 3. Find minimum spanning tree which can be formed using Prim's algorithm or Kruskal's algorithm whose complexity is O(E log(E)) where 'E' is the number of edges and in our case E=n^2.

Hope that helps.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think minimum spanning tree won't give result. It's like we have to calculate shortest Euler path, not a tree. $\endgroup$ Commented Jul 30, 2017 at 9:39
  • $\begingroup$ Eular path is a path which visits every edge once, but here we need to visit every node(i.e. every vertex (x,y) and not every edge $\endgroup$ Commented Jul 30, 2017 at 18:12
0
$\begingroup$

UPDATE: after additional clarification it turned out that OP meant "set of points" instead of "sequence of points", and so the problem is reduced to TSP. Ignore the following solution which assumes "sequence of points".

The first approach is that you could solve using Floyd-Warshall algorithm in $O(|V|^3)$ time.
1) Convert the grid into a weighted graph where $w(v_i,v_j) = 1$ for each neighbouring pair of points $(p_i,p_j)$ on the grid. I assume that every move in any of the eight directions from a point takes 1 step (but you may use a different metric).
2) Compute shortest paths for each pairs of vertices (points on the grid) $(v_i,v_j)$, by storing them in the matrix $M$, where $M[i][j]$ means the shortest path from point $p_i$ to the point $p_j$, using Floyd-Warshall algorithm.
3) Then for the given sequence of points $[p_1(x_1,y_1),\dots, p_k(x_k, y_k)]$, compute the sum $M[p_1][p_2] + M[p_2][p_3] + \dots + M[p_{n-1}][p_n]$ (The shortest path from $p_1$ to $p_2$ plus the shortest to $p_3$ plus $\dots$).

You could take a different approach (a greedy algorithm). Given a sequence of points $[p_1(x_1,y_1),\dots, p_k(x_k, y_k)]$, you first compute the shortest path from $p_1$ to $p_2$ (using Fredman-Tarjan algorithm, using Fibonacci heaps) in $O(E + V\log{V})$ time, then from $p_2$ to $p_3$, and so until the last point. So, its complexity is $O(K(E + V\log{V}))$, where $K$ is the number of points $p_i$. To improve further observe that each vertex has at most eight neighbours and so the graph has at most $8V/2 = 4V$ edges, and hence the time complexity is $O(K(4V + V\log{V}))$ which is $O(KV\log{V}))$.

Yet another approach to improve the greedy algorithm is using BFS for finding the shortest path from one point to another one since your graph has edges only of weight 1 (may be considered as unweighted). BFS works in $O(V+E)$ time or $O(V)$ since your vertices have constant number of neighbours (eight at most). So the running time may be reduced to $O(KV)$.

And finally, you may compute the shortest path from one point $p_i$ to another $p_j$ in $O(1)$ by $\max(|x_i-x_j|, |y_i-y_j|)$ given coordinates $(x_i, y_i)$ and $(x_j,y_j)$ and reduce the algorithm to $O(K)$ time.

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.