AOJの8パズルが解けない

Question

アルゴリズムの勉強をしています。
Aizu Online Judgeの8パズルでどうしてもTLEになってしまいます。

using System;
using System.Linq;
using System.Collections.Generic;

public class Program{
    public static void Main(){
        var Board = new int[3, 3];
        for(int i=0; i<3; i++){
            var line = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for(int j=0; j<3; j++){
                Board[i, j] = line[j];
            }
        }
        var Goal = new int[,]{ {1, 2, 3}, {4, 5, 6}, {7, 8, 0} };
        var StrGoal = ToStringForList(Goal);
        var queue = new Queue<State>();
        var all_list = new List<string>();
        queue.Enqueue(new State{table = Board, cnt = 0});
        while(queue.Count()>0){
            var curr = queue.Dequeue();
            if(all_list.Contains(ToStringForList(curr.table)))continue;
            else all_list.Add(ToStringForList(curr.table));
            if(ToStringForList(curr.table)==StrGoal){
                Console.WriteLine(curr.cnt);
                break;
            }
            
            var Now = curr.GetPos();
            var cx = Now.X;
            var cy = Now.Y;
            var steps = new int[]{0, 1, 0, -1, 0};
            for(int i=0; i<4; i++){
                var nx = cx+steps[i+1]; 
                var ny = cy+steps[i];
                if(0<=nx && nx<Board.GetLength(1) && 0<=ny && ny<Board.GetLength(0)){
                    var Nex = new Pos{Y = ny, X = nx};
                    var NexMap = curr.Swap(Nex, Now);
                    queue.Enqueue(NexMap);
                }
            }
        }

    }
    
    public static string ToStringForList(int[,] map){
        var ret="";
        for(int i=0; i<map.GetLength(0); i++){
            for(int j=0; j<map.GetLength(1); j++){
                ret+=map[i, j];
            }
        }
        return ret;
    }
}

public struct Pos{
    public int X{set; get;}
    public int Y{set; get;}
}

public struct State{
    public int cnt{set; get;}
    public int[,] table{set; get;}
    public Pos GetPos(){
        var retPos = new Pos{X = -1, Y = -1};
        for(int i=0; i<this.table.GetLength(0); i++){
            for(int j=0; j<this.table.GetLength(1); j++){
                if(this.table[i, j]==0){
                    retPos.X = j;
                    retPos.Y = i;
                }
            }
        }
        return retPos;
    }
    
    public State Swap(Pos pre, Pos nex){
        var _tmp = this.table.Clone() as int[,];
        var _cnt = this.cnt;
        _tmp[nex.Y, nex.X] = this.table[pre.Y, pre.X];
        _tmp[pre.Y, pre.X] = this.table[nex.Y, nex.X];
        return new State{cnt = _cnt+=1, table = _tmp};
    }
}

最短手数を求めよとのことで幅優先探索を使っています。
このコードだとcase15でTLEになります。

ほかの方の提出して得るコードをみるとなにか謎手法を用いているように思われ、解読できませんでした。ただ中には同じようにBFSを使っているものもあり、書き方のせいなのかなとも思います。

ご指摘よろしくおねがいします。

Answer 1

大きな考え方自体は間違っていないと思います。問題は個々の処理が遅すぎるという感じです。

Visual Studioを使っているのであれば、遅い部分を分析してみてください。分析→パフォーマンスプロファイラーで分析できます。

手元で確認すると、遅い処理は主に次の三つのようです。

1. 26行目のall_list.Contains(ToStringForList(curr.table))
2. 28行目のToStringForList(curr.table) == StrGoal
3. ToStringForListメソッド本体(特に60行目のret += map[i, j];)

まず、1.についてですが、Listに対するContainsの計算量は平均O(n)ととても遅いです。これは、一つ一つを要素を辿っていくため、要素の数の分だけ処理が必要だからです。こういう場合、内部でハッシュを使用することでContainsがO(1)になるHashSetを使用してください。それだけで速度が段違いになります。

次に2.についてですが、文字列の比較自体がそれほど速くないようです。

次に3.についてです。パズルを文字列にして処理していますが、文字列に変換するという処理(ToStringForList)が遅いです。それなのに、ToStringForList(curr.table)という処理を26,27,28行で3回もしています。結果は全て同じになるはずです。これを1回にするだけでも速度は変わります。

また、ToStringForListにも見直すべき所があります。それは、60行目のret += map[i, j];です。元の文字列に文字または文字列を追加して置き換える処理は遅いです。なぜなら、文字列オブジェクト自体を毎回生成するからです。このような処理を行う場合は、StringBuilderを使うといいです。StringBuilderであれば、オブジェクト自体を変更していくため、生成コストがかかりません。

さて、これで大分速くはなると思いますが、それでも足りない場合があると思います。その場合は、配列を文字列にするという処理自体を見直す必要があると思います。C#の文字列はさほど単純では無いため、配列などと比較するとどうしても遅くなります。配列は配列のまま処理できないか、ToStringForListがなくても個々に処理できないかを検討してください。

Comments

[退会済みユーザー]

回答いただいてから時間が経ってしまいまいした。ずっと悩んでいたのですが、さきほどAcceptedを得ることが適いました。以下ご指摘を受けての報告です。

（当方の環境はVSC for Macで書いており、事情によりVSやXcodeは使えないのですが、ご丁寧にVS上でのtipsも添えていただきありがとうございました。使うときの参考にしたいと思います！）

ご指摘いただいた点を参考に、```var all_list = new HashSet<long>();```とし、盤面を
```
public static long Board2Long(int[,] board){
var keta = board.GetLength(0)*board.GetLength(1)-1;
long ret = 0;
for(int i=0; i<board.GetLength(0); i++){
for(int j=0; j<board.GetLength(1); j++){
ret+=board[i,j]*(int)Math.Pow(10, keta-(i*board.GetLength(0)+j));
}
}
return ret;
}
```
と```ToStringForList```メソッドの代わりに文字列ではなく9桁の整数で管理することにしました。

これで、問題となっていたcase15は通りました！今まで文字列をキー代わりにする手段を使って困ったことが無かったので（あと```StringBuilder```を使わずにstring型で```+```でつなげても速度的に問題になるようなシーンがなかったので）、知ってはいたものの気にしたことがありませんでした。いくつもの教科書で文字列への変換は遅い！と口うるさく言われてたのはこういうことだったのか。。。

しかし、これでも次のcase16は通りません。そこで、幅優先探索自体の高速化を図ることにしました。

調べると、**双方向探索** というのが常套手段らしいのでこいつを実装してみます。スタートと同時にゴールからも探索を行うことで、互いの経路が最初に出会ったものが全体の最短経路、というのらしい。

どちらの方向からの探索か、の構造と処理を新しく作るのが面倒だったので、いっそ各経路のコスト```State.cnt```の正負で表してしまえ、としたのが以下です。
```
using System;
using System.Linq;
using System.IO;
using System.Collections.Generic;

public class Program{
public static int N = 3;
public static int[] STEPS = new int[]{0, 1, 0, -1, 0};
public static void Main(){

var Board = new int[N, N];
for(int i=0; i<N; i++){
var line = Console.ReadLine().Split().Select(int.Parse).ToArray();
for(int j=0; j<N; j++){
Board[i, j] = line[j];
}
}

var Goal = new int[,]{ {1, 2, 3}, {4, 5, 6}, {7, 8, 0} };
var queue = new Queue<State>();
var all_list = new HashSet<long>();
var all_dict = new Dictionary<long, int>();

//スタートからゴールへ向かう経路は正値、逆は負値とする
//処理の関係上どちらも1ステップ終えた状態から始めるとし、探索終了の際に-2をして帳尻を合わせる
queue.Enqueue(new State{table = Goal, cnt = -1});
queue.Enqueue(new State{table = Board, cnt = 1});
all_dict[Board2Long(Goal)] = -1;
all_dict[Board2Long(Board)] = 1;

while(queue.Count()>0){
var curr = queue.Dequeue();
var longed = Board2Long(curr.table);
if(all_list.Contains(longed)){
//既に通ったパスが存在する場合、向きが異なっていれば互いに鉢合ったことになるので終了
//つまり一方が正で他方が負である場合のみ（ほかにスマートな実装方法はないものか）
if( (all_dict[longed]<0 && 0<curr.cnt) || curr.cnt<0 && 0<(all_dict[longed]) ){
var other = Math.Abs(all_dict[longed]);
var me = Math.Abs(curr.cnt);
Console.WriteLine(other+me-2);
break;
}else{
continue;
}
}

all_list.Add(longed);
all_dict[longed] = curr.cnt;

var Now = curr.GetPos();
var cx = Now.X;
var cy = Now.Y;
for(int i=0; i<4; i++){
var nx = cx+STEPS[i+1];
var ny = cy+STEPS[i];
if(0<=nx && nx<Board.GetLength(1) && 0<=ny && ny<Board.GetLength(0)){
var Nex = new Pos{Y = ny, X = nx};
var NexMap = curr.Swap(Nex, Now);
queue.Enqueue(NexMap);
}
}
}
}

public static long Board2Long(int[,] board){
var keta = board.GetLength(0)*board.GetLength(1)-1;
long ret = 0;
for(int i=0; i<board.GetLength(0); i++){
for(int j=0; j<board.GetLength(1); j++){
ret+=board[i,j]*(int)Math.Pow(10, keta-(i*board.GetLength(0)+j));
}
}
return ret;
}
}

public struct Pos{
public int X{set; get;}
public int Y{set; get;}
}

public struct State{
public int cnt{set; get;}
public int[,] table{set; get;}
public Pos GetPos(){
var retPos = new Pos{X = -1, Y = -1};
for(int i=0; i<this.table.GetLength(0); i++){
for(int j=0; j<this.table.GetLength(1); j++){
if(this.table[i, j]==0){
retPos.X = j;
retPos.Y = i;
}
}
}
return retPos;
}

public State Swap(Pos pre, Pos nex){
var _tmp = this.table.Clone() as int[,];
var _cnt = this.cnt;
var ad = _cnt>0 ? 1 : -1;
_tmp[nex.Y, nex.X] = this.table[pre.Y, pre.X];
_tmp[pre.Y, pre.X] = this.table[nex.Y, nex.X];
return new State{cnt = _cnt+=ad, table = _tmp};
}
}
```
見事すべてのケースを通ることができました！軽く100倍は早くなりました。アルゴリズムの凄さを思い知ることができました。。。これもヒントを与えてもらったおかげです。ありがとうございました。