Artificial Intelligence - هوش مصنوعی

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)
-   حل مسائل معروف هوش مصنوعي (http://artificial.ir/intelligence/forum102.html)
-   -   حل معماي 8 (8puzzle) به روش هاي مختلف (http://artificial.ir/intelligence/thread1195.html)

Astaraki ۱۰-۱۱-۱۳۸۸ ۰۲:۳۸ بعد از ظهر

حل معماي 8 (8puzzle) به روش هاي مختلف
 
5(ها)ضميمه
حل معماي 8 (پازل 8 ) به روش هاي مختلف

صورت مسئله:

اين مسئله جورچين اعداد است!
معمای 8 شامل یک صفحه 3×3 با 8 مربع شماره دار است. همه شما با این معما آشنا هستید. نکته مهم این است که به جای اینکه بگوییم «مربع شماره 4 را به داخل فضای خالی حرکت بده» بهتر است بگوییم «فضای خالی جایش را با مربع سمت چپش عوض کند.»

http://airobo.persiangig.com/image/Puzzle-is.gif
شکل 1-1

http://airobo.persiangig.com/image/Puzzle-m.gif
شکل 1-2

فرموله سازی
عملگر ها : فضای خالی به سمت بالا، پایین، چپ و يا راست حرکت می کند.
آزمون هدف : آیا با شکل 1-2 مطابقت دارد؟
هزینه مسیر : هر قدم ارزش 1 دارد. بنابراین هزینه مسیر همان طول مسیر است.

معمای 8 متعلق به خانواده Sliding-block Puzzles است. این کلاس عمومی به عنوان NP-complete شناخته می شود.

;;;;;;;;;;;;;;;

سورس بازي پازل به 4 زبان

C#.Net

vb.net

++C

و به زبان VB

Astaraki ۱۰-۱۱-۱۳۸۸ ۰۲:۵۳ بعد از ظهر

1(ها)ضميمه
در pdf هاي زير اين مسئله به روش A* حل شده

maskofgod ۱۰-۱۱-۱۳۸۸ ۰۵:۱۹ بعد از ظهر

برنامه من . . .
 
1(ها)ضميمه
معمای هشت | ::وبلاگی برای تمام فصول::

در اینجا سورس برنامه رو به زبان دلفی قرار دادم.
انشالله مثمر ثمر واقع بشه

Astaraki ۱۲-۲۵-۱۳۸۸ ۱۱:۵۴ قبل از ظهر

معماي 8 به سي پلاس پلاس
 
1(ها)ضميمه
8puzzle.cpp

كد:

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>


typedef char puzzle_t[3][3];

puzzle_t _puzzle_start = { {1, 2, 3},
                          {4, 5, 6},
                          {7, 8, 0}
                        };
puzzle_t _puzzle_stop =        {  {1, 2, 3},
                          {4, 0, 5},
                          {6, 7, 8}
                        };
struct        context_t {
        std::list<puzzle_t*> abort_states;
        std::list<std::string> solution;
        int max_depth;
};


std::ostream& operator<<(std::ostream &s, const puzzle_t &p)
{
        for (int y=0; y<3; ++y)        {
                for (int x=0; x<3; ++x)        {
                        s << (int)p[y][x] << " ";
                }
                s << std::endl;
        }
        return s;
}

bool solver_rec(puzzle_t& start, const puzzle_t& stop, int y0, int x0, int depth, context_t &ctx)
{
        // enough CPU cycles wasted
        if (depth >= ctx.max_depth) return false;

        // is the actual start a abort state?
        for (std::list<puzzle_t*>::iterator it = ctx.abort_states.begin(); it != ctx.abort_states.end(); ++it)        {
                bool abort = true;
                for (int y=0; y<3; ++y)        {
                        for (int x=0; x<3; ++x)        {
                                if (start[y][x] != (**it)[y][x]) abort=false;
                        }
                }
                // this state will be checked by on of the parents, anyhow
                if (abort)        {
                        return false;
                }
        }
       
        // are we done?
        bool done = true;
        for (int yy=0; yy<3; ++yy)        {
                for (int xx=0; xx<3; ++xx)        {
                        if (start[yy][xx] != stop[yy][xx]) done= false;
                }
        }
        if (done) return true;

        // add this state to the list of abort states
        // it safe to push_front an stack objectpointer
        // as we remove it again before stack is unwinded
        // or never ever touch it again
        puzzle_t p;
        memcpy(p, start, sizeof(p));
        ctx.abort_states.push_front(&p);

        for (int yy=0; yy<3; ++yy)        {
                for (int xx=0; xx<3; ++xx)        {
                        // if the move is possible, take it
                        if (((yy+1 == y0) || (yy-1 == y0)) && (xx == x0))        {
                                std::swap(start[yy][xx], start[y0][xx]);
                                if (solver_rec(start, stop, yy, x0, depth+1, ctx))        {
                                        std::stringstream s;
                                        s << depth << ". tile  " << yy << "/" << x0;
                                        ctx.solution.push_back(s.str());
                                        return true;
                                }
                                std::swap(start[yy][xx], start[y0][xx]);
                        }
                        if (((xx+1 == x0) || (xx-1 == x0)) && (yy == y0))        {
                                std::swap(start[yy][x0], start[yy][xx]);
                                if (solver_rec(start, stop, y0, xx, depth+1, ctx))        {
                                        std::stringstream s;
                                        s << depth << ". tile " << y0 << "/" << xx;
                                        ctx.solution.push_back(s.str());
                                        return true;
                                }
                                std::swap(start[yy][x0], start[yy][xx]);
                        }
                }
        }
        // remove the abort state
        ctx.abort_states.pop_front();
        return false;
};

bool solver(puzzle_t& start, const puzzle_t& stop, int max_depth)       
{
        context_t ctx;
       
        // search for the 0 element
        int y0=-1, x0=-1;
        for (int y=0; y<3; ++y)        {
                for (int x=0; x<3; ++x)        {
                        if (start[y][x] == 0) {
                                y0 = y;
                                x0 = x;
                                break;
                        }
                }
        }
        assert(y0 != -1);
        assert(x0 != -1);
        // breath first search, assures that a shortest solution is found
        for (ctx.max_depth=0; ctx.max_depth<max_depth; ++(ctx.max_depth))        {
                if (solver_rec(start, stop, y0, x0, 1, ctx))        {
                        std::cout << "---SOLUTION---" << std::endl;
                        for (std::list<std::string>::reverse_iterator it = ctx.solution.rbegin(); it != ctx.solution.rend(); ++it)        {
                                std::cout << *it << std::endl;
                        }
                        return true;
                }
        }
        return false;
}

int main(int argc, char**argv)       
{
        // 3 argument == max_depth
        if (!solver(_puzzle_start, _puzzle_stop, 20))        {
                std::cout << "--- NO SOLUTION ---" << std::endl;
        }
        return 0;
}


يک سورس ديگر به c++

Astaraki ۱۲-۲۵-۱۳۸۸ ۱۲:۰۶ بعد از ظهر

برنامه معمای 8 (پازل 8)
 

كد:

#include
#include
#include
#include
#include

#define TRUE 1
#define FALSE 0

unsigned int a,b,c,d,e,f,g,h;
void main(void)
{
 unsigned char chk_crash(unsigned char,unsigned char,unsigned char);
 void draw_puzzle(void);
 clrscr();
 for (a=1;a<=8;a++);
  for (b=1;b<=8;b++);
  if (chk_crash(a,b,1))
    for (c=1;c<=8;c++)
      if ((chk_crash(c,b,1)) && (chk_crash(c,a,2)))
      for (d=1;d<=8;d++)
    if ((chk_crash(d,c,1)) && (chk_crash(d,b,2)) && (chk_crash(d,a,3)))
    for(e=1;e<=8;e++)
      if  ((chk_crash(e,d,1)) && (chk_crash(e,c,2)) && (chk_crash(e,b,3)) && (chk_crash(e,a,4)))
      for (f=1;f<=8;f++)
        if ((chk_crash(f,e,1)) && (chk_crash(f,d,2)) && (chk_crash(f,c,3)) && (chk_crash(f,b,4)) && (chk_crash(f,a,5)))
        for (g=1;g<=8;g++)
          if ((chk_crash(g,f,1)) && (chk_crash(g,e,2)) && (chk_crash(g,d,3)) && (chk_crash(g,c,4)) && (chk_crash(g,b,5)) && (chk_crash(g,a,6)))
          for (h=1;h<=8;h++)
        if ((chk_crash(h,g,1)) && (chk_crash(h,f,2)) && (chk_crash(h,e,3)) && (chk_crash(h,d,4)) && (chk_crash(h,c,5)) && (chk_crash(h,b,6)) && (chk_crash(h,a,7)))
        {
        draw_puzzle();
        getch();
        }
          getch();
 }
 unsigned char chk_crash(unsigned char i,unsigned char j,unsigned char d)
  {
  if ((i==j) || (abs(i-j)==d))
    return(FALSE);
  else
    return(TRUE);
  }
  void draw_puzzle(void)
  {
  unsigned char a1,b1,a2,b2,i,v;
  clrscr();
  for (a1=1;a1<=16;a1++)
    for (b1=18;b<=65;b1++)
    {
      gotoxy(b1,a1+d);
      a2=(a1-1)/2+1;
      b2=(b1-18)/6+1;
      if (((a2+b2)%2)==0)
      textcolor(11);
      else
      textcolor(1);
      cprintf("A\0");
      for (i=0;i<8;i++)
      {
    switch(i)
    {
      case 0:{v=a;break;}
      case 1:{v=b;break;}
      case 2:{v=c;break;}
      case 3:{v=d;break;}
      case 4:{v=e;break;}
      case 5:{v=f;break;}
      case 6:{v=g;break;}
      case 7:{v=h;break;}
    }
      gotoxy(15+6*v,5+i*2);
      cprintf("*\0");
      }
}
}


Astaraki ۱۲-۲۵-۱۳۸۸ ۱۲:۳۲ بعد از ظهر

حالت خطی
8puzzle


كد:

#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <map>
#include <queue>
using namespace std;
map <string , int> m;
queue < string > qs;
queue < int > qc,qd;
//struct state{
//    string s;
//    int c,d;
//};
//queue <state> q;
void puzzle(int cur,string s){
    if (m.find(s)==m.end()){
        m[s]=qd.front();
        if (cur-1>=0 && cur-1<=8 && cur!=6 && cur!=3){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur-1]; temp[cur-1]=t; }
            qc.push(cur-1);
            qd.push(m[s]+1);
            qs.push(temp);
        }
        if (cur+1>=0 && cur+1<=8 && cur!=2 && cur!=5){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur+1]; temp[cur+1]=t; }
            qc.push(cur+1);
            qd.push(m[s]+1);
            qs.push(temp);
        }
        if (cur-3>=0 && cur-3<=8){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur-3]; temp[cur-3]=t; }
            qc.push(cur-3);
            qs.push(temp);
            qd.push(m[s]+1);
        }
        if (cur+3>=0 && cur+3<=8){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur+3]; temp[cur+3]=t; }
            qc.push(cur+3);
            qs.push(temp);
            qd.push(m[s]+1);
        }
    }
    qs.pop();
    qc.pop();
    qd.pop();
}
int main () {
    clock_t cl=clock();
    ifstream in ("8puzzle.in");
    qs.push("123456780");
    qc.push(8);
    qd.push(0);
    while (!qs.empty())
        puzzle(qc.front(),qs.front());
    int t;
    for (in >> t;t>0;--t){
        string s,temp;
        for (int i=0;i<3;++i)
            for (int j=0;j<3;++j){
                in >> temp;
                if (temp=="-1")
                    temp="0";
                s+=temp;
            }
            if (m.find(s)==m.end())
                cout << "Impossible" << endl;
            else
                cout << m[s] << endl;
    }
    cout << "time: " << (clock()-cl) * 0.001 << endl;
    return 0;
}


Astaraki ۰۳-۸-۱۳۸۹ ۱۱:۱۰ قبل از ظهر

1(ها)ضميمه
Eight-Puzzle (IDA*) with prolog

Astaraki ۰۳-۸-۱۳۸۹ ۱۱:۴۴ قبل از ظهر

1(ها)ضميمه
8Puzzle C Source Code

nasim1212 ۰۳-۱۲-۱۳۸۹ ۱۱:۳۶ بعد از ظهر

میشه حل این برنامه رو با الگوریتم ژنتیک بذارین؟

Astaraki ۰۳-۱۳-۱۳۸۹ ۱۱:۰۶ قبل از ظهر

نقل قول:

نوشته اصلي بوسيله nasim1212 (پست 6256)
میشه حل این برنامه رو با الگوریتم ژنتیک بذارین؟


اميدوارم لينک زيرمفيد باشه:15:

Genetic 8-Puzzle


زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۲:۲۴ بعد از ظهر ميباشد.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.