Я справился!! Ураа!!    
Главное - нужно отсекать повторы и использовать алгоритм А*
Могу привести ооочень грязный код решения задачи. Это черновой вариант программы. Пользуйтесь на здоровье. Всем спасибо за советы.
| Код |
#include <vcl.h>
#pragma hdrstop
#include "BFSUnit.h"
#include "math.h"
#include <vector>
#include <list>
using namespace std;
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//vector <_vertex> L (100*1024*1024 / ss);
// 100*1024*1024 - выделить 100 мб данных. 100- это 100мб,
// 1024*1024 - перевод мегабаты в байты
// /ss - sizeof(тип данных)
typedef int gameState[3][3]; //состояние игрового поля
struct _vertex // вершина графа
{
gameState state; // соответствующее состояние
unsigned int prevVertex; // номер предыдущей вершины на пути к текущей
int cost; // "цена" вершины
int heuristics; // эвристика
bool marked; // индикатор "просмотрена / не просмотрена"
}vertex;
//gameState startingState = {{4,1,3},{2,0,6},{7,5,8}};
gameState startingState = {{4,1,8},{7,3,5},{0,2,6}};
//gameState startingState = {{6,5,1}, {8,0,2}, {3,7,4}};
gameState neighbours[4];
vector <_vertex> L(30000000);
//vector <_vertex> L (1000*1024*1024 / sizeof(_vertex)); // выделить 1 ГБ данных
unsigned __int64 tailIdx;
bool stop = false;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
int GetNeighbours(gameState &s)
{
int i, j, k;
int zi, zj;
int idx;
const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, -1, 0, 1};
for (i=0; i<3; i++)
for (j=0; j<3; j++)
if (s[i][j] == 0)
{
zi = i; zj = j;
}
idx = 0;
for (k=0; k<4; k++)
{
i = zi + di[k];
j = zj + dj[k];
// если соседняя клетка находится в пределах поля
if ((i >= 0) && (j >= 0) && (i <= 2) && (j <= 2))
{ // записываем очередной элемент
memcpy(neighbours[idx], s, sizeof(s));
neighbours[idx][i][j] = 0; // пустая клетка меняется
neighbours[idx][zi][zj] = s[i][j]; //местами с соседней
idx++;
}
}
return idx;
}
bool IsGoal(gameState &s)
{
int i, j;
const gameState goal = {{1,2,3}, {4,5,6}, {7,8,0}};
for (i=0; i<3; i++)
for (j=0; j<3; j++)
{
if (s[i][j] != goal[i][j])
return false;
}
return true;
}
bool is2MatrixSame(gameState& state, gameState &neighbour)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (state[i][j] != neighbour[i][j])
return false; // Разные
return true; // Одинаковые
}
bool isSame(vector <_vertex> &L, gameState &neighbour)
{
int k;
gameState state;
for (k=0; k<tailIdx; k++)
{
memcpy(state, L[k].state, sizeof(L[k].state));
if ( ! is2MatrixSame(state, neighbour))
continue;
else
return true;
}
return false;
}
String StateToString(gameState &s)
{
int i, j;
String r;
r = "";
for (i=0; i<3; i++)
{
for (j=0; j<3; j++)
r += IntToStr(s[i][j]) + " ";
r += "\r\n";
}
return r;
}
void PrintState(gameState &s, int c)
{
String st;
//Form1->Memo->Text = " ";
Form1->Memo->Text += StateToString(s) + "\r\n";
// Memo->Text += "Исследовано состояний: " + IntToStr(c); -
// не работает 0_о
/*
st = Form1->Memo->Text;
st += "Исследовано состояний: " + IntToStr(c);
Form1->Memo->Text = st;
Form1->Label1->Caption = IntToStr(c); // показываем кол-во проверенных вершин
*/
}
//---------------------------------------------------------------------------
int CalculateHeuristics(gameState &s)
{
int i, j, r;
// тут был хитрый баг! В делфи коде были массивы rowOf, colOf 1..8
// и s 0..2. В делфи значение rowOf\colOf[s[i][j]], извлекалось с учотом, что
// rowOf и colOf начинаются от 1, там код работал. А в Си, rowOf colOf начинаются
// от 0, код не работал. Поэтому, я добавил еще один элемент к rowOf и colOf (8+1=9).
// В каджыйй массив занес 5ку, которая при работе программы игнорируется. Код заработал!
const int rowOf[9] = {5, 0, 0, 0, 1, 1, 1, 2, 2};
const int colOf[9] = {5, 0, 1, 2, 0, 1, 2, 0, 1};
r = 0;
for (i=0; i<3; i++)
for (j=0; j<3; j++)
if (s[i][j] != 0)
r += abs(rowOf[s[i][j]] - i) + abs(colOf[s[i][j]] - j);
return r;
}
// определить следующую вершину, извлекаемую из списка L
int GetIndexOfNextElement()
{
int min, idx, i;
min = 10000000;
for (i=0; i<tailIdx; i++)
if ((L[i].marked == false) && (L[i].cost + L[i].heuristics < min))
{
idx = i;
min = L[i].cost + L[i].heuristics;
}
return idx;
}
void __fastcall TForm1::ASearchButtonClick(TObject *Sender)
{
int headIdx; // указатель на начало списка L
int n; // количество соседних состояний
int i; // счетчик цикла
_vertex v; // текущая исследуемая вершина
int c; // количество уже исследованных вершин
int idx;
String st;
Memo->Clear();
memcpy(L[0].state, startingState, sizeof(startingState)); // вносим в список L стартовую вершину
L[0].prevVertex = -1; // предыдущей вершины у стартовой нет
L[0].cost = 0; // цена стартовой позиции равна нулю
// вычисляем эвристику
L[0].heuristics = CalculateHeuristics(startingState);
L[0].marked = false;
tailIdx = 1;
c = 0;
Form1->Memo->Text = "ijko\r\n";
do
{
idx = GetIndexOfNextElement();
v = L[idx]; //{ извлекаем элемент из списка }
c++;
L[idx].marked = true; //{ помечаем его как рассмотренный }
if (IsGoal(v.state)) // если он - целевой
{
Form1->Memo->Text = StateToString(v.state) + "\r\n";
do
{
v = L[v.prevVertex];
Form1->Memo->Text = StateToString(v.state) + "\r\n" + Form1->Memo->Text;
}while (v.prevVertex != -1);
// Memo->Text += "Исследовано состояний: " + IntToStr(c); -
// не работает 0_о
st = Form1->Memo->Text;
st += "Исследовано состояний: " + IntToStr(c);
Form1->Memo->Text = st;
Form1->Label1->Caption = IntToStr(c); // показываем кол-во проверенных вершин
Label1->Caption = IntToStr((__int64)tailIdx++);
return;
}
//Label1->Caption = IntToStr(c); // показываем кол-во проверенных вершин
//PrintState(v.state, c);
//Form1->Memo->Text = StateToString(v.state) + "\r\n" + Form1->Memo->Text;
//Label1->Caption = IntToStr((__int64)tailIdx);
n = GetNeighbours(v.state); // определяем соседние вершины
for (i=0; i<n; i++) // и вносим их в список L
{
if (! isSame(L, neighbours[i]) )
{
memcpy(L[tailIdx].state, neighbours[i], sizeof(neighbours[i]));
// цена = цена предыдущей вершины + вес ребра (1)
L[tailIdx].cost = v.cost + 1;
L[tailIdx].heuristics = CalculateHeuristics(neighbours[i]);
L[tailIdx].prevVertex = idx;
tailIdx++;
}
}
if (stop) return;
Application->ProcessMessages();
}while (tailIdx != 0); // По сути - это бесконечный цикл
Memo->Text = "Решение не найдено " + IntToStr(c);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::StopButtonClick(TObject *Sender)
{
stop = !stop;
}
|
|
Это была попытка перечислить все позиции и построить граф смежностей? 
Жаль что не на Си 