PDA

View Full Version : الگوریتم 8پازل به روش A*



shima3000
جمعه 30 فروردین 1392, 11:31 صبح
سلام دوستان این ی برنامه کامل از اگوریتم 8پازل ب روش A*هس..اونم گرافیکی!!

میخاستم ببینم کسی میتونه ی توضیحی دربارش بمن بده!!..اخه میخام همینو تحوبل استاد بدم باید یچیزی ازش سر دربیارم..تا حدودوی فهمیدم..
فقط میخاستم هرکسی ک از این برنامه چیزی فهمیده بمن بگه!!..(مخصوصا قسمت هیستوریکش ک نمیدونم چرا iو puzzle[i رو باقی مانده اش رو بر 3ب دست اوورده!

خواهشا کمک کنین..:گریه:


using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;

namespace _8_Puzzle
{
/// <summary>
/// Summary description for Form1.
/// </summary>
public class Form1 : System.Windows.Forms.Form
{
public bool initialopen = false;
internal char[] rep = {'d', 'u', 'l', 'r'};
internal int[] notvalid1 = {6, 0, 0, 2};
internal int[] notvalid2 = {7, 1, 3, 5};
internal int[] notvalid3 = { 8, 2, 6, 8 };
internal int[] applyparam = { +3, -3, -1, +1};
internal int[] goal_Puzzle = {0, 1, 2, 3, 4, 5, 6, 7, 8}; //8 indicates no tile
public int[] initialPuzzle = {0, 1, 2, 3, 4, 5, 6, 7, 8};
internal int maxdepth = 40;
internal elementstruct top;

private System.Windows.Forms.Button[] buttonArray = new Button[9];
private System.Windows.Forms.Button button_play;
private System.Windows.Forms.Button button_initial;

/// <summary>
/// Required designer variable.
/// </summary>
private System.ComponentModel.Container components = null;

public Form1()
{

for(int i = 0;i < buttonArray.Length;i++)
{
this.buttonArray[i] = new System.Windows.Forms.Button();
this.buttonArray[i].Font = new System.Drawing.Font("Microsoft Sans Serif", 14.25F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((System.Byte)(178)));
this.buttonArray[i].Location = new System.Drawing.Point(25+(i%3)*62,30+(i/3)*42);
this.buttonArray[i].Name = "buttonArray";
this.buttonArray[i].Size = new System.Drawing.Size(60, 40);
this.buttonArray[i].TabIndex = i;
if(i != 8)
{
this.buttonArray[i].Text = ""+(i+1);
this.buttonArray[i].BackColor = System.Drawing.SystemColors.Control;
}
else
{
this.buttonArray[i].Text = "";
this.buttonArray[i].BackColor = System.Drawing.SystemColors.ControlDarkDark;
}
this.buttonArray[i].Click += new System.EventHandler(this.buttonArray_Click);
this.Controls.Add(this.buttonArray[i]);
}



//
// Required for Windows Form Designer support
//
InitializeComponent();

//
// TODO: Add any constructor code after InitializeComponent call
//
}

/// <summary>
/// Clean up any resources being used.
/// </summary>
protected override void Dispose( bool disposing )
{
if( disposing )
{
if (components != null)
{
components.Dispose();
}
}
base.Dispose( disposing );
}

#region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
System.ComponentModel.ComponentResourceManager resources = new System.ComponentModel.ComponentResourceManager(typ eof(Form1));
this.button_play = new System.Windows.Forms.Button();
this.button_initial = new System.Windows.Forms.Button();
this.SuspendLayout();
//
// button_play
//
this.button_play.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(178)));
this.button_play.Location = new System.Drawing.Point(250, 210);
this.button_play.Name = "button_play";
this.button_play.Size = new System.Drawing.Size(80, 25);
this.button_play.TabIndex = 0;
this.button_play.Text = "Play";
this.button_play.Click += new System.EventHandler(this.button_play_Click);
//
// button_initial
//
this.button_initial.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(178)));
this.button_initial.Location = new System.Drawing.Point(160, 210);
this.button_initial.Name = "button_initial";
this.button_initial.Size = new System.Drawing.Size(85, 25);
this.button_initial.TabIndex = 1;
this.button_initial.Text = "Initial...";
this.button_initial.Click += new System.EventHandler(this.button_initial_Click);
//
// Form1
//
this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
this.BackColor = System.Drawing.SystemColors.ControlDarkDark;
this.ClientSize = new System.Drawing.Size(342, 261);
this.Controls.Add(this.button_initial);
this.Controls.Add(this.button_play);
this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;
this.Icon = ((System.Drawing.Icon)(resources.GetObject("$this.Icon")));
this.Name = "Form1";
this.StartPosition = System.Windows.Forms.FormStartPosition.CenterScree n;
this.Text = "Play";
this.Load += new System.EventHandler(this.Form1_Load);
this.ResumeLayout(false);

}
#endregion

