21

ここ数日、私は修士課程の勉強を控えて、この (一見単純な) パズルに集中してきました。

この 10*10 のグリッドは、100 の利用可能な場所の正方形を構成します。目的は、コーナーから開始し、いくつかの単純な「トラバース ルール」に従ってすべての場所をトラバースし、100 番に到達することです (または、プログラマーの場合は 99 番で、代わりに 0 から始めます :)

トラバースのルールは次のとおり
です。 1. 縦軸と横軸に沿って
2 つのスペースをホップします。 2. 対角線に沿って 1 つのスペースをホップし
ます。 3. 各マスは 1 回だけ訪れることができます。

よりよく視覚化するために、有効なトラバースの例 (8 番目のステップまで) を次に示し
ます。

手動で、私は退屈からこのパズルに取り組んできました。何年もの間、私は時々手で解こうと試みてきましたが、96 を超えることはありませんでした。簡単に聞こえますか? 自分で試してみてください:)

したがって、この問題を解決するために、Python で短い (約 100 行のコード) プログラムを開発しました。私はこの言語の初心者です。何ができるか見てみたいと思っていました。
プログラムは、徹底的な試行錯誤解決法を適用するだけです。言い換えれば、力ずくの深さ優先検索です。

ここから私の質問が発生します。残念ながら、プログラムは問題を解決できません。これは、状態空間が非常に大きいため、解決策が見つからない限り検索が終了しないためです。問題なく 98 まで (そしてそれを出力) することができますが、それでも完全な解決策ではありません。
プログラムは、これまでにカバーした検索ツリーの長さも出力します。数分で、たとえば 65 番目の要素からのトラバース リストが、1 つのパスについて最後までカバーされます。この数は、指数関数的に増加する期間で減少します。私はかなり長い間コードを実行してきましたが、50 バリアを超えることはできませんでしたが、今では確信しています。

この単純なアプローチは、私が永久に実行しない限り十分ではないようです。では、コードをより高速かつ効率的に改善して、解決策を導き出すにはどうすればよいでしょうか?

基本的に、次の方法に関するアイデアを楽しみにしています。

  1. この問題に固有のドメイン知識を取得して活用する

  2. 疲労を克服するためにプログラミングのテクニック/トリックを適用する

    ..そして、最終的に実質的な解決策を実現します。

前もって感謝します。

リビジョン
所属するドメインに問題を関連付けてくれた Dave Webb に感謝します。

これは、同じマスを再訪せずにチェス盤の周りでナイトを動かすことに関するナイツ ツアー問題に非常に似ています。基本的には同じ問題ですが、「トラバース ルール」が異なります。

4

7 に答える 7

15

これは、同じマスを再訪せずにチェス盤の周りでナイトを動かすことに関するナイツ ツアー問題に非常に似ています。基本的には同じ問題ですが、「トラバース ルール」が異なります。

Knights Tour に再帰的に取り組むことから覚えている重要な最適化は、次の移動先のマスで利用可能な移動数の昇順で移動することです。これにより、ボード全体をズームして決して訪れることのできない小さな島の正方形を残すのではなく、1 つの領域で密集して移動してそれを埋めようとする検索が促進されます。(これはWarnsdorff のアルゴリズムです。)

また、できる限り対称性を考慮してください。たとえば、最も単純なレベルでは、(10,10) はボードを回転させた (1,1) と同じであるため、最初の正方形の x と y は 5 までしか必要ありません。

于 2009-04-20T12:06:28.333 に答える
10

私は問題を見て、解決策の最後が別の解決策の隅から 1 つ離れたところにある 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 x 5 の最初のコーナー (10 x 10 で) 5 までの斜めジャンプを配置します。

2 番目の正方形: [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] は、25 の最後の 2 乗を 10x10 に入れます。これは、55 から 2 ジャンプ離れています。

3 番目の正方形: [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] は、94 から 2 ジャンプ離れた 10x10 の 97 の最後の 2 乗でそれを配置します。

終点は重要ではないため、4 番目の正方形は任意の有効なソリューションになる可能性があります。ただし、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 でした。これは、さらなる計算と再マッピングのためにソリューションを保存するのが非常に簡単であることを意味します。

私がこれを間違っていない限り、これにより 1 つの可能な解決策が得られます (上記の 5x5 の解決策はそれぞれ 1 から 4 として定義されています)。

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万のソリューションが見つかりました。
ソリューションの完全なセットには、完全な全数検索が必要です。つまり、すべての組み合わせで終了するまでプログラムを実行する必要があります。ただし、「a」の正当なソリューションに到達することは、「線形時間」に短縮できます。

まず、私が学んだこと：

  1. DaveWebbの回答とammoQの回答に感謝します。問題は、NP困難であるため、実際にハミルトン閉路問題の拡張です。そもそも「簡単な」解決策はありません。ナイトツアーの有名ななぞなぞがあります。これは、ボード/グリッドのサイズとトラバースルールが異なるだけで同じ問題です。問題を詳しく説明するために言われ、行われたことはたくさんあり、方法論とアルゴリズムが考案されました。

  2. ジョーの答えに感謝します。問題はボトムアップの意味でアプローチすることができ、解決可能なサブ問題にスライスすることができます。解決されたサブ問題は、入口と出口の概念で接続できるため（一方の出口点は他方の入口点に接続できます）、主要な問題は小規模な問題の構成として解決できます。このアプローチは健全で実用的ですが、完全ではありません。答えが存在する場合、それを見つけることを保証することはできません。

徹底的なブルートフォース検索で、ここに私がコードで開発した重要なポイントがあります：

  • Warnsdorffのアルゴリズム：このアルゴリズムは、便利な数のソリューションにすばやく到達するための重要なポイントです。それは単に、「最もアクセスしにくい」場所への次の移動を選択し、「移動」リストに昇順またはアクセス可能性を入力する必要があることを示しています。最もアクセスしにくい場所とは、次の移動の可能性が最も少ない場所を意味します。

    以下は（ウィキペディアからの）擬似コードです：

いくつかの定義：

  • 位置Qは、Pが1人の騎士の動きでQに移動でき、Qがまだ訪問されていない場合、位置Pからアクセスできます。
  • 位置Pのアクセス可能性は、Pからアクセス可能な位置の数です。

アルゴリズム：

Pをボード上のランダムな初期位置に設定します。2からボード上の正方形の数までの各移動番号の移動番号「1」でボードをPでマークします。Sを入力位置からアクセス可能な位置のセットとします。 Pを最小のアクセシビリティでSの位置に設定し、現在の移動番号でボードをPにマークし、マークされたボードを返します。各正方形には、訪問した移動番号がマークされます。

  • 島のチェック：ここでのドメイン知識の優れた活用が便利であることが証明されました。移動（最後の移動でない限り）によって隣接する島が島になる場合、つまり他の人がアクセスできない場合、そのブランチは調査されなくなります。Warnsdorffのアルゴリズムと組み合わせると、かなりの時間を節約できます（非常に約25％）。

そして、これが謎を解くPythonの私のコードです（問題がNP困難であることを考えると許容できる程度に）。私は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

考えられるすべての解決策を考え出すプログラムを作成できるかどうかを確認したかったのです。

#! /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しましたが、200MBを超えていました。

于 2009-04-21T03:55:54.307 に答える
0

スイープライン動的計画法アルゴリズムを使用して、解の数を正確に数えることができます。

于 2009-09-13T11:46:45.223 に答える