بالا
 تعرفه تبلیغات




 دانلود نمونه سوالات نیمسال دوم 93-94 پیام نور

 دانلود نمونه سوالات آزمونهای مختلف فراگیر پیام نور

نمایش نتایج: از شماره 1 تا 10 از مجموع 10

موضوع: الگوريتم مربع هشت ( 8-puzzle )

  1. #1
    Y@SiN آواتار ها
    • 2,083

    عنوان کاربری
    مدیر بازنشسته بخش کامپیوتر و تخصصی IT
    تاریخ عضویت
    Mar 2009
    راه های ارتباطی

    Icon30 الگوريتم مربع هشت ( 8-puzzle )

    مربع هشت ( 8-puzzle )


    در یک مربع 3 در 3 که شامل 9 خانه کوچک است ، هشت مربع شماره گذاری شده قرار داده ایم . یکی از خانه ها نیز خالی است . مسئله با یک حالت اولیه شروع می شود . هدف چیدن مربع های شماره گذاری شده به ترتیب روبرو است ( حالت هدف ) :



    نکته مسئله مربع هشت اینسنت که فقط مربع های اطراف خانه خالی را می توانیم با خانه خالی تعویض کنیم . یعنی با حرکت دادن مکرر خانه خالی به چپ ، راست ، بالا و پایین باید به حالت هدف برسیم . برای حل این مساله می توان از روش جستجوی A* استفاده کرد . برای این مسئله چند هیوریستیک مختلف وجود دارد . دو هیوریستیک معمول به صوزت زیر هستند :
    1) هیوریستیک اول سعی می کند خانه خالی را طوری جابجا کند که تعداد مربع هایی را در خانه خود قرار نگرفته اند ، صفر شود . یعنی این هیوریستیک بر اساس تعداد مربع هایی که در خانه خود قرار نگرفته اند ، جستجو انجام می دهد.

    2) هیوریستیک دوم مجموع فاصله های بلوک شهری هر مربع از خانه خود را محاسبه کرده و سعی می کند خانه حالی را طوری حرکت دهد که این مقدار را به صفر برسد .
    Y@SiN
    فعلا امضا نداريم.باشگاه داريم

  2. #2
    • 4

    عنوان کاربری
    کاربر باشگاه
    تاریخ عضویت
    Nov 2012
    محل تحصیل
    birjand
    راه های ارتباطی

    پیش فرض

    سلام
    کد الگوریتم مربوط به پازل 8 تایی را قرار میدهید؟
    با تشکر

  3. #3
    sunyboy آواتار ها
    • 33,773
    مدیـریت کــل باشگاه

    عنوان کاربری
    مدیــــریت کـــــل باشگاه
    تاریخ عضویت
    Sep 2008
    محل تحصیل
    علوم - فناوری
    شغل , تخصص
    وب مستر - طراح وب
    رشته تحصیلی
    مهندسی نرم افزار
    راه های ارتباطی

    پیش فرض

    نقل قول نوشته اصلی توسط far.farzane نمایش پست ها
    سلام
    کد الگوریتم مربوط به پازل 8 تایی را قرار میدهید؟
    با تشکر


    بفرمایید

    کد:
    /*
     	Solution of the 8 puzzle.
     	Uses A-Star algorithm.
     	*/
     	#include <stdio.h>
    	#include <string.h>
    	#include <iostream.h>
    	#include <math.h>
    	#include <stdlib.h>
     	#define DOWN 0
    	#define UP 1
    	#define LEFT 2
    	#define RIGHT 3
    	#define H2
     	struct elementstruct
    	{
    	  int block[9];
    	  char* str;
    	  int pathcost;
    	  int valid;
    	  int totalcost;
    	  elementstruct* next;
    	};
     	int heur(int block[]);
    	void prepend(elementstruct* newnode, elementstruct* oldnode, int operator1);
    	int goal(int* block);
    	int notonqueue(int block[]);
    	elementstruct* bestnodefromqueue();
    	void print_block(int* block);
    	int apply (int* newstate, int* oldstate, int op);
    	elementstruct* newelement();
    	int op(char);
    	char to_char(int i);
     	char rep[] = "dulr";
    	int notvalid1[4] = { 6, 0, 0, 2 };
    	int notvalid2[4] = { 7, 1, 3, 5 };
    	int notvalid3[4] = { 8, 2, 6, 8 };
    	int applyparam[4] = { +3, -3, -1, +1 };
    	int goal_block[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8}; //8 indicates no tile
    	int maxdepth;
    	elementstruct* top;
     	int main()
    	{
    	  int block[9];
     	  printf("\nThe Eight Puzzle!\n");
     	  printf("\nPlease Enter the initial state of the game \n"
    	         " [Represent tiles with numbers 1 to 8, and the blank space as 'x'.\n"
    	         " Start writing them from left to right for each row. Start from the topmost row to the bottommost row.\n"
    	         " Your final string will look similar to this '1 4 2 3 x 6 7 8 5'.\n"
    	         " Do not forget the spaces in between the characters]\n");
     	  int i = 0;
    	  while(i<9)
    	    {
    	    char chr;
    	    chr = fgetc(stdin);
    	    if (chr==32) continue;
    	    if (chr=='x') block[i] = 8;
    	    else if (chr >= '1' && chr <= '9') block[i] = chr - '1';
    	    else { printf("Invalid Input. Example of valid input...2 1 3 4 7 5 6 8 x.", chr); return 1; }
    	    i++;
    	    }
     	  fgetc(stdin); //flush out the end of line character
     	  printf("\n Now Enter the Goal State in a similar way. (Typical. 1 2 3 4 5 6 7 8 x): ");
     	  i = 0;
    	  while(i<9)
    	    {
    	    char chr;
    	    chr = fgetc(stdin);
    	    if (chr==32) continue;
    	    if (chr=='x') goal_block[i] = 8;
    	    else if (chr >= '1' && chr <= '9') goal_block[i] = chr - '1';
    	    else { printf("chr=%d. Invalid Input. Example of valid input...2 1 3 4 7 5 6 8 x.",(int) chr); return 1; }
    	    i++;
    	    }
     	  printf("Enter the maximum depth you want to search (<25 is solved quickly): ");
    	  scanf("%d", &maxdepth);
     	  printf("\nWorking...");
     	  top = newelement();
    	  for(i=0; i<9; i++)
    	    top->block[i] = block[i];
    	  top->totalcost = heur(block);
    	 
    	  elementstruct* newnode = newelement();
     	  while (1)
    	    {
    	      elementstruct* node = bestnodefromqueue();
    	      if (node == NULL) {
    	    printf("done!\n");
    	    printf("There is no solution to this of less than %d depth.\n", maxdepth);
    	    printf("Try increasing the depth by 5.\n");
    	    printf("If there is no solution within 35-40 depth, the pattern is usually unsolvable.\n\n");
    	    break;
    	      }
    	      else if (goal(node->block)) {
    	    char chr[15];
    	    printf("done. \nFound the solution of least number of steps (%d).", node->pathcost);
    	    printf("\nWant a graphical display of each step? (Y/N)?");
    	    scanf("%s", chr);
    	    if(chr[0] =='n' || chr[0]=='N') {
    	      printf("\n (Move Blank u=up, d=down, l=left, r=right)\n");
    	      printf(node->str);
    	      printf("\n");
    	      break;
    	    }
    	    
    	    int block2[9];
    	    for (i=0; i<node->pathcost; i++)
    	      {
    	        print_block(block);
    	        apply(block2, block, op(node->str[i]));
    	        for(int j=0; j<=8; j++)
    	          block[j] = block2[j];
    	      }
    	    print_block(block);
    	    
    	    printf("\nGraphical Display Complete.\nThe steps taken were: (Move blank u=up, d=down, l-left, r=right)\n");
    	    printf(node->str);
    	    printf("\n");
    	    break;
    	    
    	      }
     	      if (node->totalcost > maxdepth) continue;
     	      for(i=0; i<=3; i++) {
    	    if (apply(newnode->block, node->block, i) == -1)
    	      continue;
     	    if (notonqueue(newnode->block)) {
    	      prepend(newnode, node, i);
    	      newnode = newelement();
    	      if (newnode==NULL) { printf ("ERROR!! insufficient memory!! Try decreasing depth!"); return 1; }
    	    }
    	      }
     	    }
    	    return 0;
    	}
     	int heur(int* block)
    	{
    	#ifdef H2
    	  int to_return = 0;
     	  for(int i=0; i<9; i++)
    	    {
    	    to_return += abs((i/3) - (block[i]/3));
    	    to_return += abs((i%3) - (block[i]%3));
    	    }
    	  return to_return;
    	 
    	#else
    	  int to_return = 0;
     	  for(int i=0; i<9; i++)
    	    {
    	      if (block[i] != i) to_return++;
    	    }
    	  return to_return;
    	 
     	#endif
     	}
     	void prepend(elementstruct* newnode, elementstruct* oldnode, int op)
    	{
    	  newnode->next = top;
    	  top = newnode;
     	  strcpy(newnode->str, oldnode->str);
    	  newnode->str[oldnode->pathcost] = rep[op];
    	  newnode->str[oldnode->pathcost+1] = 0;
     	  newnode->pathcost = oldnode->pathcost+1;
    	  newnode->totalcost = newnode->pathcost + heur(newnode->block);
    	  if (newnode->totalcost < oldnode->totalcost) newnode->totalcost = oldnode->totalcost;
    	}
     	int goal(int* block)
    	{
    	  int* g_block = goal_block;
     	  for(int i=0; i<9; i++)
    	    if ((*(block++))!=(*(g_block++)))
    	      return 0;
     	  return 1;
    	}
     	int notonqueue(int* block)
    	{
    	  int i,j;
    	  elementstruct* t = top;
    	 
    	  while (t!=NULL)
    	    {
    	      for(i=0; i<9; i++)
    	    if (t->block[i] != block[i]) break;
    	      if (i==9) return 0;
    	      
    	      t = t->next;
    	    }
    	  return 1;
    	}
     	elementstruct* bestnodefromqueue()
    	{
    	  elementstruct* t = top;
    	  int min_totalpathcost = 1000;
    	  int totalpathcost;
    	  elementstruct* to_return = NULL;
     	  while (t != NULL)
    	    {
    	      if (t->valid==1 && t->totalcost < min_totalpathcost)
    	    {
    	    min_totalpathcost = t->totalcost;
    	    to_return = t;
    	    }
    	      t = t->next;
    	    }
    	 
    	  if (to_return != NULL) to_return->valid = 0;
     	  return to_return;
    	}
     	int apply (int* newstate, int* oldstate, int op)
    	{
    	  int j;
    	  int blank;
     	  for (j=0; j<9; j++)
    	    if (oldstate[j]==8) { blank=j; break; }
     	  if (blank==notvalid1[op] || blank==notvalid2[op] || blank==notvalid3[op])
    	    return -1;
     	  for (j=0; j<9; j++)  
    	    newstate[j] = oldstate[j];
     	  newstate[blank] = newstate[blank+applyparam[op]];
    	  newstate[blank+applyparam[op]] = 8;
     	  return 1;
    	}
     	elementstruct* newelement()
    	{
    	  elementstruct* t = new elementstruct;
    	  if (t==NULL) return NULL;
    	  t->valid = 1;
    	  t->str = new char[maxdepth+1];
    	  if (t->str ==NULL) return NULL;
    	  t->str[0] = 0;
    	  t->pathcost = t->totalcost = 0;
    	  t->next = NULL;
    	  return t;
    	}
     	void print_block(int* block)
    	{
    	  printf("\n");
    	  printf ("\n-------");
    	  printf ("\n|%c|%c|%c|", to_char(block[0]), to_char(block[1]), to_char(block[2]));
    	  printf ("\n-------");
    	  printf ("\n|%c|%c|%c|", to_char(block[3]), to_char(block[4]), to_char(block[5]));
    	  printf ("\n-------");
    	  printf ("\n|%c|%c|%c|", to_char(block[6]), to_char(block[7]), to_char(block[8]));
    	  printf ("\n-------");
    	}
     	char to_char(int i)
    	{
    	  if (i>=0 &&i<=7) return i+'1';
    	  else if (i==8) return 'x';
    	  else { printf("ERROR in Program!"); return -1; }
     	}
     	int op(char i)
    	{
    	switch (i)
    	  {
    	  case 'd': return 0;
    	  case 'u': return 1;
    	  case 'l': return 2;
    	  case 'r': return 3;
    	  default: printf("ERROR!"); return -1;
    	  }
    	}





    فروشگاه نمونه سوالات پیام نور با پاسخنامه تستی و تشریحی


    دانلود رایگان نمونه سوالات نیمسال اول 93-92 پیام نور

    دانلود رایگان نمونه سوالات نیمسال دوم 92-91 پیام نور مقطع کارشناسی

    دانلود رایگان مجموعه نمونه سوالات تمامی رشته های پیام نور نیمسال اول 90-91 دانشگاه پیام نور


    دانلود نمونه سوالات آزمون فراگیر کارشناسی ارشد تمامی دوره های دانشگــــاه پیــــام نور




    دانلود مجموعه نمونه سوالات ارشد فراگیر پیام نور




    برای دانلود رایگان نمونه سوالات پیام نور با جوابهای تستی و تشریحی در مقطع نمونه سوالات کارشناسی ارشد پیام نور - نمونه سوالات پیام نور کارشناسی - نمونه سوالات پیام نور دکترا- نمونه سوالات آزمونهای فراگیر پیام نور( دانشپذیری)

    به ادرس زیر مراجعه کنید

    نمونه سوالات رایگان پیام نور


    ********************************



    ********************************




  4. #4
    • 4

    عنوان کاربری
    کاربر باشگاه
    تاریخ عضویت
    Nov 2012
    محل تحصیل
    birjand
    راه های ارتباطی

    پیش فرض

    سلام
    خیلی خیلی ممنونم

    میخواستم ببینم حل این پازل با استفاده از جستجوی تعمقی تدریجی هم همین قطعه کد می باشد؟
    اگر نیست ممکن است قطعه کد آنرا با این جستجو در اختیار بزارین
    با سپاس فراوان

  5. #5
    • 4

    عنوان کاربری
    کاربر باشگاه
    تاریخ عضویت
    Nov 2012
    محل تحصیل
    birjand
    راه های ارتباطی

    پیش فرض

    سلام
    خیلی خیلی ممنونم

  6. #6
    • 4

    عنوان کاربری
    کاربر باشگاه
    تاریخ عضویت
    Nov 2012
    محل تحصیل
    birjand
    راه های ارتباطی

    پیش فرض

    سلام
    امکانش هست شبه کد یا ایده حل 8پازل را به روش عمقی تدریجی بگذارید؟

  7. #7
    • 1

    عنوان کاربری
    کاربر باشگاه
    تاریخ عضویت
    Aug 2012
    راه های ارتباطی

    پیش فرض

    سلام اگه امکانش هست توضیح کامل و سورس کد 8 پازل را با توجه به جست و جوی آگاهانه و نا آگاهانه قرار بدهید خیلی ضروریه ممنون میشم.

  8. #8
    Borna66 آواتار ها
    • 55,397
    مدير بازنشسته

    عنوان کاربری
    مدير بازنشسته
    تاریخ عضویت
    Mar 2009
    محل تحصیل
    خيام-سهراب
    شغل , تخصص
    طراح و تحلیل گر حرفه ای وب
    رشته تحصیلی
    مهندسي نرم افزار
    راه های ارتباطی

    پیش فرض

    با سلام

    چشم دوستان اگر فراهم سازی شد حتما درج و خدمتون اطلاع رسانی می کنیم ولی قولی در این باره داده نمیشه خدمتون

    موفق باشید

    روزگار خوش




    فروشگاه نمونه سوالات پیام نور با پاسخنامه تستی و تشریحی



    دانلود رایگان نمونه سوالات دانشگاه پیام نور





    http://up.pnu-club.com/images/00ld7yux3ay3itvspd7n.png
    برای دانلود رایگان نمونه سوالات پیام نور با جوابهای تستی و تشریحی در مقطع نمونه سوالات کارشناسی ارشد پیام نور - نمونه سوالات پیام نور کارشناسی - نمونه سوالات پیام نور دکترا- نمونه سوالات آزمونهای فراگیر پیام نور( دانشپذیری)

    به ادرس زیر مراجعه کنید

    نمونه سوالات رایگان پیام نور




  9. #9
    • 1

    عنوان کاربری
    کاربر باشگاه
    تاریخ عضویت
    Mar 2013
    شغل , تخصص
    دانشجو
    رشته تحصیلی
    مهندسی کامپیوتر
    راه های ارتباطی

    پیش فرض

    سلام
    خسته نباشید

    ببخشید میتونه کسی بگ الان این برنامه ای ک انیجا نوشتین براساس کدوم هیستوریک هس؟؟

    ی کمم درباره این الگوریتم توضیح بدین من گیج شدم!!

    ممنون میشم ی کم کمک کنید.

  10. #10
    • 1

    عنوان کاربری
    کاربر باشگاه
    تاریخ عضویت
    May 2015
    راه های ارتباطی

    پیش فرض

    نقل قول نوشته اصلی توسط shima_70 نمایش پست ها
    سلام
    خسته نباشید

    ببخشید میتونه کسی بگ الان این برنامه ای ک انیجا نوشتین براساس کدوم هیستوریک هس؟؟

    ی کمم درباره این الگوریتم توضیح بدین من گیج شدم!!

    ممنون میشم ی کم کمک کنید.
    فکر کنم عمقی محدود باشه.

برچسب برای این موضوع

مجوز های ارسال و ویرایش

  • شما نمی توانید موضوع جدید ارسال کنید
  • شما نمی توانید به پست ها پاسخ دهید
  • شما نمی توانید فایل پیوست ضمیمه کنید
  • شما نمی توانید پست های خود را ویرایش کنید
  •