21

最近几天，我一直克制自己的硕士学习，一直专注于这个（看似简单的）难题：

有这个 10*10 的网格构成了一个包含 100 个可用地点的正方形。目的是从一个角落开始，根据一些简单的“遍历规则”遍历所有地方并达到第 100 号（如果您是程序员，则为 99 号，而不是从 0 开始：）

遍历的规则是：
1. 沿纵横轴跳两个空格
2. 沿对角线跳一个空格
3. 每个方格只能访问一次

为了更好地可视化，这是一个有效的遍历示例（直到第 8 步）：
示例遍历 http://img525.imageshack.us/img525/280/squarepuzzle.png

出于无聊，我一直在手动解决这个难题。多年来，我时不时尝试手动解决，但从未超过96。听起来容易吗？试试自己，看看自己:)

因此，为了解决这个问题，我用 Python 开发了一个简短的（大约 100 行代码）程序。我是这门语言的初学者，我想看看我能做什么。
该程序简单地应用了详尽的尝试和错误解决技术。换句话说：蛮力深度优先搜索。

我的问题从这里出现：不幸的是，该程序无法解决问题，因为状态空间太大以至于搜索永远不会结束而没有找到解决方案。它可以毫不费力地上升到 98 号（并打印出来），但也不是一个完整的解决方案。
该程序还打印出到目前为止它所覆盖的搜索树的长度。几分钟后，从第 65 个元素开始的遍历列表就被覆盖到最后，只有一条路径。这个数字在指数增加的时间段内减少。我已经运行代码很长一段时间了，无法超过 50 个障碍，现在我确信了。

除非我永远运行它，否则这种简单的方法似乎是不够的。那么，如何改进我的代码以更快、更高效地提出解决方案呢？

基本上，我期待看到有关如何：

  1. 捕获和利用特定于该问题的领域知识

  2. 应用编程技术/技巧来克服疲惫

    ..并最终实现一个实质性的解决方案。

提前致谢。

修订
感谢 Dave Webb 将问题与它所属的域相关联：

这与骑士巡回赛问题非常相似，后者涉及在棋盘周围移动骑士而不重新访问同一个方格。基本上这是同一个问题，但有不同的“遍历规则”。

4

7 回答 7

15

这与骑士巡回赛问题非常相似，后者涉及在棋盘周围移动骑士而不重新访问同一个方格。基本上这是同一个问题，但有不同的“遍历规则”。

我记得递归处理骑士巡回赛的关键优化是按照目标方格上可用移动数量的递增顺序执行下一步。这鼓励搜索尝试在一个区域密集移动并填充它，而不是在整个板上缩放并留下永远无法访问的小岛广场。（这是Warnsdorff 的算法。）

还要确保你已经尽可能地考虑了对称性。例如，在最简单的级别上，您的起始方块的 x 和 y 只需上升到 5，因为 (10,10) 与 (1,1) 相同，但棋盘旋转。

于 2009-04-20T12:06:28.333 回答
10

我决定看看这个问题，看看我是否可以把它分解成 5x5 的解决方案，一个解决方案的结尾从另一个角落跳开。

第一个假设是 5x5 是可解的。它很快。

所以我运行了solve(0,5) 并查看了结果。我在 Excel 中绘制了一个 10x10 编号的网格，并带有一个 5x5 的编号网格进行翻译。然后我只是搜索了#]（结束单元格）的结果，这将是下一个 5x5 开始时的跳跃。（例如，对于第一个方格，我搜索了“13]”。）

以供参考：

10 x 10 grid                       5 x 5 grid 
 0  1  2  3  4 |  5  6  7  8  9     0  1  2  3  4
10 11 12 13 14 | 15 16 17 18 19     5  6  7  8  9
20 21 22 23 24 | 25 26 27 28 29    10 11 12 13 14
30 31 32 33 34 | 35 36 37 38 39    15 16 17 18 19
40 41 42 43 44 | 45 46 47 48 49    20 21 22 23 24
---------------+---------------
50 51 52 53 54 | 55 56 57 58 59
60 61 62 63 64 | 65 66 67 68 69
70 71 72 73 74 | 75 76 77 78 79
80 81 82 83 84 | 85 86 87 88 89
90 91 92 93 94 | 95 96 97 98 99

这是一个可能的解决方案：

第一个方格：[0, 15, 7, 19, 16, 1, 4, 12, 20, 23, 8, 5, 17, 2, 10, 22, 14, 11, 3, 18, 6, 9, 24, 21, 13] 把它放在对角线跳到 5（在 10x10 中）下一个 5 x 5 的第一个角。

第二方：[0, 12, 24, 21, 6, 9, 17, 2, 14, 22, 7, 15, 18, 3, 11, 23, 20, 5, 8, 16, 19, 4, 1, 13, 10] 将它放在 10x10 中的最后一个 25 格，距离 55 有两跳。

第三格：[0, 12, 24, 21, 6, 9, 17, 5, 20, 23, 8, 16, 19, 4, 1, 13, 10, 2, 14, 11, 3, 18, 15, 7, 22] 将它放在 10x10 中的最后一个格子 97 处，距离 94 两跳。

第四方阵可以是任何有效的解决方案，因为终点并不重要。然而，解决方案从 5x5 到 10x10 的映射更难，因为正方形从对角开始。代替翻译，运行solve(24,5)并随机选择一个：[24, 9, 6, 21, 13, 10, 2, 17, 5, 20, 23, 8, 16, 1, 4, 12, 0、15、18、3、11、14、22、7、19]

这应该可以通过编程方式完成，因为已知 5x5 解决方案在端点合法移动到下一个 5x5 角时是有效的。5x5 解决方案的数量为 552，这意味着存储解决方案以供进一步计算和重新映射非常容易。

除非我做错了，否则这会为您提供一种可能的解决方案（以上 5x5 解决方案分别定义为一到四个）：

def trans5(i, col5, row5):
    if i < 5: return 5 * col5 + 50 * row5 + i
    if i < 10: return 5 + 5 * col5 + 50 * row5 + i
    if i < 15: return 10 + 5 * col5 + 50 * row5 + i
    if i < 20: return 15 + 5 * col5 + 50 * row5 + i
    if i < 25: return 20 + 5 * col5 + 50 * row5 + i

>>> [trans5(i, 0, 0) for i in one] + [trans5(i, 1, 0) for i in two] + [trans5(i, 0, 1) for i in three] + [trans5(i, 1, 1) for i in four]
    [0, 30, 12, 34, 31, 1, 4, 22, 40, 43, 13, 10, 32, 2, 20, 42, 24, 21, 3, 33, 11, 14, 44, 41, 23, 5, 27, 49, 46, 16, 19, 37, 7, 29, 47, 17, 35, 38, 8, 26, 48, 45, 15, 18, 36, 39, 9, 6, 28, 25, 50, 72, 94, 91, 61, 64, 82, 60, 90, 93, 63, 81, 84, 54, 51, 73, 70, 52, 74, 71, 53, 83, 80, 62, 92, 99, 69, 66, 96, 78, 75, 57, 87, 65, 95, 98, 68, 86, 56, 59, 77, 55, 85, 88, 58, 76, 79, 97, 67, 89]

有人可以仔细检查方法吗？我认为这是解决问题的有效解决方案和方法。

于 2009-04-20T17:33:38.937 回答
8

最终，我想出了修改后的 Python 代码来解决这个问题。我已经调整了几个小时的代码，它已经在几个小时内找到了 50 万个解决方案。
全套解决方案仍然需要彻底的搜索，即让程序运行直到它完成所有组合。但是，达到“一个”合法解决方案可以减少到“线性时间”。

首先，我学到的东西：

  1. 感谢Dave Webb 的回答和ammoQ 的回答。该问题确实是哈密顿路径问题的扩展，因为它是 NP-Hard。一开始没有“简单”的解决方案。Knight's Tour有一个著名的谜语，这只是同一个问题，不同大小的棋盘/网格和不同的遍历规则。为了详细说明问题和方法和算法已经设计了很多事情。

  2. 感谢乔的回答。该问题可以自下而上的方式处理，并且可以分解为可解决的子问题。解决的子问题可以在入口-出口点的概念中连接（一个人的出口点可以连接到另一个人的入口点），这样主要问题就可以作为较小规模问题的构成来解决。这种方法是合理和实用的，但并不完整。如果存在，它不能保证找到答案。

经过详尽的蛮力搜索，以下是我在代码上开发的关键点：

  • Warnsdorff 算法：该算法是快速获得大量解决方案的关键点。它只是说，你应该选择你的下一步行动到“最不方便”的地方，并用升序或可访问性填充你的“去”列表。最不容易到达的地方是指可能跟随动作最少的地方。

    以下是伪代码（来自维基百科）：

一些定义：

  • 如果 P 可以通过一个骑士的移动移动到 Q 并且 Q 尚未被访问，则可以从位置 P 访问位置 Q。
  • 位置 P 的可访问性是从 P 可访问的位置数。

算法：

将 P 设置为棋盘上的随机初始位置 将棋盘标记为 P 处的棋步数为“1”，每个棋步数从 2 到棋盘上的方格数，令 S 为可从输入位置访问的位置集合将 P 设置为 S 中具有最小可访问性的位置 用当前移动编号标记 P 处的棋盘 返回已标记的棋盘——每个方块都将标记有它被访问的移动编号。

  • 检查岛屿：这里对领域知识的一个很好的利用被证明是很方便的。如果一个移动（除非它是最后一个移动）会导致它的任何邻居变成一个岛，即任何其他移动都无法访问，则不再调查该分支。与 Warnsdorff 算法相结合可节省大量时间（大约 25%）。

这是我在 Python 中的代码，它解决了这个谜题（考虑到问题是 NP-Hard，在可接受的程度上）。代码很容易理解，因为我认为自己是 Python 的初学者。这些评论在解释实现方面很简单。解决方案可以通过基本的 GUI（代码中的指南）显示在简单的网格上。

# Solve square puzzle
import operator

class Node:
# Here is how the squares are defined
    def __init__(self, ID, base):
        self.posx = ID % base
        self.posy = ID / base
        self.base = base
    def isValidNode(self, posx, posy):
        return (0<=posx<self.base and 0<=posy<self.base)

    def getNeighbors(self):
        neighbors = []
        if self.isValidNode(self.posx + 3, self.posy): neighbors.append(self.posx + 3 + self.posy*self.base)
        if self.isValidNode(self.posx + 2, self.posy + 2): neighbors.append(self.posx + 2 + (self.posy+2)*self.base)
        if self.isValidNode(self.posx, self.posy + 3): neighbors.append(self.posx + (self.posy+3)*self.base)
        if self.isValidNode(self.posx - 2, self.posy + 2): neighbors.append(self.posx - 2 + (self.posy+2)*self.base)
        if self.isValidNode(self.posx - 3, self.posy): neighbors.append(self.posx - 3 + self.posy*self.base)
        if self.isValidNode(self.posx - 2, self.posy - 2): neighbors.append(self.posx - 2 + (self.posy-2)*self.base)
        if self.isValidNode(self.posx, self.posy - 3): neighbors.append(self.posx + (self.posy-3)*self.base)
        if self.isValidNode(self.posx + 2, self.posy - 2): neighbors.append(self.posx + 2 + (self.posy-2)*self.base)
        return neighbors


# the nodes go like this:
# 0 => bottom left
# (base-1) => bottom right
# base*(base-1) => top left
# base**2 -1 => top right
def solve(start_nodeID, base):
    all_nodes = []
    #Traverse list is the list to keep track of which moves are made (the id numbers of nodes in a list)
    traverse_list = [start_nodeID]
    for i in range(0, base**2): all_nodes.append(Node(i, base))
    togo = dict()
    #Togo is a dictionary with (nodeID:[list of neighbors]) tuples
    togo[start_nodeID] = all_nodes[start_nodeID].getNeighbors()
    solution_count = 0


    while(True):
        # The search is exhausted
        if not traverse_list:
            print "Somehow, the search tree is exhausted and you have reached the divine salvation."
            print "Number of solutions:" + str(solution_count)
            break

        # Get the next node to hop
        try:
            current_node_ID = togo[traverse_list[-1]].pop(0)
        except IndexError:
            del togo[traverse_list.pop()]
            continue

        # end condition check
        traverse_list.append(current_node_ID)
        if(len(traverse_list) == base**2):
            #OMG, a solution is found
            #print traverse_list
            solution_count += 1
            #Print solution count at a steady rate
            if(solution_count%100 == 0): 
                print solution_count
                # The solution list can be returned (to visualize the solution in a simple GUI)
                #return traverse_list


        # get valid neighbors
        valid_neighbor_IDs = []
        candidate_neighbor_IDs = all_nodes[current_node_ID].getNeighbors()
        valid_neighbor_IDs = filter(lambda id: not id in traverse_list, candidate_neighbor_IDs)

        # if no valid neighbors, take a step back
        if not valid_neighbor_IDs:
            traverse_list.pop()
            continue

        # if there exists a neighbor which is accessible only through the current node (island)
        # and it is not the last one to go, the situation is not promising; so just eliminate that
        stuck_check = True
        if len(traverse_list) != base**2-1 and any(not filter(lambda id: not id in traverse_list, all_nodes[n].getNeighbors()) for n in valid_neighbor_IDs): stuck_check = False

        # if stuck
        if not stuck_check:
            traverse_list.pop()
            continue

        # sort the neighbors according to accessibility (the least accessible first)
        neighbors_ncount = []
        for neighbor in valid_neighbor_IDs:
            candidate_nn = all_nodes[neighbor].getNeighbors()
            valid_nn = [id for id in candidate_nn if not id in traverse_list]
            neighbors_ncount.append(len(valid_nn))
        n_dic = dict(zip(valid_neighbor_IDs, neighbors_ncount))
        sorted_ndic = sorted(n_dic.items(), key=operator.itemgetter(1))

        sorted_valid_neighbor_IDs = []
        for (node, ncount) in sorted_ndic: sorted_valid_neighbor_IDs.append(node)



        # if current node does have valid neighbors, add them to the front of togo list
        # in a sorted way
        togo[current_node_ID] = sorted_valid_neighbor_IDs


# To display a solution simply
def drawGUI(size, solution):
    # GUI Code (If you can call it a GUI, though)
    import Tkinter
    root = Tkinter.Tk()
    canvas = Tkinter.Canvas(root, width=size*20, height=size*20)
    #canvas.create_rectangle(0, 0, size*20, size*20)
    canvas.pack()

    for x in range(0, size*20, 20):
        canvas.create_line(x, 0, x, size*20)
        canvas.create_line(0, x, size*20, x)

    cnt = 1
    for el in solution:
        canvas.create_text((el % size)*20 + 4,(el / size)*20 + 4,text=str(cnt), anchor=Tkinter.NW)
        cnt += 1
    root.mainloop()


print('Start of run')

# it is the moment
solve(0, 10)

#Optional, to draw a returned solution
#drawGUI(10, solve(0, 10))

raw_input('End of Run...')

感谢大家分享他们的知识和想法。

于 2009-04-21T13:40:39.190 回答
5

这只是http://en.wikipedia.org/wiki/Hamiltonian_path问题的一个例子。德国维基百科声称它是 NP 难的。

于 2009-04-20T12:08:15.490 回答
1

我可以进行优化以检查岛屿（即没有有效邻居的未访问空间。）并退出遍历，直到岛屿被消除。这将发生在某个树遍历的“便宜”一侧附近。我想问题是减少是否值得付出代价。

于 2009-04-20T14:25:46.580 回答
1

我想看看我是否可以编写一个能提出所有可能解决方案的程序。

#! /usr/bin/env perl
use Modern::Perl;

