NP-hard algorithm

Question

I'm working on a NP-hard problem algorithm (like hand seller problem) and I can't find the proper algorithm. I will appreciate if anyone can help me with it. We have a (x,y) matrix, there is a robot in the (n,m) block and there are some rubbish in the matrix blocks.

We want the robot to go to each block that has a rubbish, after crossing all of them it comes back to its first block. There are two conditions in the related question:

1. The robot can only move horizontal and vertical.
2. The output is an integer that is the length of the path that it has crossed. This path must have minimum length.

For example, inputs are:

10 10 ----> x,y
1 1   ----> n,m
4     ----> number of rubbishes

position of rubbish:

2 3
5 5  
9 4  
6 5

output is:

24

Answer 1

Like this?

Point definition:

public class Point {

    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

The node:

public class Node {

    private Point p;
    private int cost;
    private int estimatedCost;
    private Set<Point> points;
    private Point origin;

    public Node(Point p, int cost, Set<Point> points, Point origin) {
        this.p = p;
        this.points = points;
        this.origin = origin;
        this.cost = cost;
        // Heuristic estimate cost
        if (points.isEmpty()) {
            this.estimatedCost = cost + distance(p, origin);
            this.cost = estimatedCost;
        } else {
            this.estimatedCost = cost + nearest(p, points) + nearest(origin, points);
            for (Point point : points) {
                estimatedCost += nearest(point, points);
            }
        }
    }

    private static int distance(Point p0, Point p1) {
        return Math.abs(p0.x - p1.x) + Math.abs(p0.y - p1.y);
    }

    private int nearest(Point p, Set<Point> points) {
        int result = Integer.MAX_VALUE;
        for (Point point : points) {
            int d = distance(point, p);
            if (d != 0 && d < result) {
                result = d;
            }
        }
        return result;
    }

    public int getCost() {
        return cost;
    }


    public boolean isClosed(){
        return cost == estimatedCost;
    }

    public int getEstimatedCost() {
        return estimatedCost;
    }

    public Set<Point> getPoints() {
        return points;
    }

    public Node goTo(Point target) {
        int newCost = cost + distance(this.p, target);
        Set<Point> newPoints;
        if (points.isEmpty()) {
            newPoints = Collections.emptySet();
        } else {
            newPoints = new HashSet<>(points);
            newPoints.remove(target);
        }
        return new Node(target, newCost, newPoints, origin);
    }
}

A Solver algorithm:

public static void main(String[] args) {
    Point origin = new Point(1, 1);
    Set<Point> points = new HashSet<>(Arrays.asList(new Point(2, 3), new Point(5, 5), new Point(6, 5), new Point(9, 4)));
    Node begin = new Node(origin, 0, points, origin);
    PriorityQueue<Node> candidates = new PriorityQueue<>((n0, n1) -> Integer.compare(n0.estimatedCost, n1.estimatedCost));
    candidates.add(begin);
    Node solution = null;
    while (!candidates.isEmpty()) {
        Node candidate = candidates.poll();
        if (candidate.isClosed()) {
            solution = candidate;
            candidates.clear();
        } else {
            for (Point p : candidate.getPoints()) {
                candidates.add(candidate.goTo(p));
            }
        }
    }
    if (solution != null) {
        System.out.println(solution.getCost());
    }
}