logo标签列表

以最少步数同时解决所有4x4迷宫

algorithmpath-findingmaze
30

我遇到了一个非常有趣的问题，我们有一个4x4的迷宫和一个机器人在里面试图到达目标。问题是，你必须找到一系列预定义的命令序列，这些命令序列将始终导致机器人到达目标。

假设我们有一个像这样的迷宫：

x . . .
. # # .
. # # .
. . . g

这个特定的迷宫可以用例如命令序列DDDRRR或RRRDDD来解决，其中R = 向右，L = 向左，U = 向上，D = 向下（当然）。

然而，这两个序列都无法解决此迷宫：

x . # .
. . . .
# . . .
. . . g

机器人总是从左上角开始，终点总是在右下角，迷宫始终是一个2D的4x4矩阵。

我已经实现了一种算法，得到了一个78个命令的获胜序列。我确定至少存在一个解决方案需要29个命令（有人已经做到了这一点）。

事实上，这个问题已经存在几年了，所以我忘记了当时用的算法，但基本想法是运行一个搜索来处理我生成的所有迷宫，并始终选择结果为解决最多迷宫的路线。实际上，这得到了一个略长于78的序列；我手动减少了一些我发现是多余的命令。

是的，暴力破解通常需要数年时间。

如果我的记忆正确，可能的迷宫少于4000个（可能的迷宫指的是从左上角到右下角存在路径的迷宫）。

哦！机器人只需在执行命令过程中至少访问一次目标即可。也就是说，在最后一个命令后，机器人不必停在目标上。

我引起了任何人的兴趣吗？我应该如何更有效地解决这个问题？感谢考虑 :)

有趣的事情：Pastebin

这是一个（非常）匆忙地编写的Java代码。它应该能够编译和运行 :) 程序在同时玩 ~4000 个迷宫。程序接收输入（w、a、s、d），代表上、左、下和右，然后模拟移动并显示一些统计信息。如果您尝试，可以在屏幕上看到每个迷宫中每个位置的障碍总数以及每个迷宫的当前位置的总数。很难解释 :) 如果有问题，请问我。

再一次......不要介意可怕的代码。它是在20分钟内编写的...ish

进度

我间接地从这位用户的回答中得到了这个想法，并与Mooing Duck一起进行了建模。这个想法是找到一个解决迷宫右侧的序列。也就是说，解决至少一半所有迷宫的解决方案，并且当其镜像并再次从头开始运行时可以解决剩余的迷宫。

图示：

首先找到一个序列，其第一个命令是RIGHT，可以解决例如这个迷宫：

0 1 0 0
0 1 0 0
0 0 0 0
0 1 0 0

一个这样的序列是RDDRRRD。该序列的镜像副本是这样的

R -> D
D -> R
L -> U
U -> L

这意味着RDDRRRD -> DRRDDDR

现在，这个镜像序列能解决迷宫吗？不行，会卡住。因此，即使对于这一个迷宫，它也不是有效的序列。我们必须找到这样一个序列，它至少可以解决所有迷宫的一半，而它的镜像对应的序列在重新从起点运行时解决另一半。

通过简单地粗力计算R、D和L的所有可能排列，我得到了一些可能的序列。

其中之一就是RRDRRRDRLDRDR

现在，下一个问题是，在运行这个序列后，其余的迷宫处于随机混乱状态。我们需要获得尽可能短（最优）的序列，将所有剩余的迷宫带回起始位置（0,0）。目前我只能手工完成这部分。我的答案绝不是最优的，但它可以让所有迷宫回到开始位置。

这个序列是LDLUULURUUULULL

之后我们只需运行镜像序列DDRDDDRDURDRD，我们就解决了所有迷宫。

这个序列的完整代码：

RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD - 41步

虽然这是一个有前途并且值得奖励的里程碑，但它距离最佳已证明的解决方案还有12步之遥。任何见解都受到欢迎! 还要感谢所有帮助我的人 ：）

序列缩小了

我目前还无法通过编程获得比58步更好的答案。然而，根据上述方法，并仅仅通过手工调整字符，我已经将序列缩短到只有33个字符。该序列如下所示：

RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR - 33步

虽然序列现在非常接近29的目标，但我仍在寻找以编程方式获得同等品质的解决方案。当我删除序列中的字符并检查是否解决了所有迷宫时，我没有使用任何逻辑-我只是简单地删除一个字符，然后重复检查。

1
@templatetypedef：在一个空的4x4矩阵中，从左上角到右下角有多少条唯一的路径 - 肯定不是4000^16吧？ - 500 - Internal Server Error
1
@גלעדברקן 哦，抱歉没有提到：移动到被阻塞的方格只会使机器人不去那里。 - Olavi Mustanoja
1
@500-服务器内部错误 我认为迷宫数量确实比2的14次方要少得多：我们可以忽略那些从起点到终点没有路径的迷宫，以及与其他迷宫等效的迷宫，因为某些非墙壁单元格是不可达的。我尝试了所有可能的迷宫，总共有2423个不同的迷宫，当然这还不包括我的错误... - Vincent van der Weele
我不知道。 - Olavi Mustanoja
顺便说一句，如果你再次发布你的答案，我肯定会给它点赞 :) - Olavi Mustanoja
显示剩余29条评论
10个回答
14
我将这个问题编码为一个包含4280308个变量和21975717个子句的SAT问题（其中包括很多冗余但似乎有用的子句），treengeling花费了大约100.5小时解决，并找到了长度为29的解决方案字符串。
RRDRRDRDLDLDULLDLDRDDURDRRDRR

一项类似的计算表明，经过将近85小时的运算，没有长度为28的解决方案存在。
这是我用来创建SAT问题的快速且简单的Haskell程序：
import Data.List(tails,nub)
import Data.Bits
import Numeric(showHex)
import System.Environment(getArgs)

