java - NP 困難なアルゴリズム

Question

私は NP 困難な問題アルゴリズム (手売り問題など) に取り組んでいますが、適切なアルゴリズムが見つかりません。誰かが私を助けてくれれば幸いです。マトリックスが(x,y)あり、ブロックにはロボットがあり(n,m)、マトリックス ブロックにはゴミがあります。

ロボットがゴミのある各ブロックに移動し、すべてのブロックを通過した後、最初のブロックに戻るようにします。関連する質問には2つの条件があります。

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