如何设计算法生成随机但有效的火车轨道布局？

Question

我想知道我是否有弯曲轨道的数量c和直轨的数量，我如何设计算法（计算机辅助或不），使用所有这些轨道设计“随机”布局，这样满足以下规则：

1）轨道，当所有连接时，形成一个封闭的（连续的）循环，用于火车进去。

2）斜坡，扭转轨道，轨道的碰撞，轨道的交叉都不允许。

3）c和s均均为偶数。一个例子是C= 20和S= 10。注意，在相同的方向上需要12条曲线，以制作360度的完整圆，因此至少12个曲线需要以相同的方式定向以完成360度。其他人可以“曲折”只要网络结果为360度，所以火车有一个完整的循环。

直轨约10英寸（25.4厘米）长而弯曲的轨道长约12.4英寸（31.6厘米）长（沿着曲线下调）和曲线30度。轨道上的“连接”的最大宽度为3 5/8英寸（9.2厘米）。我彼此顶部的直线和弯曲的轨道放置，并测量了12.4“（31.6cm）曲线的线性长度（在与直线相同），3”（7.6厘米）弯曲（在直线的垂直方向上）。12c圆的直径为47.5英寸（120.6厘米），从中心到相对侧的轨道中心。

所有测量都是近似的。

更新

我用更多更多他们重新测量了轨道来帮助消除错误，有点令我惊讶的是，直线的长度不是10英寸，它们看起来约为9.78英寸。这对Zigzag曲线的匹配产生了重大影响。最初我认为4个锯齿形曲线= 5级，但这不太正确。 4曲线的线性距离大约47英寸的线性距离如此5英寸直线“每个”每个将是48.9“，差不多2英寸。因此，它找到了47和9.78的LCM（最不常见的多个）。事实证明是235 。235= 47 * 5和235 / 9.78= 24.028 ......（足够接近）。这意味着20个Zigzag曲线几乎与线性长度的直线相同。幸运的是，我有26个直线，所以我几乎没有做到这一点。这2剩余的可以很容易地定位在布局中的其他地方。

我发现的另一件事是，如果我以相同的时间（ooccccoo）zigzag zigzag，那么8的8个只有83英寸的线性距离，如果我替代曲线（ockoocco）则不是94英寸。 LCM为83和9.78约为166.因此，这些曲线中的16个具有与17直线相同的线性长度。这是有用的，因为我有44个曲线，只有26曲线，但如果我这样做，我可以帮助弥补它。

如果我一次曲折曲线3（ooccccccooo）并稍微弯曲，我可以获得10个直线的精确线性长度（约97.8英寸）。

更新结束

所以计算机程序是否必须创建几何模型并记住每个轨道的确切位置，或者有一些更简单的方式来编码这个吗？我希望能够“按下一个按钮”，电脑“吐出”对我有效的“新”布局。

我想将这个工作算法给使用火车的孩子，因此他们不会沮丧尝试不起作用的布局，然后他们试图弯曲轨道以使其工作或必须遗漏很少有轨道片Cuz他们不适合。计算机可以使用所有曲目创建有效的布局，如果算法好，可能在几秒钟内。这是为了帮助防止他们的挫折。

我有一些编码技巧，但我需要先知道一个算法在我可以编写有意义的东西之前（除了测试候选算法的几个部分）之前，我可以确定一个算法）

我认为是什么，我可以使用更小（缩小）表示的曲目模型。我认为它可以只是“将”候选人布局中的曲目“放置”，并检查已经存在的其他轨道。

我在想有可能做得更好的方法，所以这就是为什么我在这里寻求一些帮助/想法。我真的很想得到这个工作，我有轨道在这里，所以我可以用它们来帮助验证算法是否正常工作。

我们可以使用c= 20和s= 10作为尝试解决这个问题的参数，因为它是一个相当少量的曲目（总共30个）。我假设算法是否足够强大，C和S值可以随意改变，它仍然可以工作。例如，最终我想尝试c= 44和s= 26。

最终词

谢谢你们对这个问题的意见和建议。我也学到了很多东西。作为一个孩子，我从未真正考虑过大量的火车轨道以及它们如何合适，但作为成年人，我可以看到它是一个迷人的几何问题，以及生成/图的非常困难的数学计数问题

有多少种不同（独特的）轨道布局。我希望你尽可能多地享受这个练习。孩子们也很欣赏它。

结束最终词

Answer 1

我以为我会提供蛮力解决方案。

想法是依次尝试每一个轨道布局。在构造布局时，只需要考虑三个部分：左手曲线，右手曲线和直线。

您可以将轨道布局作为基本3编号编码，宽度对应于布局中的片段数。要枚举所有轨道布局，只需在基础3中计数，其中编码转为0=直，1=左和2=右。

下一阶段是检查布局在两端加入。第一个检查是确保有足够的曲线来进行一个完整的电路。如果我们为一个电路选择逆时针方，则需要12个左曲线。对于每个额外的正确曲线，我们需要添加额外的左曲线。因此要检查特定的布局可能会有效，只需添加左曲线的数量并减去右曲线的数量 - 这必须等于12。

最后，我们需要检查实际满足的目的。我们只是在笛卡尔栅栏上绘制曲目。我们在[0,0]的原点，如果它在[0,0]结束，那么它就会连接。

绘制曲目的最简单方法是 logo 样式。换句话说，我们维持一个方向向量，该方向向量朝着最后一个轨迹件的方向点。如果我们围绕左曲线，则将方向旋转30度，右曲线旋转-30度 - 直线不会影响方向。

实际上绘制曲线和直线，我们通过曲线的尺寸来扩大方向矢量，即直线10个单位，12.4 x 12/2 x pi（半径的完整圆形轨道）为曲线。

capeats

由于添加浮点数时舍入错误，绘图并不准确。在现实生活中，我们可以留下一些蠕动的房间来满足，所以这需要迎合。

许多布局将是相同的，但是由一个位置移位。我看不到以除了保持前一体的重复移位布局并检查它们的方法。

算法不排除碎片交叉的布局。为此，您必须检查布局中的每件作品不会在布局中交叉（那对O（n ^ 2））。并且必须检查曲线曲线，曲线直线和直线交叉，并且开始变得非常复杂。

算法的运行时间显然是o（3 ^ n），这是指数级的 - 并且对于非常大的布局可能是不切实际的。

下面是一些VBA代码，你可以粘贴到Excel上，以给你概念证明。我故意试图将代码保持尽可能简单，以帮助转换为您喜欢的语言。任何问题，请随时询问。

Option Explicit

Type Vector
    X As Double
    Y As Double
End Type