data Lit = Lit Bool [Char]

type Wall = Int -- [Bool]

lit s = Lit True s
litS s = lit (s "")

inv (Lit b s) = Lit (not b) s

instance (Show Lit) where
  showsPrec _ (Lit b s) = showString (if b then "" else "~") . showString s
  showList = showString . unwords . (map show)

showDir d = showChar ("NESW"!!d)
dir n d = litS $ showChar 'D' . shows n . showDir d

showStuff n s p = showHex n . showChar (['A'..]!!p) . shows s
pos n s p = litS $ showChar 'P' . showStuff n s p
posh n s p h = litS $ showDir h . showStuff n s p

opdir :: Int -> Int
opdir d = (d+2) `mod` 4

(<-&) :: Lit -> [Lit] -> [[Lit]]
l <-& ls = lt : lf where 
  lt = l : map inv ls                   --      l or ~l1 or ~l2 ...
  lf = [ [ inv l, li ] | li <- ls ]     --      ~l or li , all i

(<-|) :: Lit -> [Lit] -> [[Lit]]
l <-| ls = lf : lt where 
  lf = (inv l) : ls                     --      ~l or l1 or l2 ...
  lt = [ [ l, inv li ] | li <- ls ]     --      l or ~li , all i

atmostone l = [ [inv a, inv b] | (a:bs) <- tails l, b <- bs ]

dirconds n = concat [ atmostone [ dir i d | d <- [0..3]]
                    | i <- [0..n-1] ]

boundary p = (p<5) || (p>24) || (p `mod` 5 == 0)
positions = [ p | p<-[0..24], not (boundary p) ]
start = head positions
stop = last positions
wp = [ if boundary p then 0 else p - 4 - p `div` 5 | p <- [0..23]]
       ++ [1,0,0,0,0,0]

wallat :: Wall -> Int -> Bool
wallat w p = testBit (4*w+1) (wp!!p) -- (True:False:w) !! (wp!!p)

jump:: Int -> Int -> Int
jump pos dir =  pos + ([-5,1,5,-1]!!dir)

freestep :: Wall -> Int -> Int -> Maybe Int
freestep w pos dir = let np = jump pos dir in 
           if wallat w np
              then Nothing
              else Just np

reach :: Wall -> Int -> [Int]
reach w p = [ np | Just np <- map (freestep w p) [0..3] ]

reachable :: Wall -> [Int]
reachable w = go [start] [start] where
                 go seen [] = seen
                 go seen front = let new = nub [ n | p <- front,
                                                     n <- reach w p,
                                                     n `notElem` seen ]
                                 in go (seen++new) new

nicereachable :: Wall -> Maybe [Int]
nicereachable w =
  let r = reachable w
  in if and [ p `elem` r || wallat w p | p <- positions]
       then Just r
       else Nothing

mazestepdirposconds w n p d =
  let ph = posh w (n+1) p d
      conds = case freestep w p d of
                (Just np) -> ph <-& [ pos w n np, dir n (opdir d) ]
                Nothing   -> ph <-& [ pos w n p, dir n d ]
  in (ph,conds)

mazestepposconds w n p =
  let cnds = map (mazestepdirposconds w n p) [0..3]
      ps = pos w (n+1) p
  in ( ps <-| (map fst cnds)) ++ (concatMap snd cnds)

mazestepconds w r n = concatMap (mazestepposconds w n) r

mazeconds w len r = [ pos w 0 start ] :
                    [ pos w i stop | i <- [6..len] ] :
                    (concat [ atmostone [ pos w s p | p <- positions ] 
                                          | s<-[0..len] ]) ++
                    (concatMap (mazestepconds w r) [0..len-1])

conds l = dirconds l ++ 
          concat [ mazeconds w l r |
                   (w,Just r) <- [(i,nicereachable i)|i<-[0..2^14-1]]]

main = do
         [n] <- getArgs
         mapM_ print $ conds (read n)

该程序需要一个命令行参数，一个整数表示解字符串的长度。输出是一个CNF SAT问题，每行一个子句，符号文字和波浪线表示否定。这是Donald Knuth用于他的SAT求解器此处的格式。我使用他的SAT-TO-DIMACS程序将其转换为更常见的DIMACS格式。它是用CWEB编写的，因此您需要使用ctangle将其转换为C程序。您还需要gb_flip.w。该程序从stdin读取并写入stdout，您需要给它一个选项，例如h20，以增加其哈希表大小。

为了打破对称性，我添加了单元子句 D0E 来强制第一步向右走。（请注意，我使用了 NESW 而不是 URDL，因为之前我阅读过 一个类似的问题 使用这些作为方向。）
该程序考虑了所有 2423 个迷宫，其中每个位置都是可达或者是墙壁。正如 @Hans_Olsson 所观察到的那样，只需要考虑 2083 个迷宫，其中每个位置都是墙壁或者可以到达但不经过目标点。为了优化程序仅考虑这些迷宫，请在 reachable 的定义中，在 p <- front, 后面添加 p /= stop,。
编码方式：
（我会添加与程序所做的描述相关的备注。如果您只对编码感兴趣，可以忽略它们。）

让len成为我们正在搜索的解的长度， 让i成为一个范围在0<=i<=len（除非另有说明）的整数。 让m涵盖所有考虑的迷宫，让p涵盖特定迷宫的可到达位置。 可到达的位置包括起始位置和目标值start和stop。 让d涵盖四个可能的方向。

（程序将m作为十六进制14位数字编码输出墙壁位置，将p作为大写字母输出。 它不一致地使用变量名：n用于m或i或len，w（墙）用于m，s（步骤）用于i，在某些情况下还使用h（助手）代表d。）

