A-star: 多目标启发式算法

Question

考虑一个简单的网格，其中任何一个点最多与其他4个点相连（北-东-西-南邻居）。

我需要编写一个程序，计算从选定的初始点到任何一个目标点的最小路径，这些目标点是相连的（任意两个目标点之间存在由目标点组成的路径）。当然，网格上可能会有障碍物。

我的解决方案非常简单：我使用A*算法，其中的启发式函数h(x)是从x到最近的目标点的曼哈顿距离。为了找到最近的目标点，我需要进行线性搜索（在O(n)时间复杂度下，其中n是目标点的数量）。这里是我的问题：是否有更高效的解决方案（启发式函数）来动态地找到最近的目标点（其中时间小于O(n)）？

或者也许A*不是解决这个问题的好方法？

- ThereIsElse

Answer 1

你需要翻译的内容如下：

你要搜索多少个目标，是十个还是几千个？如果只有十个，那么你的方法就可以很好地工作，但如果是几千个，那么最近邻搜索将为你提供建立数据快速搜索的思路。

权衡是显而易见的，将你的数据以空间方式组织起来进行搜索将需要时间，在小数据集上，暴力搜索会更简单。由于你不断地评估，我认为在非常少量的点上构造数据将是值得的。

另一种方法是修改的洪水填充算法，在到达目标点时停止洪水。

- Patrick Hughes

---

你认为这个算法能否扩展到一个可以找到所有目标的A*版本？我在想最近邻函数应该只返回尚未发现的目标，以防止搜索已经找到的节点。我不确定在运行算法时改变启发式方法是否会破坏它的功能。 - b9s

Answer 2

首先，决定是否需要优化，因为任何优化都会使您的代码变得更加复杂，对于少数目标来说，您当前的解决方案可能已经足够简单了，比如曼哈顿距离这样的简单启发式算法。

在采取第一步之前，计算每个目标的启发式值。将最近的目标记为当前选择的目标，并朝它移动，但从所有其他距离中减去可能的最大进展。您可以将第二个值视为“元启发式”；它是其他目标启发式的乐观估计。

在后续步骤中，计算当前目标的启发式以及任何具有小于或等于该启发式的“元启发式”的目标。其他目标不可能有更好的启发式，因此您无需计算它们。最近的目标成为新的当前目标；向它移动，从其他目标中减去可能的最大进展。重复此过程，直到到达目标。

- erickson

---

是的，我需要进行优化，因为我的问题针对大型网格（即约10^5 x 10^5）和大量目标。顺便说一句，谢谢你的回答 :)。 - ThereIsElse

如果你有这么多的目标，你可以考虑在开始A*之前计算目标的Voronoi图。然后只需查看图表以确定哪个目标最接近给定点。 - erickson

Answer 3

使用Dijkstra算法，该算法的输出是到所有可达点的最小成本。然后您只需从输出中选择目标点即可。

- Brian Minton

Answer 4

如果你的目标不是太高，想要简单的方法，可以考虑this article。

如果你想搜索多个目标中的任何一个，请构建一个启发式函数h'(x)，它是h1(x)、h2(x)、h3(x)等所有附近位置的启发式函数中的最小值。

一种思考方式是，我们可以从每个目标到一个新的图节点添加一个新的零成本边。到达该新节点的路径必然会经过其中一个目标节点。

如果你想搜索到所有几个目标的路径，你最好的选择可能是Dijkstra算法，并在找到所有目标时提前退出。可能有一种A*的变体可以计算这些路径；我不知道。

如果你想搜索靠近单个目标的位置，请让A*搜索找到到目标区域中心的路径。在处理OPEN集合中的节点时，当你拉出一个足够接近的节点时退出。

- Hussien Mostafa

Answer 5

您可以使用最近的目标来计算F分数。正如其他人所说，对于天真的方法，您可以直接计算当前节点距离所有目标的距离并选择最小值，如果您只有少量目标要搜索。对于超过100个目标，您可以使用 KDTree以加速进程找到最近的。

这里是Dart语言的样例代码。

Iterable<Vector2> getPath(Vector2 from, Iterable<Vector2> targets,
      {double? maxDistance, bool useAStar = false}) {
    targets = targets.asSet();
    clearPoints();
    var projectedTargets = addPoints(targets).toSet();

    var tree = useAStar ? IKDTree(targets) : null;
    var q = PriorityQueue<Node>(_priorityQueueComparor);
    Map<Vector2, Node> visited = {};
    var node = Node(from);
    visited[from] = node;
    q.add(node);
    while (q.isNotEmpty) {
      var current = q.removeFirst();
      // developer.log(
      //     '${current.point}#${current.distance}: ${getEdges(current.point).map((e) => e.dest)}');
      for (var edge in getEdges(current.point)) {
        if (visited.containsKey(edge.dest)) continue;

        var distance = current.distance + edge.distance;

        // too far
        if (maxDistance != null && distance > maxDistance) continue;

        // it is a target
        if (projectedTargets.contains(edge.dest)) {
          return reconstructPath(visited, current, edge.dest);
        }

        // we only interested in exploring polygon node.
        if (!_polygonPoints.contains(edge.dest)) continue;

        var f = 0.0;
        if (tree != null) {
          var nearest = tree
              .nearest(edge.dest, maxDistance: maxDistance ?? double.infinity)
              .firstOrNull;
          f = nearest != null ? edge.dest.distanceToSquared(nearest) : 0.0;
        }

        node = Node(edge.dest, distance, current.count + 1, current.point, f);
        visited[edge.dest] = node;
        q.add(node);
      }
    }

    return [];
  }

  Iterable<Vector2> reconstructPath(
      Map<Vector2, Node> visited, Node prev, Vector2 point) {
    var path = <Vector2>[point];
    Node? currentNode = prev;
    while (currentNode != null) {
      path.add(currentNode.point);
      currentNode = visited[currentNode.prev];
    }
    return path.reversed;
  }

  int _priorityQueueComparor(Node p0, Node p1) {
    int r;
    if (p0.f > 0 && p1.f > 0) {
      r = ((p0.distance * p0.distance) + p0.f)
          .compareTo((p1.distance * p1.distance) + p1.f);
      if (r != 0) return r;
    }
    r = p0.distance.compareTo(p1.distance);
    if (r != 0) return r;
    return p0.count.compareTo(p1.count);
  }

以及KD树的实现

class IKDTree {
  final int _dimensions = 2;
  late Node? _root;

  IKDTree(Iterable<Vector2> points) {
    _root = _buildTree(points, null);
  }

  Node? _buildTree(Iterable<Vector2> points, Node? parent) {
    var list = points.asList();
    if (list.isEmpty) return null;

    var median = (list.length / 2).floor();

    // Select the longest dimension as division axis
    var axis = 0;
    var aabb = AABB.fromPoints(list);
    for (var i = 1; i < _dimensions; i++) {
      if (aabb.range[i] > aabb.range[axis]) {
        axis = i;
      }
    }
    // Divide by the division axis and recursively build.
    // var list = list.orderBy((e) => _selector(e)[axis]).asList();
    list.sort(((a, b) => a[axis].compareTo(b[axis])));
    var point = list[median];
    var node = Node(point.clone());
    node.parent = parent;
    node.left = _buildTree(list.sublist(0, median), node);
    node.right = _buildTree(list.sublist(median + 1), node);
    update(node);
    return node;
  }

  void addPoint(Vector2 point, [bool allowRebuild = true]) {
    _root = _addByPoint(_root, point, allowRebuild, 0);
  }

  // void removePoint(Vector2 point, [bool allowRebuild = true]) {
  //   if (node == null) return;
  //   _removeNode(node, allowRebuild);
  // }

  Node? _addByPoint(
      Node? node, Vector2 point, bool allowRebuild, int parentDim) {
    if (node == null) {
      node = Node(point.clone());
      node.dimension = (parentDim + 1) % _dimensions;
      update(node);
      return node;
    }
    _pushDown(node);

    if (point[node.dimension] < node.point[node.dimension]) {
      node.left = _addByPoint(node.left, point, allowRebuild, node.dimension);
    } else {
      node.right = _addByPoint(node.right, point, allowRebuild, node.dimension);
    }
    update(node);
    bool needRebuild = allowRebuild && criterionCheck(node);
    if (needRebuild) node = rebuild(node);
    return node;
  }

  // checked
  void _pushDown(Node? node) {
    if (node == null) return;
    if (node.needPushDownToLeft && node.left != null) {
      node.left!.treeDownsampleDeleted |= node.treeDownsampleDeleted;
      node.left!.pointDownsampleDeleted |= node.treeDownsampleDeleted;
      node.left!.treeDeleted =
          node.treeDeleted || node.left!.treeDownsampleDeleted;
      node.left!.deleted =
          node.left!.treeDeleted || node.left!.pointDownsampleDeleted;
      if (node.treeDownsampleDeleted) {
        node.left!.downDeletedNum = node.left!.treeSize;
      }
      if (node.treeDeleted) {
        node.left!.invalidNum = node.left!.treeSize;
      } else {
        node.left!.invalidNum = node.left!.downDeletedNum;
      }
      node.left!.needPushDownToLeft = true;
      node.left!.needPushDownToRight = true;
      node.needPushDownToLeft = false;
    }
    if (node.needPushDownToRight && node.right != null) {
      node.right!.treeDownsampleDeleted |= node.treeDownsampleDeleted;
      node.right!.pointDownsampleDeleted |= node.treeDownsampleDeleted;
      node.right!.treeDeleted =
          node.treeDeleted || node.right!.treeDownsampleDeleted;
      node.right!.deleted =
          node.right!.treeDeleted || node.right!.pointDownsampleDeleted;
      if (node.treeDownsampleDeleted) {
        node.right!.downDeletedNum = node.right!.treeSize;
      }
      if (node.treeDeleted) {
        node.right!.invalidNum = node.right!.treeSize;
      } else {
        node.right!.invalidNum = node.right!.downDeletedNum;
      }
      node.right!.needPushDownToLeft = true;
      node.right!.needPushDownToRight = true;
      node.needPushDownToRight = false;
    }
  }