Sub GenerateTrackLayout()
    Dim lCounts(40) As Long
    Dim lColumn As Long
    Dim lTrackLength As Long
    Dim lCurveSum As Long
    Dim lIndex As Long
    Dim lIndex2 As Long
    Dim vDirection As Vector
    Dim vBase As Vector
    Dim vTrackPosition As Vector
    Dim fPI As Double
    Dim fCurveRadius As Double
    Dim fStraightLength As Double
    Dim sPath As String
    Dim lOutputRow As Long
    Const TOLERANCE = 0.5 'inch

    lOutputRow = 1

    vBase.X = Sqr(3) / 2 ' 30 degrees
    vBase.Y = 1 / 2 ' 30 degrees

    fPI = 4 * Atn(1)
    fCurveRadius = 12.4 * 12 / (2 * fPI)
    fStraightLength = 10

    lTrackLength = 12 ' initial track length

    Application.ScreenUpdating = False

    Do
        ' Check for closed track
        lCurveSum = 0

        For lIndex = 0 To lTrackLength - 1
            If lCounts(lIndex) = 1 Then
                lCurveSum = lCurveSum + 1
            ElseIf lCounts(lIndex) = 2 Then
                lCurveSum = lCurveSum - 1
            End If
        Next

        If lCurveSum = 12 Then ' one 360 degree rotation anti-clockwise
            vDirection.X = 0
            vDirection.Y = 1
            vTrackPosition.X = 0
            vTrackPosition.Y = 0

            ' Plot the track and ensure that ends meet
            For lIndex = 0 To lTrackLength - 1
                Select Case lCounts(lIndex)
                    Case 0 ' straight
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fStraightLength))
                    Case 1 ' left curve
                        vDirection = MultiplyVectors(vDirection, vBase, 1)
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
                    Case 2 ' right curve
                        vDirection = MultiplyVectors(vDirection, vBase, -1)
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
                End Select

                ' If ends meet within tolerance then output the track
                If Abs(vTrackPosition.X) < TOLERANCE Then
                    If Abs(vTrackPosition.Y) < TOLERANCE Then
                        If lIndex = (lTrackLength - 1) Then
                            sPath = ""
                            For lIndex2 = 0 To lIndex
                                Select Case lCounts(lIndex2)
                                    Case 0 ' straight
                                        sPath = sPath & "S"
                                    Case 1 ' left
                                        sPath = sPath & "L"
                                    Case 2 ' right
                                        sPath = sPath & "R"
                                End Select
                            Next
                            Application.ScreenUpdating = True
                            Cells(lOutputRow, 1).Value = sPath
                            Application.ScreenUpdating = False
                            lOutputRow = lOutputRow + 1
                        End If
                    End If
                End If
            Next
        End If

        ' Count in base 3 where number width is Track Length
        lColumn = 0
        Do
            lCounts(lColumn) = lCounts(lColumn) + 1
            If lCounts(lColumn) = 3 Then
                lCounts(lColumn) = 0
                lColumn = lColumn + 1
            Else
                Exit Do
            End If
        Loop Until lColumn = lTrackLength

        ' We've tried all tracks of this length, next one up...
        If lColumn = lTrackLength Then
            Erase lCounts ' reset all columns to zero
            lTrackLength = lTrackLength + 1
        End If
        DoEvents
    Loop
End Sub

' Vector maths

Function MultiplyVectors(vVectorA As Vector, vVectorB As Vector, ByVal fConjugate As Double) As Vector
    MultiplyVectors.X = vVectorA.X * vVectorB.X - fConjugate * vVectorA.Y * vVectorB.Y
    MultiplyVectors.Y = vVectorA.Y * vVectorB.X + fConjugate * vVectorA.X * vVectorB.Y
End Function

Function AddVectors(vVectorA As Vector, vVectorB As Vector) As Vector
    AddVectors.X = vVectorA.X + vVectorB.X
    AddVectors.Y = vVectorA.Y + vVectorB.Y
End Function

Function ScaleVector(vVector As Vector, ByVal fScale As Double) As Vector
    ScaleVector.X = vVector.X * fScale
    ScaleVector.Y = vVector.Y * fScale
End Function

.

Answer 2

首先，框架挑战：

计算机可以使用所有曲目创建有效的布局，如果算法好，可能在几秒钟内

您不需要算法在几秒钟内运行。您需要在几秒钟内输出。我没有看到任何阻止您在拐角处的计算机上运行的蛮力布局粗糙沉积，并将解决方案存储在数据库中，从中可以选择随机布局。

---

在代代语方面，有许多半标准方法。状态空间相当大，因此详尽的搜索可能不可行。但以下任何一项可能值得一试：

• 纯无随机洗机的直线列表和左曲线的等于数量，然后是“善良”测试。
• 爬山：从一个随机排列开始，然后测试简单的掉掉，看看它们是否改善了“善良”。如果他们这样做，请转换并重复。
• 模拟退火：相似，但有时允许改变减少“善良”的希望希望获得更好的山丘。
• 遗传算法：生成大量的随机排列，并反复混合它们并保持最佳结果。然而，它并不完全清楚如何混合它们。
• 后者可以从插入到圆圈生成的“已知良好”曲线开始。
• 探索中间相遇的选项。例如。生成具有+90°的总角度的所有曲线，在端点之间通过2D向量索引它们，如果有比有曲线的曲线较少，您可能能够彻底考虑它们的四分之一，以找到形成闭合四边形的那些。