对于每个 i<len 和每个 d，都有一个变量 D<i><d> 表示解决方案的第 i 步是朝着方向 d 前进。（程序使用 dir 函数创建它们。）
对于每个 i0<len，都有子句要求最多只有四个变量 D<i0><d> 中的一个为真。
对于每个迷宫 m、i 和 p，都有一个变量 P<m><i><p> 表示在迷宫 m 中，在时间 i 到达位置 p。（程序使用 pos 函数创建它们。）
对于每个迷宫 m0，都有一个单元子句 P<m0><0><start> 确定起始位置。
对于每一个 m0 和 i0，都有一些条款要求最多只能有一个变量 P<m0><i0><p> 是 true（我们不能处于两个不同的位置）。 除了 i0=0 的情况（在这种情况下它们可以被替换为所有 p!=start 的单元条款 ~P<m0><0><p>），这些是冗余的，但似乎有所帮助。
根据D<i0><d>中给出的方向，从时间i0的迷宫到时间i0+1的迷宫的进展是使用辅助变量描述的。 对于每个m，i>0，p和d，都有变量P<m><i><p><d>。 （程序使用posh函数创建它们。为了使变量名长度限制在Knuth程序规定的8个字符以内，它们被打印成<d><m><i><p>。）
思路是每个方向都提供了一个可能的到达某个位置的原因。该变量指示在迷宫m中，在时间i时到达位置p是“由于”d。 如果我们考虑朝某个方向前进，撞到墙并从墙上反弹，就认为是从那个方向来的，那么我们可以将这些变量解释为通过从方向d到达该位置。
因此，让我们考虑一些固定的m、i<len、p和d。由于d，如何使P<m><i+1><p>成立？如果在d方向（从p来）没有墙壁，则我们可能是从那里来的；让我们称那个位置为np。如果有一堵墙，那么我们可能之前就曾经到过这里，试图去那里并撞到了墙。

因此，我们需要建立子句，以确立P<m><i+1><p><d>等价于P<m><i><p'>和D<i><d'>的合取（逻辑与），其中p'=np且如果没有墙，则d'是d的相反方向，如果有墙，则p'=p且d'=d。（程序在函数mazestepdirposconds中执行此操作。）

然后，我们只需要建立条款，对于每个、 > 0和，变量
最后，我们需要添加迷宫已解决的条件。因此，对于每个迷宫，我们需要一个条款要求其中一个变量P<m0><i><stop>为真。由于迷宫不能在6步以内被解决，我们只需要考虑。
1
你能展示一下你如何将它编码为一个 SAT 实例吗？ - templatetypedef
@גלעדברקן 对不起，我犯了一个错误，我的观点是你应该能够镜像每个解决方案，并且它也必须是一个解决方案。(用 R 替换 D，D 替换 R，L 替换 U，U 替换 L)。 - maraca
@maraca 很酷，它有效。现在我的问题是，除了镜像的解决方案之外，是否还有多个长度为29的解决方案？ - גלעד ברקן
@גלעדברקן 是的，nicereachable 检查所有位置是否可达或为墙壁。计算 length [ r | Just r <- map nicereachable [0..2^14-1]] 得到 2423。 - Christian Sievers
我的代码刚刚在95分钟内找到了这个：RRDRRDRDLDLDULLLDDRDDURDRRDRR，给定初始值为9。 - גלעד ברקן
显示剩余9条评论
4

使用元A*算法和C#，我发现以下32个和31个字符序列（迄今为止）：

RRDRRDRLDRDLDLULLLDDRDDRDRURRDRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 characters)

我使用了31个字符的序列forked Olavi's ideone，以确保没有错误。

关于迷宫计数，我使用洪水填充算法得到了3828个有效的迷宫。

Google Drive上提供了C#项目源代码和编译后的发布二进制文件（在bin\release文件夹中）。

你可以在那里输入A*搜索的起始字符串和最大搜索长度。代码已经进行了相当多的速度优化，但仍有提升空间。例如，对于每个扩展，它都会创建4个Candidate类的实例，创建新的迷宫，运行旧候选人的每一步，然后是4个不同的方向（左、右、上、下）。使用Candidate.Clone()方法可以大大提高性能，分析器显示当前热点就在那里。此外，到目前为止还没有多线程，程序在访问列表中使用的内存越来越多（在我的电脑上10分钟后约为2 GB）。请注意，在IDE中运行程序即使在发布模式下也会使其变慢，因此最好在外部启动它。

导致上述序列的基本元算法是：

  • 使用A*搜索已知长度为N且最大长度为M的字符串，从末尾逐渐删除更多字符，例如：

    搜索RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD（32个字符），M = 33

    搜索RRDRRDRLDRDLDLULLLDDRDDRDRURRRD（31个字符），M = 33

    搜索RRDRRDRLDRDLDLULLLDDRDDRDRURRR（30个字符），M = 33

    搜索RRDRRDRLDRDLDLULLLDDRDDRDRURR（29个字符），M = 33

    ...

  • 一旦找到比N短的字符串，将其用作新的最大长度进行A*搜索，以使搜索速度更快，占用的内存更少。

我尝试过的实际组合可以在源代码中看到，如下所示。时间是来自旧版本的未经优化的数据，当前版本应该快6倍左右。

        //// 33 char solution
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR", 33); // 33 chars, 00:00:00.0032911 Finished, 1 solution, best 33, visitedList length 0

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD", 33); // 32 chars, 00:00:00.0308543 Finished, 1 solution, best 33, visitedList length 3
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRD", 33); // 31 chars, 00:00:00.0871429  Finished, 2 solutions, best 33, visitedList length 14
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRR", 33); // 30 chars, 00:00:00.2536057  Finished, 2 solutions, best 33, visitedList length 49

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 33); // 29 chars, 00:00:01.0540762  Finished, 8 solutions, best 32, visitedList length 205
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 33); // 28 chars, 00:00:03.8993877  Finished, 7 solutions, best 32, visitedList length 771
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 33); // 27 chars, 00:00:10.4225150  Finished, 7 solutions, best 32, visitedList length 2069
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 33); // 26 chars, 00:00:24.2552908  Finished, 7 solutions, best 32 visitedList length 4484
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 33); // 25 chars, 00:01:44.3295165  Finished, 14 solutions, best 32, visitedList length 16600
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 33); // 24 chars, 00:16:18.6666045  Finished, 14 solutions, best 32, visitedList length 77106

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 32); // 29 chars, 00:00:00.3134699  Finished, 1 solution, best 32, visitedList length 66
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 32); // 28 chars, 00:00:01.1053798  Finished, 1 solution, best 32, visitedList length 238
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 32); // 27 chars, 00:00:03.5172143  Finished, 1 solution, best 32, visitedList length 730
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 32); // 26 chars, 00:00:07.1336796  Finished, 1 solution, best 32, visitedList length 1413
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 32); // 25 chars, 00:00:26.4906874  Finished, 2 solutions, best 32, visitedList length 5084
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 32); // 24 chars, 00:02:52.8134463  Finished, 2 solutions, best 32, visitedList length 24623
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 32); // 23 chars, cancelled after 6 seconds, finds RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 chars)

        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 31); // 23 chars, 00:01:58.4861802  Finished, 1 solution, best 31, visitedList length 18835
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRD", 30); // 22 chars, 00:00:34.6602434  Finished, 0 solution, best distance 44, visitedList length 21084  
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDR", 30); // 21 chars, 00:04:32.2439241  Finished, 0 solution, best distance 44, visitedList length 78500
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDD", 30); // 20 chars, cancelled after 10 minutes, found no solution, best distance 44
        //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLD", 30); // 19 chars, cancelled after 10 minutes, found no solution, best distance 44

        //var aStarSearch = new AStarSearch("R", 29); // Complete search, would take waaay too long and consume much memory
一个好主意和令人印象深刻的结果！如果我理解正确，如果更改必须在序列开始附近进行，则查找较短的解决方案变得困难，是吗？ - Olavi Mustanoja
不，确实在序列开头进行更改是值得尝试的下一步。这都与搜索空间有关。使用20-31个字符的起始序列和最大长度为33或更少的A搜索可以快速完成，并且结果相当不错。相反，以短的起始序列（例如“R”）开始通常会快速消耗内存和时间，就像Ilmari所说的那样。当然，这完全取决于起始序列的质量，而您的33个字符的解决方案是一个很好的开始。因此，它是20％略微不同地使用A和80％的运气 :) - schnaader
3
一些想法：
  • 在任何最优解中都不能出现子字符串RLR、LRL、UDU或DUD，因为在每个迷宫中，它们要么使机器人停留在同一位置（如果第一步被墙挡住），要么朝着第一步的方向前进一步（否则），而在每种情况下，这与执行序列中仅第一步的结果相同。RRLLRR、LLRRLL等也是如此（对于所有更长的模式也可能是如此，但我没有验证过，并且它们在裁剪搜索方面产生递减的回报）。[编辑：这不完全正确——只有当没有尚未到达
  • 在任何有效的解决方案中，如果所有的D和R交换，所有的L和U交换，我们得到另一个有效的解决方案，因为这个“翻转”的解决方案将解决所有被“翻转”绕着主对角线的迷宫——这就是所有迷宫的集合。总之，我们只需要考虑第一步是R的解决方案。
  • 使用A*搜索（或分支和界限，或完整枚举）的一种方法是，在搜索树的每个节点记录机器人在所有~4000个有效迷宫中的状态。但我们可以通过合并到目前为止无法区分的所有迷宫的状态来节省很多时间和空间。我们可以通过记录第三个“未知”单元格状态*来实现这一点。每当我们尝试将一个*单元格移动时，这个状态就会分裂成两个子状态：它变成空单元格（我们的移动成功完成），或者它变成墙（我们仍然停留在同一位置）。如果揭示这个单元格是一堵墙意味着不再可能到达目标单元格，那么就不会生成这个子状态。
例如，在尝试第一步（R）之后，在搜索树节点中完整的状态信息包括以下两个部分迷宫：
x # * *    . x * *
* * * *    * * * *
* * * *    * * * *
* * * g    * * * g

如果我们尝试进行D移动，最终会得到以下结果：
. # * *    . x * *    . . * *
x * * *    * # * *    * x * *
* * * *    * * * *    * * * *
* * * g    * * * g    * * * g

请注意，从左边的状态移动必须成功，否则机器人会被困在（1,1）的单元格中。
另一个例子是，以下部分迷宫代表了32个不同的完整迷宫（对应着32种*单元格解决方法），每个迷宫都有相同的最优解。
x # * *
. # * *
. # # *
. . . g

虽然仍然可以使用templatetypedef的BFS启发式算法来进行A*搜索，但是现在每个单元格可以处于3种状态之一，这增加了预计算距离的总数，为16 * 3 ^ 14 = 76527504，但仍然可管理。我们需要将可以假定3种状态的项目集表示为3的幂次和以形成查找表的索引，这不像处理2状态项目那样快速或方便，但也不太难：唯一昂贵的操作是除以3，这可以通过乘以0x55555556并保留64位结果的前32位来完成。
+1，你的第一个观点可以轻松加速@Vincent的实现（他获得长度为k的所有移动排列）。 - Olavi Mustanoja
@MooingDuck：我觉得你误解了我的意思：我们需要尝试所有的迷宫；我们不需要尝试以D开头的任何移动序列。 - j_random_hacker
哦，我明白了，我把“解决方案”解释成了“当前路径”，但这不是你说的。 - Mooing Duck
这对于生成所有可能的迷宫很有用，但并没有涉及到所有可能的路径。即使假设第一步是向右移动，如果你看看必须成功的R->D，那么是RD、RRD、RRRD、RURD、RRUD、RURRD、RRURD，还有...这还不包括任何L！实际上，我们可以丢弃任何路径，其中包含UD、DU、LR、RL，当第一个点不可能是终点时，也可以在第一个D之前丢弃所有的U... - Mooing Duck
@MooingDuck：这是真的，但仅当它适用于每个迷宫时才成立。例如，在R->D示例中，虽然它适用于最左边的迷宫，但它不适用于最右边的迷宫：在那个迷宫中，机器人在D步骤上取得了进展。 - j_random_hacker
@MooingDuck：实际上，忘记我之前评论中的第二句话，那不是很恰当的例子。但仍然存在这样一种情况，即您的条件必须在每个可能的迷宫（我们尚未到达g的迷宫）中保持，以使其成为安全的修剪步骤。换句话说，如果任何机器人可以向某个方向取得进展，我们必须考虑朝着那个方向移动。 - j_random_hacker
3
看起来您可以在这里使用A*搜索，将所有迷宫的最大启发式作为启发式。这个保守估计了到解决方案的距离，并可能会给出合理的第一步。
由于所有的迷宫都很小，你可以通过从每个迷宫的结尾反向运行BFS来构建每个完美的启发式，以预先计算每个点到每个迷宫目标的距离。如果您将其缓存到查找表中，您可以拥有一个每个迷宫的启发式，它完美地告诉您剩余的最小移动次数。
我实际上还没有尝试过这个，所以这仍需要实验验证，但我认为这将是解决方案的绝佳起点。
编辑：我刚刚读到注释，说明每个机器人都必须至少访问一次目标，不一定要结束在目标上。在这种情况下，将启发式修改为从任何尚未命中目标的机器人到目标的最大距离。
希望这可以帮助！
我尝试获取所有迷宫在其各自当前位置的最小步数，并将所有这些步数相加，然后进行移动以得到最低总和。但由于向右和向下之间存在无限的平局，所以它没有起作用。 - Olavi Mustanoja
我接下来会尝试A*算法，虽然我认为我的前一个得分（78个命令）就是来自这个想法:D - Olavi Mustanoja
我尝试使用A*算法解决这个问题，但是虽然它可以轻松解决3x4的情况，但是在4x4的情况下无法很好地扩展：分支因子太高，启发式不够区分，最终会使用过多的内存（即使将访问状态哈希为64位后，我也用完了15GB的内存）。我认为在这里使用启发式引导的迭代加深搜索(IDDFS)可能会更好。 - Ilmari Karonen
一种更精细的启发式方法是对每个迷宫的最小距离求和，然后除以迷宫数量。这将有利于使某些迷宫更接近解决方案的移动，但它仍然是一个有效的启发式方法，因为它必须小于这些最小值中的最大值。此外，如果两个部分解仅在它们的最大最短路径上不同，则它将按照原始启发式方法排序它们。还有其他变化可能，例如对于某个0 <= a < 1，取a （max-min-path）+（1-a）（min-min-path）。 - j_random_hacker
@IlmariKaronen：或者你可以通过准确计算解决某个选定的k个迷宫子集所需的最小移动次数来获得*更强大的下界。这是在一个16^k-顶点图中计算k元组机器人位置的最短路径 - 对于k=2，这已经太大了无法使用查找表，但仍然可以使用Dijkstra算法进行准确计算。我会选择k=2，并选择到目标距离最远的两个迷宫。另外，别忘了丢弃所有LB > 目前最佳UB（当前为29）的解决方案 :) - j_random_hacker
1
我很快地做了一个实现（如果您感兴趣，可以在这里看到，但有点乱）。我不确定这是否与@templatetypedef所描述的方法类似。我基本上执行以下操作：
  1. 生成所有迷宫并计算每个单元格到终点的距离（过滤掉所有具有无法到达区域的迷宫，因为这些等效于在那些位置有墙的迷宫）。
  2. 同时遍历所有迷宫。当前得分是尚未到达终点的所有迷宫中到终点的总距离。
  3. 计算四个可能方向的得分。贪心地移动到具有最佳（最低）得分的方向。
这种方法会收敛，但需要103步。然后我尝试更深入地观察，因此不是贪心地选择最佳下一步，而是贪心地选择最佳的k个下一步序列。
我将此方法运行到k = 10，结果如下：
 k | length | sequence
--------------------
 1 |   103  | RDRDRDRDRLDDRRDRURRDLLDDRURURRDDLLLDDRRDRURRUURRRDDDULLLDDDRRRDLLDDRRLURRLLUDRRDDRRRLUUURRRDDDULLDDRDRR
 2 |    86  | RDRDRDRDRLDDRRDRURRDLLDDRUURRDRDLLLDDRDRURRUURRDRDDULLLDDDRRDRRLULLDDRDRURRLUURURRDDRD
 3 |    79  | RDRDRDRDRLDDRRDRURURDRDLLDDLDRDRRDRURURURRDDDULLLDDRDRRRLULLDDRDRRLURURDRURRDDD
 4 |    70  | RDRDRDRDRLDDRRDRUURRDLLDLDDRDRURUURRDRDDLULLLDDRDRRRDLLDDRRRLUURURRDDD
 5 |    73  | RDRDRDRDRLLDDRRDRURRURRDDDULLLDDRDRDRUURURRDDRDLULLDDRDRRLUURURRDLLLDDRRR
 6 |    70  | RDRDRDRLDRDRDUURRDLLLDDRDRDRURUURRDDULLLDDRDRRRLUUURRRDRLLDDULLDDRDRRR
 7 |    64  | RDRDRDRLDDRRDRLLDDRURUURDRDDULLLDDRDRRDRLURURURRDLDULLDDLLDRDRRR
 8 |    67  | RDRDRDRDLLDDRRDRURUURRDDULLLDDRDDRUURRDRURRDLLLDULLDDRDRRLUURURRDDD
 9 |    64  | RDRDRDRDRLLDDRURRDDRUUURRDDULLLDDRDRDRRLUUURRRDLDULLDDLLDRDRURRD