/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main()
{
Application.Run(new Form1());
}

public void Astarsearch(int[] Puzzle)
{
top = new elementstruct(maxdepth);
for (int i = 0; i < 9; i++)
top.Puzzle[i] = Puzzle[i];
top.totalcost = heur(Puzzle);
elementstruct newnode = new elementstruct(maxdepth);
while (true)
{
elementstruct node = bestnodefromqueue();
if (node == null)
{

MessageBox.Show(this,"There is no solution to this of less than"+maxdepth,"Failed");
break;
}
else if (goal(node.Puzzle))
{
int[] Puzzle2 = new int[9];
for (int i = 0; i < node.pathcost; i++)
{
try
{
System.Threading.Thread.Sleep(1000);
}
catch {}
print_Puzzle(Puzzle);
apply(Puzzle2, Puzzle, op(node.str[i]));
for (int j = 0; j <= 8; j++)
Puzzle[j] = Puzzle2[j];
}
try
{
System.Threading.Thread.Sleep(1000);
}
catch {}
print_Puzzle(Puzzle);
Console.WriteLine("\nGraphical Display Complete.\nThe steps taken were: (Move blank u=up, d=down, l-left, r=right)\n");
Console.WriteLine(node.str);
Console.WriteLine("\n");
break;
}

if (node.totalcost > maxdepth)continue;
for (int i = 0; i <= 3; i++)
{
if (apply(newnode.Puzzle, node.Puzzle, i) == -1)
continue;

if (notonqueue(newnode.Puzzle))
{
prepend(newnode, node, i);
newnode = new elementstruct(maxdepth);
if (newnode == null)
{
Console.WriteLine(
"ERROR!! insufficient memory!! Try decreasing depth!");
}
}
}
}
}


static int heur(int[] Puzzle)
{
int to_return = 0;
for (int i = 0; i < 9; i++)
{
to_return += Math.Abs((i / 3) - (Puzzle[i] / 3));
to_return += Math.Abs((i % 3) - (Puzzle[i] % 3));
}
return to_return;
}


void prepend(elementstruct newnode, elementstruct oldnode, int op)
{
newnode.next = top;
top = newnode;
for (int i = 0; i < newnode.str.Length; i++)
newnode.str[i] = oldnode.str[i];
newnode.str[oldnode.pathcost] = rep[op];
newnode.str[oldnode.pathcost + 1] = '0';
newnode.pathcost = oldnode.pathcost + 1;
newnode.totalcost = newnode.pathcost + heur(newnode.Puzzle);
if (newnode.totalcost < oldnode.totalcost)
newnode.totalcost = oldnode.totalcost;
}


bool goal(int[] Puzzle)
{
for (int i = 0; i < 9; i++)
if (Puzzle[i] != goal_Puzzle[i])
return false;

return true;
}


bool notonqueue(int[] Puzzle)
{
int i;
elementstruct t = top;
while (t != null)
{
for (i = 0; i < 9; i++)
if (t.Puzzle[i] != Puzzle[i])
break;
if (i == 9)
return false;
t = t.next;
}
return true;
}


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 = 0;

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


public void print_Puzzle(int[] Puzzle)
{
for (int i = 0; i < Puzzle.Length; i++)
{
if (Puzzle[i] != 8)
{
buttonArray[i].Text = ""+(Puzzle[i] + 1);
buttonArray[i].BackColor = System.Drawing.SystemColors.Control;
buttonArray[i].Refresh();
}
else
{
buttonArray[i].Text ="";
buttonArray[i].BackColor = System.Drawing.SystemColors.ControlDarkDark;
buttonArray[i].Refresh();
}
}
}


public static bool isvalid(int sou,int des)
{
switch(sou)
{
case 0:
if(des == 1 || des == 3)
return true;
else
return false;
case 1:
if(des == 0 || des == 2 || des == 4)
return true;
else
return false;
case 2:
if(des == 1 || des == 5)
return true;
else
return false;
case 3:
if(des == 0 || des == 4 || des == 6)
return true;
else
return false;
case 4:
if(des == 1 || des == 3 || des == 5 || des == 7)
return true;
else
return false;
case 5:
if(des == 2|| des == 4 || des == 8)
return true;
else
return false;
case 6:
if(des == 3 || des == 7)
return true;
else
return false;
case 7:
if(des == 4 || des == 6 || des == 8)
return true;
else
return false;
case 8:
if(des == 5 || des == 7 )
return true;
else
return false;
default:
return false;
}
}


char to_char(int i)
{
if (i >= 0 && i <= 7)return (char) (i + '1');
else return 'x';
}


int op(char i)
{
switch (i)
{
case 'd':
return 0;
case 'u':
return 1;
case 'l':
return 2;
case 'r':
return 3;
default:
Console.WriteLine("ERROR!");
return -1;
}
}


