VPF::Восьмиряшки - Форум программистов

kiLLProg

Дата 28.8.2012, 13:27 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 1.10.2008

Репутация: нет
Всего: нет

Здравствуйте. Я по одной книге реализовал уменьшенную версию игры в пятнашки, где за место 15и чисел 8. Самым простым поиском в ширину решается начальная комбинация
4, 1, 3
2, 0, 6
7, 5, 8
после 632 просмотров комбинаций, программа выдаёт выигрышное состояние
1, 2, 3
4, 5, 6
7, 8, 0

Но стоит мне ввести более сложную начальную комбинацию, программа не справляется. Манхэттенское расстояние реализовывал, но потом убрал. О возможных нерешаемых комбинациях я знаю, поэтому, записывал начальные значения с ява игры на телефоне =)
Всего комбинаций чисел в игре восемь = 9! = 362 880. Для сохранения всех комбинаций, я заводил динамический массив на 100 млн. элементов, но мне это не помогло. Происходит выход за пределы массива. Даже массив зацикливал (после наполнения 5000 элемента начинал заполнять массив заново). У меня задача не решается в лоб, поиском в глубину. Похоже, где-то происходит зацикливание по графам всех возможных комбинаций.

Вот исходник программы:

Код


typedef int gameState[3][3];  //состояние игрового поля

struct _vertex   // вершина графа
{
  gameState state;  // соответствующее состояние
  unsigned int prevVertex;   // номер предыдущей вершины на пути к текущей
}vertex;

  gameState startingState = {{4,1,3},{2,0,6},{7,5,8}};
  gameState neighbours[4];
  vector <_vertex> L(10000000);
  unsigned __int64 tailIdx;
  bool stop = false;

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;
}

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 __fastcall TForm1::BFSearchButtonClick(TObject *Sender)
{
  unsigned __int64 headIdx;  // указатель на начало списка L
            int n;        // количество соседних состояний
  unsigned __int64 i;        // счетчик цикла
              _vertex v;    // текущая исследуемая вершина
  unsigned __int64 c;         // количество уже исследованных вершин
  String st;


  Memo->Clear();
  L.clear();

  memcpy(L[0].state, startingState, sizeof(startingState)); //  вносим в список L стартовую вершину
  L[0].prevVertex = -1;         //   предыдущей вершины у стартовой нет
  headIdx = 0;
  tailIdx = 1;
  c = 0;

 do
 {
   v = L[headIdx];             // v := первый элемент списка
   c++;
   if (IsGoal(v.state)) // если текущая вершина является целевой
   {
     // выводим ее в текстовое поле
     Memo->Text = StateToString(v.state) + "\r\n";
    
     do
     {
       v = L[v.prevVertex];
       Memo->Text = StateToString(v.state) + "\r\n" + Memo->Text;
     }while (v.prevVertex != -1);
     
      Memo->Text += "Исследовано состояний: " + IntToStr((__int64)c);
     st = Memo->Text;
     st += "Исследовано состояний: " + IntToStr((__int64)(c));
     Memo->Text = st;
     return;
   }

   n =  GetNeighbours(v.state);
   for (i=0; i<n; i++)
   {
     memcpy(L[tailIdx].state, neighbours[i], sizeof(neighbours[i]));
     L[tailIdx].prevVertex = headIdx;
     tailIdx++;
   }
   headIdx++;
   Application->ProcessMessages();
   if (stop) return;
 }while (headIdx != tailIdx);

 Memo->Text = "Решение не найдено " + ((__int64)(c));
}

Помогите решить эту оочень интересную задачу. smile

Это сообщение отредактировал(а) kiLLProg - 28.8.2012, 13:31

Pavia

Дата 28.8.2012, 20:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12

Цитата

Всего комбинаций чисел в игре восемь = 9! = 362 880.

Не все комбинации возможны получить перестановкой.

Akina

Дата 28.8.2012, 21:23 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(Pavia @ 28.8.2012, 21:39

)

Не все комбинации возможны получить перестановкой.

Все возможные комбинации распадаются на две группы такие, что из любой позиции группы можно получить любую другую позицию той же группы.

Цитата(kiLLProg @ 28.8.2012, 14:27

)

Для сохранения всех комбинаций, я заводил динамический массив на 100 млн. элементов

Это была попытка перечислить все позиции и построить граф смежностей?

Цитата(kiLLProg @ 28.8.2012, 14:27

)

Помогите решить эту оочень интересную задачу.

Так а какая задача-то? построить решение? оптимизировать поиск в ширину? убрать ляпы в коде? что-то ещё?

Если построить решение - я бы просто пошёл по пути разработки критерия упорядоченности позиции. Полный перебор на 4-5 шагов (т.е. просмотр максимум 2к позиций), после чего движение в позицию максимального критерия, и следующий поиск.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

Lipetsk

Дата 29.8.2012, 07:49 (ссылка)

(нет голосов)

Загрузка ...

в форме ;)

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5

Цитата(Pavia @ 28.8.2012, 18:39

)

Не все комбинации возможны получить перестановкой.

ровно половину от 9! можно

Lipetsk

Дата 29.8.2012, 10:43 (ссылка)

(нет голосов)

Загрузка ...

в форме ;)

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5

вот мое решение на lua

Код


local startPlace='413296758'
local endPlace=''

local field,field2,c={},{},0
for i=1,3 do
    local n={}
    field[i]=n
    for j=1,3 do
        c=c+1
        endPlace=endPlace..c
        n[j]=c
        field2[c]={i,j}
    end
end

local places,pCount={},0

local holePlace=function(p)
    return p:find'9'
end

local insV=function(place,pos,v)
    return place:sub(1,pos-1)..v..place:sub(pos+1)
end

local moves={{-1,0,},{1,0,},{0,-1,},{0,1,},}

local newPlaces

local fillNewPlaces=function(p)
    print(p)
    local hp=holePlace(p)
    local hp2=field2[hp]
    local x,y=hp2[1],hp2[2]
    for _,move in ipairs(moves)do
        local dx,dy=move[1],move[2]
        local nx=x+dx
        local ny=y+dy
        if nx>0 and nx<=3 and ny>0 and ny<=3 then
            local vp=field[ny][nx]
            local v=p:sub(vp,vp)
            local np=insV(insV(p,hp,v),vp,'9')
            if not places[np] then
                pCount=pCount+1
                places[np]=true
                table.insert(newPlaces,np)
            end
            if np==endPlace then
                return np
            end
        end
    end
end

places[startPlace]=true
newPlaces={startPlace}
local level,finish=0
repeat
    level=level+1
    print('level',level)
    local curPlaces=newPlaces
    newPlaces={}
    for _,place in ipairs(curPlaces) do
        if fillNewPlaces(place) then
            finish=true
            break
        end
    end
until finish

print('\nSolved by '..level..' steps')
print('processed '..pCount..' variants')

смысл его в горизонтальном обходе дерева комбинаций

код приведенный kiLLProg пример решает за 74 просмотра и 6 ходов

kiLLProg

Дата 29.8.2012, 11:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 1.10.2008

Репутация: нет
Всего: нет

Цитата(Akina @ 28.8.2012, 21:23

)

Это была попытка перечислить все позиции и построить граф смежностей?

Да.

Цитата(Akina @ 28.8.2012, 21:23

)

Так а какая задача-то? построить решение?

Да.

Цитата(Akina @ 28.8.2012, 21:23

)

Если построить решение - я бы просто пошёл по пути разработки критерия упорядоченности позиции. Полный перебор на 4-5 шагов (т.е. просмотр максимум 2к позиций), после чего движение в позицию максимального критерия, и следующий поиск.

А вот разве нельзя обойтись без таких ухищрений? Ведь памяти у современных компов предостаточно, можно просто поиском в глубину обойтись. Вот только чувствую, что программа по графам где-то зацикливается и не находит решения.

Спасибо за код, Lipetsk! smile

Жаль что не на Си smile

Цитата(Lipetsk @ 29.8.2012, 10:43

)

смысл его в горизонтальном обходе дерева комбинаций

Спасибо за идею!!! smile

Подскажи пожалуйста, как получить все комбинации без повторов? В коде это не могу найти, язык мне не знаком.

Подскажите пожалуйста какую-нибудь литературу про эту задачу, желательно с исходниками.

Akina

Дата 29.8.2012, 13:23 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(kiLLProg @ 29.8.2012, 12:51

)

разве нельзя обойтись без таких ухищрений?

Запросто. На SQL такая, как ты описываешь, таблица одним запросом создаётся, двумя - наполняется, и одним - получается решение. Сколько оно, правда, будет молотить - я хз... будет время - попробую.

--------------------

kiLLProg

Дата 29.8.2012, 14:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 1.10.2008

Репутация: нет
Всего: нет

Я справился!! Ураа!! smile

Главное - нужно отсекать повторы и использовать алгоритм А* smile

Могу привести ооочень грязный код решения задачи. Это черновой вариант программы. Пользуйтесь на здоровье. Всем спасибо за советы.

Код


#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;
}

Это сообщение отредактировал(а) kiLLProg - 29.8.2012, 14:40

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »