15

我有一个用螺旋算法排序的坐标列表。我需要从该区域的中间开始并“触摸”任何坐标。

为了简化这是（未排序的）坐标列表的表示（x，y 在下图中用“点”标记）。

CSV 坐标列表可在此处获得。
X 从左到右
增加 Y 从 TOP 到 BOTTOM 增加

未排序的坐标列表 每个坐标都与下一个坐标不相邻，而是相隔 1 或 2 个骰子（或在某些情况下更多）。

从区域的中心开始，我需要通过螺旋运动来触摸任何坐标：

螺旋法

解析每个坐标我已经起草了这个 PHP 算法：

 //$missing is an associative array having as key the coordinate "x,y" to be touched
 $direction = 'top';
 $distance = 1;
 $next = '128,127';     //starting coordinate
 $sequence = array(
     $next;
 )
 unset($missing[$next]);
 reset($missing);
 $loopcount = 0;
 while ($missing) {
    for ($loop = 1; $loop <= 2; $loop++) {
        for ($d = 1; $d <= $distance; $d++) {
            list($x,$y) = explode(",", $next);
                if ($direction == 'top')    $next = ($x) . "," . ($y - 1);
            elseif ($direction == 'right')  $next = ($x + 1) . "," . ($y);
            elseif ($direction == 'bottom') $next = ($x) . "," . ($y + 1);
            elseif ($direction == 'left')   $next = ($x - 1) . "," . ($y);
            if ($missing[$next]) {
                unset($missing[$next]);     //missing is reduced every time that I pass over a coordinate to be touched
                $sequence[] = $next;
            }
        }
            if ($direction == 'top')    $direction = 'right';
        elseif ($direction == 'right')  $direction = 'bottom';
        elseif ($direction == 'bottom') $direction = 'left';
        elseif ($direction == 'left')   $direction = 'top';
    }
    $distance++;
 }

但由于坐标彼此不等距，我得到这个输出：

坐标的排序列表

可以清楚地看到，中间的运动是正确的，而相应的坐标位置，在某个时刻，每个坐标之间的跳跃不再连贯。

我怎样才能修改我的代码以获得这样的方法呢？

预期的坐标排序列表

为了简化/减少问题：想象上图中显示的点是推销员必须经常访问的城市。从区域中间的“城市”开始，接下来要参观的城市是位于起点附近的城市，位于起点的北、东、苏奇和西。除非没有访问过起点回合中的所有相邻城市，否则推销员不能访问任何其他城市。所有城市都只能参观一次。

4

2 回答 2

10

算法设计

首先，释放你的思想，不要想螺旋！:-) 然后，让我们制定算法约束（让我们使用推销员的观点）：

我目前在一个城市，正在寻找下一步去哪里。我必须找到一个城市：

  • 我以前没去过的地方
  • 尽可能靠近中心（以保持螺旋状）
  • 离我现在的城市尽可能近

现在，给定这三个约束，您可以创建一个确定性算法来创建一个螺旋（至少对于给定的示例应该如此，您可能可以创建需要更多努力的案例）。

执行

首先，因为我们可以向任何方向行走，所以我们通常使用欧几里得距离来计算距离。

然后找到下一个要参观的城市：

$nextCost = INF;
$nextCity = null;
foreach ($notVisited as $otherCity) {
    $cost = distance($current_city, $other_city) + distance($other_city, $centerCity);
    if ($cost < $nextCost) {
        $nextCost = $cost;
        $nextCity = $otherCity;
    }
}
// goto: $nextCity

重复此操作，直到没有更多城市可供参观。

要了解它是如何工作的，请考虑下图：

在此处输入图像描述

我目前在黄色圆圈中，我们假设到这一点的螺旋是正确的。现在比较黄色、粉色和蓝色线条的长度。这些线的长度基本上是我们使用距离函数计算的。你会发现在任何情况下，下一个正确的城市距离最短（好吧，至少只要我们到处都有尽可能多的点，你可能很容易想出一个反例）。

这应该让您开始为您的问题实施解决方案。

（正确性）优化

使用当前设计，您必须在每次迭代中将当前城市与所有剩余城市进行比较。然而，有些城市并不感兴趣，甚至走错了方向。foreach您可以通过在进入上述循环之前从搜索空间中排除一些城市来进一步优化算法的正确性。考虑这张图片：

在此处输入图像描述

你现在不想去那些城市（要保持螺旋式上升，你不应该倒退），所以甚至不要考虑它们的距离。尽管计算起来有点复杂，但如果您的数据点没有像您提供的示例中那样均匀分布，则此优化应该为您提供更多受干扰数据集的健康螺旋。

更新：正确性

今天它突然打动了我，我重新考虑了建议的解决方案。我注意到依赖两个欧几里德距离可能会产生不需要的行为的情况：

在此处输入图像描述

很容易构造一个蓝线肯定比黄线短的情况，因此得到首选。然而，这将打破螺旋运动。为了消除这种情况，我们可以利用行进方向。考虑下图（我为手绘角度道歉）：

在此处输入图像描述

关键思想是计算先前行进方向和新行进方向之间的角度。我们目前处于黄点，需要决定下一步去哪里。知道了前一个点，我们可以得到一个表示前一个运动方向的向量（例如粉红色的线）。

接下来，我们计算我们考虑的每个城市的向量，并计算与前一个运动向量的角度。如果该向量 <= 180 度（图像中的情况 1），则方向是可以的，否则不是（图像中的情况 2）。

// initially, you will need to set $prevCity manually
$prevCity = null;

$nextCost = INF;
$nextCity = null;
foreach ($notVisited as $otherCity) {
    // ensure correct travel direction
    $angle = angle(vectorBetween($prevCity, $currentCity), vectorBetween($currentCity, $otherCity));
    if ($angle > 180) {
        continue;
    }

    // find closest city
    $cost = distance($current_city, $other_city) + distance($other_city, $centerCity);
    if ($cost < $nextCost) {
        $nextCost = $cost;
        $nextCity = $otherCity;
    }
}
$prevCity = $currentCity;
// goto: $nextCity

注意正确计算角度和向量。如果您需要这方面的帮助，我可以进一步详细说明或简单地提出一个新问题。

于 2015-03-04T16:27:41.137 回答
1

当您错过遍历坐标时，问题似乎出在 if-conditional 中，即因为圆角。与先前的坐标计算相反的 else 条件将修复它。

于 2015-03-04T08:12:46.967 回答