{
  package Grid;
  use Scalar::Util qw'reftype';

  sub new{
    my($class,$width,$height) = @_;
    $width  ||= 10;
    $height ||= $width;

    my $self = bless [], $class;

    for( my $x = 0; $x < $width; $x++ ){
      for( my $y = 0; $y < $height; $y++ ){
        $self->[$x][$y] = undef;
      }
    }

    for( my $x = 0; $x < $width; $x++ ){
      for( my $y = 0; $y < $height; $y++ ){
        $self->[$x][$y] = Grid::Elem->new($self,$x,$y);;
      }
    }

    return $self;
  }

  sub elem{
    my($self,$x,$y) = @_;
    no warnings 'uninitialized';
    if( @_ == 2 and reftype($x) eq 'ARRAY' ){
      ($x,$y) = (@$x);
    }
    die "Attempted to use undefined var" unless defined $x and defined $y;
    my $return = $self->[$x][$y];
    die unless $return;
    return $return;
  }

  sub done{
    my($self) = @_;
    for my $col (@$self){
      for my $item (@$col){
        return 0 unless $item->visit(undef);
      }
    }
    return 1;
  }

  sub reset{
    my($self) = @_;
    for my $col (@$self){
      for my $item (@$col){
        $item->reset;
      }
    }
  }

  sub width{
    my($self) = @_;
    return scalar @$self;
  }

  sub height{
    my($self) = @_;
    return scalar @{$self->[0]};
  }
}{
  package Grid::Elem;
  use Scalar::Util 'weaken';

  use overload qw(
    "" stringify
    eq equal
    == equal
  );

  my %dir = (
    #       x, y
    n  => [ 0, 2],
    s  => [ 0,-2],
    e  => [ 2, 0],
    w  => [-2, 0],

    ne => [ 1, 1],
    nw => [-1, 1],

    se => [ 1,-1],
    sw => [-1,-1],
  );

  sub new{
    my($class,$parent,$x,$y) = @_;
    weaken $parent;
    my $self = bless {
      parent => $parent,
      pos    => [$x,$y]
    }, $class;

    $self->_init_possible;

    return $self;
  }

  sub _init_possible{
    my($self) = @_;
    my $parent = $self->parent;
    my $width  = $parent->width;
    my $height = $parent->height;
    my($x,$y)  = $self->pos;

    my @return;
    for my $dir ( keys %dir ){
      my($xd,$yd) = @{$dir{$dir}};
      my $x = $x + $xd;
      my $y = $y + $yd;

      next if $y < 0 or $height <= $y;
      next if $x < 0 or $width  <= $x;

      push @return, $dir;
      $self->{$dir} = [$x,$y];
    }
    return  @return if wantarray;
    return \@return;
  }

  sub list_possible{
    my($self) = @_;
    return unless defined wantarray;

    # only return keys which are
    my @return = grep {
      $dir{$_} and defined $self->{$_}
    } keys %$self;

    return  @return if wantarray;
    return \@return;
  }

  sub parent{
    my($self) = @_;
    return $self->{parent};
  }

  sub pos{
    my($self) = @_;
    my @pos = @{$self->{pos}};
    return @pos if wantarray;
    return \@pos;
  }

  sub visit{
    my($self,$v) = @_;
    my $return = $self->{visit} || 0;

    $v = 1 if @_ == 1;
    $self->{visit} = $v?1:0 if defined $v;

    return $return;
  }

  sub all_neighbors{
    my($self) = @_;
    return $self->neighbor( $self->list_possible );
  }
  sub neighbor{
    my($self,@n) = @_;
    return unless defined wantarray;
    return unless @n;

    @n = map { exists $dir{$_} ? $_ : undef } @n;

    my $parent = $self->parent;

    my @return = map {
      $parent->elem($self->{$_}) if defined $_
    } @n;

    if( @n == 1){
      my($return) = @return;
      #die unless defined $return;
      return $return;
    }
    return  @return if wantarray;
    return \@return;
  }

  BEGIN{
    for my $dir ( qw'n ne e se s sw w nw' ){
      no strict 'refs';
      *$dir = sub{
        my($self) = @_;
        my($return) = $self->neighbor($dir);
        die unless $return;
        return $return;
      }
    }
  }

  sub stringify{
    my($self) = @_;
    my($x,$y) = $self->pos;
    return "($x,$y)";
  }

  sub equal{
    my($l,$r) = @_;
    "$l" eq "$r";
  }

  sub reset{
    my($self) = @_;
    delete $self->{visit};
    return $self;
  }
}

# Main code block
{
  my $grid = Grid->new();

  my $start = $grid->elem(0,0);
  my $dest  = $grid->elem(-1,-1);

  my @all = solve($start,$dest);
  #say @$_ for @all;
  say STDERR scalar @all;
}

sub solve{
  my($current,$dest,$return,@stack) = @_;
  $return = [] unless $return;
  my %visit;
  $visit{$_} = 1 for @stack;

  die if $visit{$current};

  push @stack, $current->stringify;

  if( $dest == $current ){
    say @stack;

    push @$return, [@stack];
  }

  my @possible = $current->all_neighbors;
  @possible = grep{
    ! $visit{$_}
  } @possible;

  for my $next ( @possible ){
    solve($next,$dest,$return,@stack);
  }

  return @$return if wantarray;
  return  $return;
}

该计划在终止之前提出了超过 100,000 种可能的解决方案。我发送STDOUT到一个文件，它超过 200 MB。

于 2009-04-21T03:55:54.307 回答
0

您可以使用扫描线动态规划算法精确计算解决方案的数量。

于 2009-09-13T11:46:45.223 回答