  void _removeNode(Node? node, bool allowRebuild) {
    if (node == null || node.deleted) return;

    _pushDown(node);
    node.deleted = true;
    node.invalidNum++;
    if (node.invalidNum == node.treeSize) {
      node.treeDeleted = true;
    }

    // update and rebuild parent
    var parent = node.parent;
    if (parent != null) {
      updateAncestors(parent);
      bool needRebuild = allowRebuild && criterionCheck(parent);
      if (needRebuild) parent = rebuild(parent);
    }
  }

  void updateAncestors(Node? node) {
    if (node == null) return;
    update(node);
    updateAncestors(node.parent);
  }

  void _removeByPoint(Node? node, Vector2 point, bool allowRebuild) {
    if (node == null || node.treeDeleted) return;

    _pushDown(node);
    if (node.point == point && !node.deleted) {
      node.deleted = true;
      node.invalidNum++;
      if (node.invalidNum == node.treeSize) {
        node.treeDeleted = true;
      }
      return;
    }

    if (point[node.dimension] < node.point[node.dimension]) {
      _removeByPoint(node.left, point, false);
    } else {
      _removeByPoint(node.right, point, false);
    }
    update(node);
    bool needRebuild = allowRebuild && criterionCheck(node);
    if (needRebuild) rebuild(node);
  }

  // checked
  void update(Node node) {
    var left = node.left;
    var right = node.right;
    node.treeSize = (left != null ? left.treeSize : 0) +
        (right != null ? right.treeSize : 0) +
        1;
    node.invalidNum = (left != null ? left.invalidNum : 0) +
        (right != null ? right.invalidNum : 0) +
        (node.deleted ? 1 : 0);
    node.downDeletedNum = (left != null ? left.downDeletedNum : 0) +
        (right != null ? right.downDeletedNum : 0) +
        (node.pointDownsampleDeleted ? 1 : 0);
    node.treeDownsampleDeleted = (left == null || left.treeDownsampleDeleted) &&
        (right == null || right.treeDownsampleDeleted) &&
        node.pointDownsampleDeleted;
    node.treeDeleted = (left == null || left.treeDeleted) &&
        (right == null || right.treeDeleted) &&
        node.deleted;
    var minList = <Vector2>[];
    var maxList = <Vector2>[];
    if (left != null && !left.treeDeleted) {
      minList.add(left.aabb.min);
      maxList.add(left.aabb.max);
    }
    if (right != null && !right.treeDeleted) {
      minList.add(right.aabb.min);
      maxList.add(right.aabb.max);
    }
    if (!node.deleted) {
      minList.add(node.point);
      maxList.add(node.point);
    }
    if (minList.isNotEmpty && maxList.isNotEmpty) {
      node.aabb = AABB()
        ..min = minList.min()
        ..max = maxList.max();
    }

    // TODO: Radius data for search: https://github.com/hku-mars/ikd-Tree/blob/main/ikd-Tree/ikd_Tree.cpp#L1312

    if (left != null) left.parent = node;
    if (right != null) right.parent = node;

    // TODO: root alpha value for multithread
  }

  // checked
  final minimalUnbalancedTreeSize = 10;
  final deleteCriterionParam = 0.3;
  final balanceCriterionParam = 0.6;
  bool criterionCheck(Node node) {
    if (node.treeSize <= minimalUnbalancedTreeSize) return false;
    double balanceEvaluation = 0.0;
    double deleteEvaluation = 0.0;
    var child = node.left ?? node.right!;
    deleteEvaluation = node.invalidNum / node.treeSize;
    balanceEvaluation = child.treeSize / (node.treeSize - 1);
    if (deleteEvaluation > deleteCriterionParam) return true;
    if (balanceEvaluation > balanceCriterionParam ||
        balanceEvaluation < 1 - balanceCriterionParam) return true;
    return false;
  }

  void rebuildAll() {
    _root = rebuild(_root);
  }

  // checked
  Node? rebuild(Node? node) {
    if (node == null) return null;
    var parent = node.parent;
    var points = flatten(node).toList();
    // log('rebuilding: $node objects: ${objects.length}');
    deleteTreeNodes(node);
    return _buildTree(points, parent);
    // if (parent == null) {
    //   _root = newNode;
    // } else if (parent.left == node) {
    //   parent.left = newNode;
    // } else if (parent.right == node) {
    //   parent.right = newNode;
    // }
  }

  // checked
  Iterable<Vector2> flatten(Node? node) sync* {
    if (node == null) return;
    _pushDown(node);
    if (!node.deleted) yield node.point;
    yield* flatten(node.left);
    yield* flatten(node.right);
  }

  void deleteTreeNodes(Node? node) {
    if (node == null) return;
    _pushDown(node);
    deleteTreeNodes(node.left);
    deleteTreeNodes(node.right);
  }

  double _calcDist(Vector2 a, Vector2 b) {
    double dist = 0;
    for (var dim = 0; dim < _dimensions; dim++) {
      dist += math.pow(a[dim] - b[dim], 2);
    }
    return dist;
  }

  // checked
  double _calcBoxDist(Node? node, Vector2 point) {
    if (node == null) return double.infinity;
    double minDist = 0;
    for (var dim = 0; dim < _dimensions; dim++) {
      if (point[dim] < node.aabb.min[dim]) {
        minDist += math.pow(point[dim] - node.aabb.min[dim], 2);
      }
      if (point[dim] > node.aabb.max[dim]) {
        minDist += math.pow(point[dim] - node.aabb.max[dim], 2);
      }
    }
    return minDist;
  }

  void _search(Node? node, int maxNodes, Vector2 point, BinaryHeap<Result> heap,
      double maxDist) {
    if (node == null || node.treeDeleted) return;
    double curDist = _calcBoxDist(node, point);
    double maxDistSqr = maxDist * maxDist;
    if (curDist > maxDistSqr) return;
    if (node.needPushDownToLeft || node.needPushDownToRight) {
      _pushDown(node);
    }
    if (!node.deleted) {
      double dist = _calcDist(point, node.point);
      if (dist <= maxDistSqr &&
          (heap.size() < maxNodes || dist < heap.peek().distance)) {
        if (heap.size() >= maxNodes) heap.pop();
        heap.push(Result(node, dist));
      }
    }
    double distLeftNode = _calcBoxDist(node.left, point);
    double distRightNode = _calcBoxDist(node.right, point);
    if (heap.size() < maxNodes ||
        distLeftNode < heap.peek().distance &&
            distRightNode < heap.peek().distance) {
      if (distLeftNode <= distRightNode) {
        _search(node.left, maxNodes, point, heap, maxDist);
        if (heap.size() < maxNodes || distRightNode < heap.peek().distance) {
          _search(node.right, maxNodes, point, heap, maxDist);
        }
      } else {
        _search(node.right, maxNodes, point, heap, maxDist);
        if (heap.size() < maxNodes || distLeftNode < heap.peek().distance) {
          _search(node.left, maxNodes, point, heap, maxDist);
        }
      }
    } else {
      if (distLeftNode < heap.peek().distance) {
        _search(node.left, maxNodes, point, heap, maxDist);
      }
      if (distRightNode < heap.peek().distance) {
        _search(node.right, maxNodes, point, heap, maxDist);
      }
    }
  }

  /// Find the [maxNodes] of nearest Nodes.
  /// Distance is calculated via Metric function.
  /// Max distance can be set with [maxDistance] param
  Iterable<Vector2> nearest(Vector2 point,
      {int maxNodes = 1, double maxDistance = double.infinity}) sync* {
    var heap = BinaryHeap<Result>((e) => -e.distance);
    _search(_root, maxNodes, point, heap, maxDistance);
    var found = math.min(maxNodes, heap.content.length);

    for (var i = 0; i < found; i++) {
      yield heap.content[i].node.point;
    }
  }

  int get length => _root?.length ?? 0;

  int get height => _root?.height ?? 0;
}

class Result {
  final Node node;
  final double distance;
  const Result(this.node, this.distance);
}

class Node {
  Vector2 point;
  int dimension = 0;
  Node? parent;
  Node? left;
  Node? right;
  int treeSize = 0;
  int invalidNum = 0;
  int downDeletedNum = 0;
  bool deleted = false;
  bool treeDeleted = false;
  bool needPushDownToLeft = false;
  bool needPushDownToRight = false;
  bool treeDownsampleDeleted = false;
  bool pointDownsampleDeleted = false;

  AABB aabb = AABB();

  Node(this.point);

  int get length {
    return 1 +
        (left == null ? 0 : left!.length) +
        (right == null ? 0 : right!.length);
  }

  int get height {
    return 1 +
        math.max(
          left == null ? 0 : left!.height,
          right == null ? 0 : right!.height,
        );
  }

  int get depth {
    return 1 + (parent == null ? 0 : parent!.depth);
  }
}

- shtse8