algorithm - 以最少的 Action 同时解决所有 4x4 迷宫

Question

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

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

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

例如，可以使用命令序列 DDDRRR 解决这个特殊的迷宫问题。或 RRRDDD ，其中 R = 右，L = 左，U = 上，D = 下(废话)。

然而，这些序列都不能解决这个迷宫:

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

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

我已经实现了一个算法，它让我获得了 78 个命令的获胜序列。我确信至少存在 29 个命令的解决方案(其他人完成了这个)。

这个问题实际上已经有几年了，所以我已经丢失了当时使用的算法，但是基本思想是在我生成的所有迷宫中进行搜索，并始终选择导致解决最多的路线迷宫。这实际上让我得到了一个长度略超过 78 的序列；我手动减少了一些我注意到多余的命令。

是的，像往常一样，暴力破解需要数年时间。

如果我没记错的话，可能的迷宫少于 4000 个(可能的迷宫是存在左上角和右下角之间的路径)。

哦! 机器人在执行命令期间至少访问目标一次就足够了。也就是说，它不必在最后一个命令之后坐在目标上。

我有没有捕获任何人的兴趣？我应该如何处理这个问题以获得更有效的答案？感谢您的考虑:)

有趣的事:Pastebin

它是一个(非常)草率地组合在一起的 Java。它应该编译并运行:)
该程序有点同时播放约 4000 个迷宫。该程序采用 UP、LEFT、DOWN 和 RIGHT 的输入(w、a、s、d)，然后模拟移动，显示一些统计数据。如果您尝试一下，您在屏幕上看到的是每个迷宫每个位置的障碍物总数，以及每个迷宫当前位置的总数。很难解释:) 如果你有问题，问我。

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

进步

我从 this user's 间接得到了这个想法 answer ，并进一步用 Mooing Duck 对其进行建模在聊天中。这个想法是找到一个序列来解决迷宫的右侧。也就是说，一个解至少解决了所有迷宫的一半，当 镜像并从头开始运行 解决剩余的迷宫。

插图:

首先找到一个序列，它的第一个命令是正确的，例如解决这个迷宫:

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 目标，但我仍然在寻找相同口径的以编程方式获得的解决方案。从序列中删除字符时我没有使用任何逻辑 - 我只是简单地删除一个字符并检查它是否解决了所有迷宫，冲洗并重复。

Answer 1

我将此问题编码为 SAT 4280308 个变量和 21975717 个子句(包括许多多余但看似有用的子句)的问题 treengeling大约 100 1/2 小时后解决，找到这个长度为 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 求解器的格式 here .我使用他的 SAT-TO-DIMACS 将其转换为更常见的 DIMACS 格式程序。它是用CWEB编写的，所以你必须用 ctangle把它变成一个C程序。 .您还需要 gb_flip.w .该程序从标准输入读取并写入标准输出，您需要给它一个选项，如 h20增加其哈希表的大小。

为了打破对称性，我添加了单元子句 D0E迫使第一步向右走。 (请注意，我使用了 NESW 而不是 URDL，因为我之前阅读了 a similar problem 使用这些作为说明。)

该程序考虑了所有 2423 个迷宫，其中每个位置都是
触手可及或一堵墙。作为@Hans_Olsson
observed ,
只需要
考虑 2083 个迷宫，其中每个位置要么是一堵墙，要么是可到达的
没有通过目标。优化程序只考虑这些
迷宫，添加 p /= stop,之后 p <- front,在 reachable的定义中.

编码

(我将添加与程序功能描述相关的备注。
如果您只对编码感兴趣，它们可以被忽略。)

让 len是我们正在寻找的解决方案的长度，
让 i是一个范围为 0<=i<=len 的整数(除非另有说明)。
让 m覆盖所有考虑的迷宫并让 p范围覆盖
特定迷宫的可达位置。
可到达的位置包括值 start和 stop为了
起始位置和目标。
让 d覆盖四个可能的方向。

(程序输出 m 作为十六进制 14 位数字编码墙
位置，和 p作为大写字母。它使用变量名
不一致: n为 m或为 i或为 len , w (墙壁)为 m , s (步骤)为 i ，在一种情况下 h ( helper )为 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>是真的(我们不能处于两个不同的位置)。
这些都是多余的，除了 i0=0 (可以更换的地方
按单位条款 ~P<m0><0><p>所有 p!=start )，但似乎有帮助。

时间迷宫的进展 i0到时 i0+1根据 D<i0><d> 中给出的方向使用辅助变量进行描述。
每个 m , i>0 , p和 d ，有变量 P<m><i><p><d> .
(程序使用 posh 函数创建它们。它将它们打印为 <d><m><i><p>为了将变量名长度保持在
由 Knuth 的程序强加的 8 个字符。)

这个想法是每个方向都给出了一个位置的可能原因
可以达到。该变量表明
在迷宫中 m , 时间 i职位 p达到“因为” d .
如果我们考虑朝某个方向前进，撞墙并从
它来自那个方向，然后我们可以解释变量
从方向 d 到达该位置.

所以让我们考虑一些固定的 m , i<len , p和 d .
怎么可以 P<m><i+1><p>真实，因为 d ?
如果方向没有墙 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 中执行此操作。)

然后，我们只需要为每个 m0 建立条款, i0>0和 p0 ,
变量 P<m0><i0><p0>等价于析取(逻辑或)
四个变量 P<m0><i0><p0><d> .

最后，我们需要添加解决迷宫的条件。
所以，对于每个迷宫 m0 ，我们需要一个条款要求其中一个变量 P<m0><i><stop>是真的。由于迷宫不能在少于 6 个步骤中解决，
我们只需要考虑 i>=6 .