private void buttonArray_Click(object sender, System.EventArgs e)
{
Button temp = (Button)sender;
if(temp.Text !="")
{
int space;
for(space = 0;space <initialPuzzle.Length;space++)
{
if(initialPuzzle[space] == 8)
break;
}
int clickon;
for(clickon = 0;clickon < buttonArray.Length;clickon++)
{
if(buttonArray[clickon] == temp)
break;
}
// if(isvalid(clickon,space))
// {
buttonArray[space].BackColor = System.Drawing.SystemColors.Control;
buttonArray[space].Text = temp.Text;
initialPuzzle[space] = Convert.ToInt32((temp.Text))-1;
temp.BackColor = System.Drawing.SystemColors.ControlDarkDark;
temp.Text = "";
temp.Refresh();
buttonArray[space].Refresh();
initialPuzzle[clickon] = 8;
// }
}
}


private void button_play_Click(object sender, System.EventArgs e)
{
this.Astarsearch(initialPuzzle);

}


private void button_initial_Click(object sender, System.EventArgs e)
{
if(initialopen == false)
{
Form2 f =new Form2(this);
initialopen = true;
f.Show();
f.Closing +=new CancelEventHandler(f_Closing);

}
}


private void f_Closing(object sender, CancelEventArgs e)
{
initialopen = false;
}

private void Form1_Load(object sender, EventArgs e)
{

}
}


class elementstruct
{
internal int[] Puzzle = new int[9];
internal char[] str;
internal int pathcost;
internal int valid;
internal int totalcost;
internal elementstruct next;

internal elementstruct(int max)
{
valid = 1;
str = new char[max + 1];
str[0] = '0';
pathcost = totalcost = 0;
next = null;

}
}
}

group45
جمعه 30 فروردین 1392, 12:27 عصر
لطفا برنامه رو بزارید نه سورسشو. باید کامپایل شه تا بشه بررسیش کرد

shima3000
جمعه 30 فروردین 1392, 13:33 عصر
لطفا برنامه رو بزارید نه سورسشو. باید کامپایل شه تا بشه بررسیش کرد

بفرمایید...:لبخندساده:

shima3000
جمعه 30 فروردین 1392, 17:21 عصر
کسی نتونست سر دربیاره؟؟

shima3000
شنبه 31 فروردین 1392, 17:26 عصر
static int heur(int[] Puzzle)
{
int to_return = 0;
for (int i = 0; i < 9; i++)
{
to_return += Math.Abs((i / 3) - (Puzzle[i] / 3));
to_return += Math.Abs((i % 3) - (Puzzle[i] % 3));
}
return to_return;
}

حداقل یکی بگه تو هیستوریکش چرا باقی مانده رو بر 3حساب کرده؟؟:گریه:

fortex
شنبه 31 فروردین 1392, 17:52 عصر
الگوریتم *a در شرایط مساوی، اولین سمت چپ ترین گره رو بسط می ده (این یه قرارداده)
پس بسته به این که این دو حالت مساوی فرزند کدام گره ها هستند و با توجه به اینکه اول پدر کدوم شون بسط داده شده، اون گره سمت چپ تر و مقدم تره.
چون الگورتیم همیشه راه بهینه و هدف بهینه رو پیدا می کنه

موفق باشی دوست عزیز

FastCode
شنبه 31 فروردین 1392, 18:25 عصر
فکر نمیکنم نمره بگیری.
چون همون دفعه اول که هئوریستیک رو بگی هیستوریک استاد از کلاس میندازدت بیرون.

shima3000
شنبه 31 فروردین 1392, 19:04 عصر
[QUOTE=FastCode;1749928]فکر نمیکنم نمره بگیری.
چون همون دفعه اول که هئوریستیک رو بگی هیستوریک استاد از کلاس میندازدت بیرون.[/QUOTE

نه بابا هئوریستیک!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!
:قهقهه:

سوادتون درهمین حد بود!!..هئوریستیک ،همینقد الگوریتم روفهمیدی ؟؟!!!!!!!!!!..

ما نمیخاد جوش اونو بزنین!!...:چشمک::لبخند:

shima3000
شنبه 31 فروردین 1392, 19:07 عصر
الگوریتم *a در شرایط مساوی، اولین سمت چپ ترین گره رو بسط می ده (این یه قرارداده)
پس بسته به این که این دو حالت مساوی فرزند کدام گره ها هستند و با توجه به اینکه اول پدر کدوم شون بسط داده شده، اون گره سمت چپ تر و مقدم تره.
چون الگورتیم همیشه راه بهینه و هدف بهینه رو پیدا می کنه

موفق باشی دوست عزیز


اهان یجورایی فهمیدم چیکارا میکنه...!!

خونه خالی هرجا باشه برای مثلا چپ رفتنش باید باقی مونده اش رو بر 3 بدست می اره..و تو positionش قرار میده!!..دوباره برا راست رفتن کافیه تقسیم بر 3بشه و خارج قسمت بدست بیاد!!

بازم از راهنماییتون ممنونم!!!:چشمک: