NP难算法

Question

我正在研究 NP-hard 问题算法（如卖手问题），但找不到合适的算法。如果有人可以帮助我，我将不胜感激。我们有一个 (x,y) 矩阵，(n,m) 块中有一个机器人，矩阵块中有一些垃圾。

我们希望机器人去每个有垃圾的街区，在穿过所有的街区后回到它的第一个街区。相关问题中有两个条件：

机器人只能水平和垂直移动。
输出是一个整数，表示它所经过的路径的长度。此路径必须具有最小长度。

例如，输入是：

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

垃圾位置：

输出为：

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

NP难算法

NP-hard algorithm

java

algorithm

np-hard