0

我正在研究一个 8-Puzzle Solver - 使用最佳优先搜索 + Hamming 距离（瓷砖不合适）启发式 - 这是我们作为项目所必需的。

我首先在一个单独的 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
1 6 4
7 0 5

1 2 3
8 0 4
7 6 5

它解决了难题，一切都很好。但是在我尝试的所有其他输入中，开放集在达到目标之前就变空了，尽管这些难题有解决方案。

编辑： 我试图查看进入开放集的统计数据，但没有，所以我使用下面的输入作为示例，我得到了什么：

打开的统计数据：

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

解决这个难题需要哪些步骤。

未在 Closed 中找到且未进入 Open 的统计信息：

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 中没有此类统计信息，并且这些状态的启发式值不同 On Open(4,4,5,5,5,5)其他（6,6,5,7）。

有人可以告诉我为什么 Open 拒绝输入这些统计数据，就好像它们已经存在一样。提前致谢。

4

0 回答 0