对于“善良”测试，如果曲线没有关闭，显然需要成为一个大的罚款。对自身重叠需要一个很大的惩罚。我将倾向于测试使用四肢树的那些，找到不连续但彼此接近的段，然后是电弧，弧线和线路线路线路的测试，以查看是否有一个界限的任何边缘重叠另一个边缘边缘。

---

另一个可能能够完全蛮力的策略较小的案例，但不是较大的是将代数方法施加到总载体。让直线片的长度为 $ 2 \ ell $ ，曲线的半径为 $ 2r $ 。由于取向是30度的倍数，因此直线件的端部之间的向量位于<跨度类=“math-container”> $$（0，\ PM 2 \ ell），（\ PM 2 \ ell， 0），（\ PM \ ell，\ pm \ sqrt3 \ el），（\ pm \ sqrt3 \ ell，\ pm \ ell）$$ 类似，弯曲件的末端之间的向量在< SPAN Class=“Math-Container”> $$（\ PM R，\ PM \ SQRT3 R），（\ PM \ SQRT3 R，\ PM R），（\ PM（\ SQRT3 - 1）R，\ PM（\ SQRT3 - 1）R））$$

除非 $ \ frac \ ell r $ ， $ \ frac {\ sqrt 3 \ ell} r $ ，或 $ \ frac \ ell {\ sqrt 3 r} $ 是一个小分子的分数，小分母，曲线和直线是独立的，因此，您可以找到曲线的工作组（蛮力足够有20条曲线，其中16位于一个方向，4彼此相位;对于44个曲线分裂28-16，您需要更好的方法;我没有通过它要求 $ + \ sqrt 3 $ s的含义，以匹配 $ - \ sqrt 3 $ S，但它们可能允许一些沉重的过滤器），然后成对插入直线。对少量曲线的蛮力应用这一点将允许您评估您可能用对称方法丢失的布局数量。

Answer 3

一个可能的解决方案使其尽可能简单地快速获得工作算法如下。最简单的布局当然是12c（12个弯曲轨道，都具有相同的方向（相对于彼此），并形成一个简单的圆圈。这将是我们可以建立的基础。

因此，基本算法将在添加轨道时每步维护360度连续循环布局。我们可以通过检查我们剩余的曲线和将它们添加到布局中的布局中，维护360度的曲线。例如，从我们的12C布局开始（一个简单的圆圈）。我们知道我们总共有20C，所以我们剩下8C。最简单的添加一些将维持360度属性的人是添加反向方向曲线和相同的方向曲线（与我们开始的主圆相同）。然后我们将对布局的另一侧做同样的事情。在这个简单的例子中，我们将添加4个曲线到圆形布局所以12c将成为16c（带4c剩余的）。我们将继续放置曲线，直到所有20（在本例中）正确放置。请注意，由所有曲线组成的该布局是有效的闭环布局。该火车可以使用这种布局，但是它由所有弯曲轨道组成，所以我们尚未完成。

然后将直线轨道插入相同的方式，除了可以成对添加（2个轨道），因为它们不会改变360度属性。它们可以插入任何地方，所以我认为最好首先放置所有弯曲的轨道，然后返回并使第二次通过随机放置直线（但对称）。

这是我现在可以想到的最简单算法。保证生成360度闭环，对称曲目，并假设曲线＃的曲线为4的倍数，并且直的直线是2的倍数，它将使用每个和每个轨道。

要考虑的一件事（在计算机上使用此算法或在您建立布局时使用此算法时），则可能存在比另一个方向更有的空间限制。例如，在延长的露台上，但不是如此宽阔。使用算法时，它应该更加偏向于将组装布局的位置的长尺寸。

如果有人可以弄清楚使用所有轨道形成不对称布局的算法，那将更令人印象深刻。

最简单的解决方案和最复杂的复杂性的差异是惊人的。从一个圆圈（12c）开始就像它对这个问题一样简单并且对孩子来说是合理的，但是分析一个可以产生任何有效布局的通用解决方案非常有趣（包括不对称的问题）。