10 |    58  | RDRDRDRDRLLLDDRURDRDRUUURRDDDLULLLDRDDRRURRDRRLDDUURURRDDD

当然，对于大的 k 值，这种方法变得不可行。由于 OP 表示该问题可以仅使用 29 步解决，因此这种贪心方法似乎不是最佳选择...
你能发布一下你有的解决方案吗？ - Nuclearman
@Olavi 我稍微更新了算法，结果略有改善。仍然无法与你的41相比。干得好！ - Vincent van der Weele
@VincentvanderWeele 做得好！我今天稍后会研究你的更改 :) - Olavi Mustanoja
1

我們來思考一下這個問題。

考慮這個重複的模式 DRDRDRDRDRDR。我們可以通過呈現類似以下的方式使機器人出錯，

xx#x
x#xx
xxxx
xx#x

如果以Right（RDRDRDRDRDRD）或者Down（DRDRDRDRDRDR）开头都不行。


然而，让我们考虑重复出现的模式RRDDRRDDRRDD。为了让机器人失误，我们需要在某个地方设置一个死路。让我们考虑可能性，并看看是否能找到一种模式，使得两种起始移动方式（即RR或DD）都会失败。

1

x#xx
#xxx
xxxx
xxxx

显然这是一个无法解决的迷宫。

2

xx#x
x#xx
xxxx 
xxxx

这会使RRDDRRDDRRDD无法通过。现在，我们需要添加哪些块才能使它也无法通过DDRRDDRRDDRR呢？试试看，你会发现没有办法添加块来同时阻止DDRRDDRRDDRR并保持一个可解的迷宫。

3

xxx#
xx#x
xxxx
xxxx

同第二条。

4 5 6 8 9 10

xxxx    xxxx    xxxx    xxxx    xxxx    xxxx
xxx#    x#xx    xx#x    xxxx    xxxx    xxxx
xxxx    #xxx    x#xx    xxx#    x#xx    xx#x
xxxx    xxxx    xxxx    xxxx    #xxx    x#xx

不要跌倒。

7

xxxx
xxx#
xx#x
xxxx

显然无法添加方块，使得DDRRDDRRDDRRDDRR也会失败并保持可解性。

11 12

xxxx    xxxx
xxxx    xxxx
xxx#    xxxx
xx#x    xxx#

无法解决的迷宫。


考虑到似乎没有迷宫可以同时失败于RRDDRRDDRRDDRRDD和DDRRDDRRDDRRDDRR，也许可以通过尝试一种模式，向后遍历步骤并从另一个可能性开始（即，如果我们以RR开头，则以DD开始，反之亦然），来形成解决方案。

我希望我有更多时间思考在这种情况下保证向后遍历步骤会回到起点的必要性。

更新

正如评论所指出的那样，两步序列确实会失败很多迷宫。然而，一个由28个步骤组成的序列DDRRDDRRDDRRLLUURRDDRRDDRRDD，基于这个想法，似乎可以解决3828个迷宫中的3456个。

@MooingDuck 打败了我 :D 无论如何，我列出了一小部分失败的案例：**pastebin**。不过我很喜欢你的想法！如果我们有一个序列，在第二次运行时镜像，肯定可以达到目标，这将仅用29步解释答案！ - Olavi Mustanoja
有这么少的失败案例子集，可能只需要在这五个中添加一个“逃逸”，然后继续原始模式到出口：URURRDLDL-DDDRR？那是什么？30？假设我没有错误？ - Mooing Duck
@MooingDuck 我只是随意从所有失败的案例中挑选了一些。大约有 800 个失败了。 - Olavi Mustanoja
1
@MooingDuck 确切地说是880 - Olavi Mustanoja
1
我从原始帖子中取出了长度为41的字符串并尝试将其最小化。 我发现可以删除4个字符。虽然不多，但我认为值得注意。 因此，从这个字符串 RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD，我得到了这个字符串 RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDRD。它通过了 @Vincent 方法生成的每个迷宫。
我还检查了本线程的其他结果，但没有任何显着差异。
我使用了 @Vincent 代码的一部分来生成迷宫。
这里是代码和示例的链接。 http://ideone.com/9OFr5E 如果我哪里做错了，请告诉我。
我刚刚正在做这件事。用略微不同的顺序，它有39个字符长，但我能够手动将其缩短为33个字符长。我将在一秒钟内编辑我的帖子。 - Olavi Mustanoja
1
以下是Python代码，可以在95分钟内找到第三个序列RRDRRDRDLDLDULLLDDRDDURDRRDRR，给定了初始的9个方向（请注意，Christian Sievers在给定初始的9个方向后在45分钟内找到了他们的第二个序列）。 这是一个深度优先搜索算法，其中包含一些预计算，可能只是幸运。 Hans Olsson 展示了如果提供了15个初始步骤，我们可以找到更多的29长度序列（下面的代码在17秒钟内找到了一个）。
有关U和L的数量限制，这取决于Christian Sievers answer中序列的知识，并且还要防止模式RLR和RRLL（以及可比较的镜像和旋转），如j_random_hacker所指出noted。此外，还检查移动是否实际上在至少一个迷宫中改变了一些内容（共有2432个...简化该检查可能节省更多时间），以及预计算的最少移动次数仍然需要小于或等于序列中分配的移动次数（限制为29）。任何一个迷宫状态的编码都是32位。
另外请注意，只有2423个可达迷宫，而不是本页面其他地方出现的3828个（后者列表包括仅在不可达位置不同的迷宫）。
文件mazes.txt（可在here找到）包含所有3828个迷宫，代码将其减少。
"""
Let f(state, move, seq) represent the optimal sequence for the simultaneous maze solution. We define state as a list of 3828 numbers since we can represent each maze's state with 16 bits for the maze and 16 bits for the robot's position.

We can precalculate the shortest route to the start for each positon for each maze. Moving anywhere from the start position will just stay at the start. Then our search backwards from the end becomes:

    f(state, 0, seq) = seq

    f(state, move, seq)
      if position is too far from start for any maze, given move:
        return []
      otherwise:
        return union of f(next_state(mv), move - 1, reverse(mv) + seq)
          where mv <- [r, l, u, d]

There are at most 2423 * 16 = 38768 states for any one maze but many are unreachable / invalid (I know, 2423 to even a small power is a huge number). We can also try more a restricted distance pruning by, for example, looking at the difference in distance between different maze states. Also, we'll remember not to use RLR, LRL, UDU or DUD as j_random_hacker pointed out.

0111
0111
0000
1000

0b0111011100001000
"""

# Does not differentiate a completed maze
def move_pre(maze, direction):
  pos = maze >> 16
  temp = pos
  shift = -1
  while temp:
    shift += 1
    temp >>= 1
  if direction == 'l':
    if (pos not in [1<<3, 1<<7, 1<<11, 1<<15]) and not (maze & (1 << (shift + 1))):
      shift = shift + 1
  if direction == 'r':
    if (pos not in [1, 1<<4, 1<<8, 1<<12]) and not (maze & (1 << (shift - 1))):
      shift = shift - 1
  if direction == 'u':
    if pos < (1 << 12) and not (maze & (1 << (shift + 4))):
      shift = shift + 4
  if direction == 'd':
    if pos > (1 << 3) and not (maze & (1 << (shift - 4))):
      shift = shift - 4
  maze ^= (pos << 16)

  return maze | (1 << (shift + 16))

def get_moves_pre(maze, visited):
  l = move_pre(maze, 'l')
  r = move_pre(maze, 'r')
  u = move_pre(maze, 'u')
  d = move_pre(maze, 'd')
  return [m for m in [l, r, u, d] if m != maze and not (m >> 16) & visited]

# Returns 0 if the maze is completed
def move(maze, direction):
  if not maze:
    return maze

  pos = maze >> 16
  temp = pos
  shift = -1
  while temp:
    shift += 1
    temp >>= 1
  if direction == 'l':
    if (pos not in [1<<3, 1<<7, 1<<11, 1<<15]) and not (maze & (1 << (shift + 1))):
      shift = shift + 1
  if direction == 'r':
    if (pos not in [1, 1<<4, 1<<8, 1<<12]) and not (maze & (1 << (shift - 1))):
      shift = shift - 1
  if direction == 'u':
    if pos < (1 << 12) and not (maze & (1 << (shift + 4))):
      shift = shift + 4
  if direction == 'd':
    if pos > (1 << 3) and not (maze & (1 << (shift - 4))):
      shift = shift - 4
  maze ^= (pos << 16)

  if shift == 15:
    return 0

  return maze | (1 << (shift + 16))

"""
0111
0111
0000
1000
"""
#a = 0b0111011100001000
#print "{0:b}".format(move(a | (1 << 16), 'd'))

def get_moves(maze, visited):
  l = move(maze, 'l')
  r = move(maze, 'r')
  u = move(maze, 'u')
  d = move(maze, 'd')
  return [m for m in [l, r, u, d] if m != maze and not (m >> 16) & visited]

def least_steps(maze):
  visited = 0
  stack = [(i, 1) for i in get_moves_pre(maze, visited)]

  while stack:
    (new_maze, count) = stack.pop(0)
    # robot is in starting position
    if new_maze & (1 << (16 + 15)):
      return count
    visited |= (new_maze >> 16)

    stack.extend(
      [(i, count + 1) for i in get_moves_pre(new_maze, visited)]
    )

#print least_steps(0b10111011100001000)

least_moves = {0: 0}

# We can reduce the number of mazes by grouping only reachable sections
def reachable(maze):
  global least_moves
  visited = 0
  stack = get_moves_pre(maze, visited)

  while stack:
    new_maze = stack.pop(0)
    # hash least moves
    least_moves[new_maze] = least_steps(new_maze)
    visited |= (new_maze >> 16)

    mvs = get_moves_pre(new_maze, visited)
    if mvs:
      stack.extend(mvs)

  return visited

#print reachable(0b10111001110111000)
#print reachable(0b10110001010111000)

rs = {}

print "precalculating..."
for L in open("mazes.txt"):
  L = L.strip()
  maze = int(L, 2) | (1 << 16)
  r = reachable(maze)
  if r in rs:
    rs[r].append(maze)
  else:
    rs[r] = [maze]

mazes = []

for r in rs:
  mazes.append(rs[r][0])

print "%s reachable mazes" % len(mazes)

