NP-hard algorithm

Question

Я работаю над алгоритмом NP-hard проблемы (например, проблемой продавца рук), и я не могу найти правильный алгоритм. Буду признателен, если кто-нибудь сможет мне помочь. У нас есть матрица (x,y), в блоке (n,m) есть робот, и в матричных блоках есть мусор.

Мы хотим, чтобы робот попал в каждый блок, в котором есть мусор, после пересечения всех их он возвращается к первому блоку. В соответствующем вопросе есть два условия:

1. Робот может двигаться только горизонтально и вертикально.
2. Вывод представляет собой целое число, которое является длиной пути, с которым он пересек. Этот путь должен иметь минимальную длину.

Например, входы:

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

положение мусора:

2 3 
5 5 
9 4 
6 5 

выход:

24 

Answer 1

Как это?

определение точки:

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; 
    } 
} 

Узел:

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); 
    } 
} 

решатель алгоритм:

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()); 
    } 
}