在现实中，非计算机算法将只是将一些“COOL”形状添加到布局中，并将其靠近连接，然后返回并微调它，使其确实连接（对于闭环）。通过70个轨道片总共（44c和26s），可能是一个巨大的布局。我计算总共约67英尺的轨道，约为20米。火车应该花大约1分钟循环整个布局一次。

另一个候选解决方案是采取每个轨道的实际测量，并记住布局的最右边。在构建布局时，您可以从直线轨道或左曲线（逆时针）开始，累积最后一个添加的曲目来自最右边的轨道，然后在添加其他轨道时，从不允许将曲目的组合组合碰撞或横向右边或甚至没有接近。所以例如，从直线轨道开始（在该候选解决方案上没有12C初始圆圈），然后随机挑选另一个轨道件。从开始时通知我们不会允许右（顺时针）转弯，因为这将破坏“交叉”的右边的规则。在第一轨道之后，我们唯一的选项是另一个直的或左（逆时针）曲线。强制执行的另一条规则将是直接的，我们不允许连续添加超过9个相同的方向曲线，否则可能会碰到已经到位的其他一些轨道。对于更多的间隙，该限制甚至可以减少到8，如果发生这种情况，则下一条轨道必须是反向定向的曲线（因为直线可能导致问题）。

此算法需要一些帮助将其返回并连接到第一添加轨道件的另一侧。我们可以通过坚持逆时针曲线计数为+1和顺时针曲线计数为-1，并且必须在最后添加的曲线上加入12个。我们可以通过顺时针曲线偏置CC（逆时针）曲线（逆时针）曲线以4：1的比率偏置来帮助这一点，因此我们可以获得16个CC和4顺时针，这将有效地净360度圈。如果是

他的算法尝试添加CC曲线但颠簸现有曲目，我们在该点有2个选项，尝试相反的方向曲线，或放弃布局并重新开始。我会认为在一个快速的计算机上，最终它会得到一个很好的布局。

我尚不确定此方法是否会产生与12c开始的所有相同的布局，但也许在计算机上可能更容易实现，因为只有少数规则强制执行，而且我们正在构建一次布局一条轨道。

实际上，我只是想到了一个第3可能的候选解决方案，应该工作，并不太难以实现。它如下。

使用上面描述的技术，但只制作半布局（使用每种类型的一半，所以10曲线和5个直线。我们有计算机选择随机轨道，但只接受最终网站的布局180度的左转（因为我们强制执行右侧边界，没有轨道可以触摸或交叉。好的，所以假设电脑很快找到有效的“半布局”。然后我们所做的只是拍摄多少顺时针曲线并且逆时针曲线存在，并且在轨道的另一半（但不一定对称）中有复制。对于直线，我们必须记录它们在它们插入的角度，然后在轨道的另一半匹配时匹配它们，但再一次，不一定对称。

让我们尝试使用s的直线，o for逆时针曲线，以及c的顺时针曲线。首先专注于半布局。

第一轨道将远离我们，并定义我们最右边的边缘，我们不允许交叉。

soosocsoossoooc - 这是一个有效的半布局，因为它有5个直线，10条曲线，其中6个逆时针曲线（8的2的2）逐渐消除2个顺时针曲线）。

现在我们需要“保持标签”在插入直线的角度并匹配具有相同角度（但相反方向）轨道的角度，以“取消”它们。

1：0度角直线

0：30度角直 2：60度角直链
0：90度角直链
2：120度角直 0：150度角直链
0：180度角直率

因此将其“匹配”在其他一半的布局上并使其连接到单个起始的直线轨道，我们只需要匹配相同数量的操作系统和CS，也匹配直的直线在+180度“返回”角度。例如，60度直的直线在布局的另一侧具有240度，不一定完全相同。这是因为60度直线将大部分到左侧和一点点（使用该方案），240度直线会使它回到右侧并返回相同的数量，以有效地“取消”这两个轨道贡献偏离起始轨道位置。

所以现在我们需要做的就是创建布局的“缺少的一半”是采取我们需要的已知曲目（并且知道直线的角度是什么），只是以任何顺序“争夺”它们。

可能有一种方法不必用另一侧的“互补”轨道完全匹配布局的一半，但这将涉及一些更复杂的数学，并且可能有足够的时间来解决赏金是活动的时间。还有机会，并非所有的曲目都可以使用这种方式，并且需要一些轻微的曲目弯曲。我们可以忽略这个问题的这个特殊财产。

我实际上是一个不对称的曲目，看看它是否会起作用，似乎它似乎是。使用S for直的O用于逆时针曲线，以及C对于顺时针曲线，加上相对于起始直线轨道的角度（以度为单位），我得到以下下半部分：

S0，O30，O60，S60，O90，C60，S60，O90，O120，S120，S120，O150，O180，O210，C180

对于我得到的轨道的下半部分：

O210，O240，S240，C210，O240，S240，O270，O300，S300，S300，O330，O360，O390，C360，S360

实际上，图片是从错误的一侧取出的，所以翻转顶部和底部。第一轨道铺设是蓝色垃圾桶附近的直线，朝向PIC的观看者，第二轨道是逆时针曲线。

似乎这种技术将适用于许多偶数曲线甚至是直的直线，包括44c和26s，这是我的最终目标。这真的是令人鼓舞，因为电子电脑真的有必要解决这个问题，我只能让孩子们建立一个轨道（22c和13s）的一半，然后“纠正”它们的设计这是

180度，然后“匹配”轨道的另一侧，不一定对称。

如果您要在起始轨道和结束轨道非常靠近一起创建180度半的布局，则必须小心。例如，问号“？”的上半部分的形状“？” （没有点）但继续上曲线，所以它绕过更多，直接下降，从此将非常接近直接，在圆点上方的位置。然后，对于下半部分，您将无法立即完成更逆时针的曲线，因为其他从“上半部分”有其他直线。我闭环布局的图像工作，因为我在“上”一半没有“瓶颈”，而是当然，当我刚才描述的那些方面就是可能的。

“有问题的”列车布局是当轨道的一半时，略带横向窄的中间。在这种情况下，您几乎必须“镜像”顶部，因为不能制造某些曲线，因为轨道彼此如此接近。这是一个榜样...

另一个有趣的观察是，4个锯齿形弯曲轨道几乎是5直线的精确替换（即，跨越线性距离）。然而，这太多会产生显着的长度差异。如上所述的更新部分所述，20个锯齿形曲线几乎是一个完全匹配（用于线性距离），为24直线。

使用这种技术，可以用所有70个轨道件制成巨大的布局。它将从一个12c圈开始，然后在一侧，我可以插入 24直线（长240英寸）。在布局的相对的长边上（几乎与直边的长度相匹配），我将使用20个锯齿形曲线（长约240英寸）。那些应该绕过略微排队，稍微弯曲应该使它变成。剩余的轨道（2直线和12个弯曲）很容易放置，以保持布局“平衡”（和连接）。

Answer 4

假设您从直接向右的点（0,0）开始。您需要添加曲目，直到达到点（0,0），此时直接从左侧。这里有两个问题：一个是达到来自左边的点（0,0）完全。另一个是没有重叠。

要形成逆时针圆，您需要12个弯曲件左转。这些形成了一个精确的圆圈。含有0或24或36个弯曲件，您可以拥有图8或两个或三个圆圈，任何一个都可以在没有交叉的情况下完成。

当然，您可以添加其他曲目，这些曲目必须遵循某些规则：您可以成对地以x度和x + 30度的角度添加左弯曲，直的和右弯曲的碎片，所以您返回0,0。并且超出前12的左弯曲的件的数量必须匹配右弯曲的件的数量，因此在0,0时匹配的棋子匹配。

所以这是你可以使用的作品。你需要检查是否显然没有过境点。

如果长度正好正确，那么它可能是左/右/右/左/左/左/左覆盖与四或五个直线完全相同的距离，因此可以允许一些其他组合。

当然，曲目是 bendy，可能会产生更多的可能性。