def get_next_params(mazes, seq, rd_count, seq_length, max_rd_count):
  global least_moves
  if len(seq) == seq_length:
    return []

  next_states = []
  mazes_state = [None] * len(mazes)

  if seq[-2:] != "ud" and seq[-3:] != "ddu":
    for i, maze in enumerate(mazes):
      if seq_length - len(seq) < least_moves[maze]:
        return []
      mazes_state[i] = move(maze, 'u')
    next_states.append((mazes_state[:], seq + 'u', rd_count))

  if seq[-2:] != "lr" and seq[-3:] != "rrl":
    for i, maze in enumerate(mazes):
      if seq_length - len(seq) < least_moves[maze]:
        return []
      mazes_state[i] = move(maze, 'l')
    next_states.append((mazes_state[:], seq + 'l', rd_count))

  if rd_count < max_rd_count:
    if seq[-2:] != "rl" and seq[-3:] != "llr":
      for i, maze in enumerate(mazes):
        if seq_length - len(seq) < least_moves[maze]:
          return []
        mazes_state[i] = move(maze, 'r')
      next_states.append((mazes_state[:], seq + 'r', rd_count + 1))

    if seq[-2:] != "du" and seq[-3:] != "uud":
      for i, maze in enumerate(mazes):
        if seq_length - len(seq) < least_moves[maze]:
          return []
        mazes_state[i] = move(maze, 'd')
      next_states.append((mazes_state[:], seq + 'd', rd_count + 1))

  return next_states


def different(state, new_state):
  return any([a != b for (a,b) in zip(state, new_state)])

def f(mazes, seq_length, max_rd_count, starting_seq='l', rd_count=0):
  global start_time
  stack = [(mazes, starting_seq, rd_count)]
  count = 0

  while stack:
    mazes, seq, rd_count = stack.pop()

    count += 1
    if not (count % 1000):
      print "%s sequences so far, current length: %s, %s seconds" % ("{:,}".format(count), len(seq), time.time() - start_time)

    if not any(mazes):
      return seq

    for (new_mazes, new_seq, new_rd_count) in get_next_params(mazes, seq, rd_count, seq_length, max_rd_count):
      if (different(mazes, new_mazes)):
        stack.append((new_mazes, new_seq, new_rd_count))

  return None

#         x x xxx x    x
# rrdrrdrdldldulldldrddurdrrdrr
# llullulururudrruruluudlullull
#         x x xxx x    x
def play(maze, seq):
  for m in seq:
    maze = move(maze, m)
  return maze 

# Start into the sequence
new_mazes = []
seq = "llullulur"#urudrruruluudlullull"
rd_count = 0
for c in seq:
  if c in ['r', 'd']:
    rd_count += 1
for m in mazes:
  new_mazes.append(play(m, seq))

print "starting sequence: %s\nrd count: %s" % (seq, rd_count)
import time
print "starting calculation..."
start_time = time.time()
print f(new_mazes, 29, 7, seq, rd_count)
print("--- %s seconds ---" % (time.time() - start_time))
1
改进现有解决方案的想法不仅可以基于起始字符串进行搜索，还可以同时具有固定的起始和结束字符串。
即使没有并行化，也足够快速，您可以在几分钟内从32步解决方案转换为29步解决方案。
对于m步的结束字符串，您需要找到这样的方格：从那里开始，并应用结束部分序列将击中终点。（在每一步中，您考虑每个点的两个可能的前任，并添加终点。对于一个R移动的方块S，它的两个可能的前任是方块S和其左侧邻居（如果有效），Move（S，L）。只有在Move（S'，R）== S时才会添加这些内容。）（稍后可以发布整个代码。）
然后，它们被赋予距离m，以及它们的邻居距离m + 1等。
然后，您可以使用此启发式方法应用A *搜索。

这个过程花了1分钟，从RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD（长度为32），只保留前7个和后11个字符，得到RRDRRDRDLDDULDLDLDRDDRDURRDRRD（长度为30），然后保留前15个字符，花费半分钟找到RRDRRDRDLDDULDLDLDRDRDURDRRDR（长度为29）。

请注意，有2423个可达迷宫，但只需要考虑2083个，因为其他的方格只能通过通过终点来到达。

哦，当我无意中枚举没有终点的迷宫时，我看到了2083这个数字。我不确定它是否正确，所以我还是用了2423。 - גלעד ברקן
我在回答中发布的代码在17秒内运行成功（参考2423个迷宫，而非2083个），提供了RRDRRDRDLDDULDLDLDRDDRDURRDRRD的前15个字符。 - גלעד ברקן
只需要考虑2083个迷宫，这是一个很好的观察！ - Christian Sievers
-1

虽然不是一个确切的答案，但其他人可能会发现它对于得出答案很有用。

总体而言，似乎最好的方法是对角线移动。然而，我遇到了一些棘手的情况，我在下面列出了这些情况，这些情况似乎会使我手工想出的方法失效。

1 0 0 0    1 0 0 0    1 0 0 0    1 0 # Z    1 0 # Z
0 # X #    0 # # X    0 # # X    # 0 X 0    # 0 # Z
0 Z # Z    0 Z Z #    0 0 0 #    Z Z # 0    Z 0 X 0
0 0 0 1    0 0 0 1    X # 0 1    Z Z # 1    Z Z # 1

其中：1 表示起点/终点，0 表示空位，# 表示墙壁，Z 可能是墙壁或空位，X 是问题点，可能会卡住或难以到达。

一种可以用最少的指令解决上述迷宫的方法应该相当接近于解决任何迷宫的方法。

基本上是DRDRDRDRD :D - Olavi Mustanoja
行和列可以交换，所以它可以是RDRDRDRDR:D。似乎墙随从迷宫解算法也可能很有用。 - Nuclearman
@OlaviMustanoja：建议的解决方案是“向斜下右走”x8。我的逃脱方式似乎是遵循גלעד ברקן的答案，先“向斜上右走”x2.5，然后“向斜下右走”x1，“向斜下左走”x2.5，最后“向斜下右走”x2。我敢打赌那里有个提示。 - Mooing Duck
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接