c++ - 8-Puzzle Solver の予期しない動作

Question

私はプロジェクトとして私たちから要求された 8 パズルソルバー -ベストファーストサーチ + ハミング距離(タイルの位置ずれ) ヒューリスティックを使用する - に取り組んでいます。

最初に、ヘッダーファイルで次のように分離された cpp ファイルでStat Struct を定義しました。

#ifndef STAT_H_INCLUDED
#define STAT_H_INCLUDED
#include <iostream>

struct Stat
{
    int Board[3][3];
    int depth;
    int Empty[2];
    int Evaluation;
    int operator- (Stat) const; //Overloading operator- to return "Hamming distance"
    void operator= (Stat);
    bool operator== (Stat) const;
    bool operator< (Stat) const;
};

//Used as a compare class for the set container

class Comparor  //Class to Compare between Stats(Default Bigger)
{
    bool Bigger;

public:
    Comparor(const bool& Smaller=1)
    {
        Bigger=Smaller?0:1;
    }
    bool operator() (const Stat& lhs, const Stat& rhs) const
    {
        if (Bigger) return (lhs<rhs?0:1);
        else return (lhs<rhs);
    }
};
std::istream& operator>> (std::istream&,Stat&); //To input the 9-cells as one 
std::ostream& operator<< (std::ostream&,Stat&); //To output the 9-cells as one
#endif // STAT_H_INCLUDED

次は main.cpp ファイルです:

#include <vector>
#include <set>
#include <algorithm>
#include <fstream>
#include "Stat.h"

using namespace std;

//Global Variables
Stat Start,Goal,temp;
int Steps=0;
set<Stat,Comparor> Open; //Used so that the Stats will be arranged -by heuristic value- and unique
vector<Stat> Closed;

//Forward Declaration
int Solver();
inline int Generate_Move(char);

int main()
{
    ifstream cin("input.txt");

    cin>>Start>>Goal;
    Start.depth=0;
    Start.Evaluation=Start-Goal;
    Open.insert(Start);
    Solver();
    cout<<temp<<endl;
    cout<<endl<<"Setps to reach the goal = "<<Steps<<endl;
    return 0;
}

int Solver()
{
  set<Stat,Comparor>::iterator it=Open.begin();
  temp=*it;
  if(temp==Goal)
    return Steps;
  cout<<temp<<endl;
  Closed.push_back(temp);
  Open.erase(it);

  Start=temp;
  if(temp.Empty[0]<2) //Up Direction
    Generate_Move('U');
  if(temp.Empty[0]>0) //Down Direction
    Generate_Move('D');
  if(temp.Empty[1]<2) //Right Direction
    Generate_Move('R');
  if(temp.Empty[1]>0) //Left Direction
    Generate_Move('L');

  Steps++;
  Solver();
}

inline int Generate_Move(char Direction)
{
  int Index,Inverse,Row,Coloum;
  int E0=temp.Empty[0],E1=temp.Empty[1];

  if(Direction == 'U'){Index=1;Inverse=0;}
  else if(Direction == 'D'){Index=-1;Inverse=0;}
  else if(Direction == 'R'){Index=0;Inverse=1;}
  else if(Direction == 'L'){Index=0;Inverse=-1;}

  Row=E0+Index;
  Coloum=E1+Inverse;

  swap(temp.Board[E0][E1],temp.Board[Row][Coloum]); //Swapping the empty cell with an adjacent cell
  if(find(Closed.begin(),Closed.end(),temp)!=Closed.end())
  {
      temp=Start;
      return 0;
  }
  //Changing the place of empty cell to the new place
  temp.Empty[0]=Row;
  temp.Empty[1]=Coloum;

  temp.depth++; //Increasing the depth of the stat

  //Setting the heuristic value of the stat
  temp.Evaluation=Goal-temp;
  temp.Evaluation+=temp.depth;

  Open.insert(temp);
  temp=Start;
  return 0;
}

次のようなサンプル入力を使用してプログラムを実行すると、次のようになります。

それはパズルを解決し、すべてが良いです.しかし、他のすべての入力を試してみると、それらのパズルの解決策があるという事実にもかかわらず、目標に到達する前にオープンセットが空になりました.

編集: オープンセットに入った統計を確認しようとしましたが、そうではなかったので、以下の入力をサンプルとして使用し、得たもの:

オープンに入力された統計:

2 8 3    2 8 3    2 0 3    0 2 3    1 2 3     1 2 3
1 6 4    1 0 4    1 8 4    1 8 4    0 8 4     8 0 4
7 0 5    7 6 5    7 6 5    7 6 5    7 6 5     7 6 5

パズルを解くために必要な手順はどれですか。

クローズドで見つからず、オープンにならなかった統計:

2 8 3    2 8 3     2 8 3    1 2 3
1 6 4    1 4 0     0 1 4    7 8 4
0 7 5    7 6 5     7 6 5    0 6 5

したがって、Open セットは、上記の統計が Open に存在し、それらの入力を拒否すると述べていますが、Open にはそのような統計はなく、それらの状態のヒューリスティック値は Open(4,4,5,5,5,5) で異なります。その他(6,6,5,7)。

オープンがそれらの統計を既に存在するかのように入力することを拒否する理由を誰か教えてください. 前もって感謝します。

c++ - 8-Puzzle Solver の予期しない動作

0 に答える 0

Related

Reference