时间戳

首页 > 解决方案 > 我正在尝试编写一个简短的程序来找到理想的多米诺骨牌链，想法？

python - 我正在尝试编写一个简短的程序来找到理想的多米诺骨牌链，想法？

问题描述

如果您不熟悉多米诺骨牌：您的游戏棋子上有两个数字。你必须把它们安排好，第一首曲子的结尾是第二首曲子的开头。因此，如果我们有 3 张多米诺骨牌，其值为 [3-1][3-4][1-4]，您可以将它们排列为 [1-3]、[3-4]、[4-1] 或 [4-1 ]、[1-3]、[3-4]，因为你可以切换你开始的那一面（转动图片）。

现在到我的代码问题：

我得到了一个带有多米诺骨牌值的熊猫 df：

# D1 D2
1 1 5
2 2 4
3 3 6
4 4 1
5 3 4
6 2 3
7 6 5 
dominos = {'D1': [1, 2,3,4,3,2,6], 'D2': [5,4,6,1,4,3,5]}

现在，如果我随机选择其中一个，并且需要找到一条“路线”来到达那个特定的多米诺骨牌（所选的多米诺骨牌不能旋转），从 1 开始并再次以 1 结束，同时使用尽可能少的多米诺骨牌件。

例如：选择的部分是 [3-4]，代码需要打印出路线，看起来像这样（或在数组中）：

1: #1 [1-5]
2: !#7 [5-6] 
3: !#3 [6-3] 
4: **[3-4]** 
5: #4 [4-1]

到目前为止，我已经尝试使用很多for循环来做到这一点，但没有奏效。

import pandas as pd


dominos = {'D1': [1, 2,3,4,3,2,6], 'D2': [5,4,6,1,4,3,5]}
data = pd.DataFrame(dominos) 


ranD = data.loc[4,]

def findpath(data, ranD):
    trargetD1 = ranD.D1 
    #fid possible start
    for x in range(len(data)):
        if data.loc[x,'D1'] == 1:
            start = start + data.loc[x,]
            if start.loc[x, 'D2'] == ranD.D1:
                PerfectStart = start.loc[x, 'D2']
            elif start.loc[x, 'D2'] != ranD.D1:
                PerfectStart = start.loc[1,] 
        else:
            print("no start found")
    # when a start was found, that doesn't match ranD at pos. D2 find possible steps        
    for x in range(len(data)):
        if PerfectStart.D2 == ranD.D2 :
            
            step1 = step1 + data.loc[x,'D1']
            if step1.loc[x, 'D2'] == ranD.D1:
                PerfectStep = step1.loc[x, 'D2']
            elif start.loc[x, 'D2'] != ranD.D1:
                PerfectStep = step1.loc[1,]
  
etc.

如果有人对如何解决此问题有任何想法，请告诉我。

非常感谢您的反馈！

标签： pythonpandasalgorithmsorting

解决方案

您想将此视为图形问题。

您有 6 个节点（1..6），多米诺骨牌是节点之间的边。

您正在寻找一条从 1 到 1 的路径，该路径通过特定边 (a,b)，并且具有最少数量的边并且不会两次通过同一边。

因此，天真的方法是寻找从 1 到 a 和从 1 到 b 的路径，并希望或强制它们不共享边。

但是，由于您选择的第一个路径阻塞了第二个路径，因此在某些设置中它不起作用。对此有一个解决方案，即最大流量。

为此，您需要将 Source 链接到容量为 2 的节点 1。a 和 b 链接到容量为 1 的 Sink。每个其他边的容量为 1。如果您解决最大流量，它的容量为 2，您可以提取路径或将具有容量 0 或 1 在这种情况下没有解决方案。

由于您只有 6 个节点，因此不必担心有一个非常有效的解决方案，因为几乎所有东西都会运行得很快。

如果您熟悉最大流量，您可能可以稍微简化一下实现。如果没有，请不要担心，尽可能实施最直接的解决方案。

推荐阅读