8-Puzzle Solver неожиданное поведение

Я работаю над 8-Puzzle Solver поиск в первую очередь + расстояние Хэмминга(плитки неуместны) эвристика, которая требовалась от нас как проекта.

Я сначала определил Stat Структура в отдельном файле cpp, который выглядит следующим образом в заголовочном файле:

#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 нет таких показателей и эвристические значения этих состояний различаются при Open (4,4,5,5,5,5) остальные (6,6,5,7).

Может кто-нибудь, пожалуйста, скажите мне, почему Open отказывается вводить эти статистические данные, как будто они уже существуют.
Заранее спасибо.

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector