mhd-kvn
سه شنبه 06 خرداد 1393, 21:18 عصر
سلام به برنامه نویسان بسیار حرفه ای و حرفه ی و نیمه حرفه ای و مبتدی و آماتور(مثل خودم)
من دارم الگوریتم A* (که مربوط به جستجوی آگاهانه در مبحث هوش مصنوعی هست) رو با ++c پیاده سازی می کنم. البته هنوز کامل نشده. می خوام خروجی بگیرم تا ببینم آیا برنامه تا جایی که نوشتم درست عمل می کنه یا نه؟ اما بعد از کامپایل شدن این خطا ظاهر می شه:
119563
متوجه شدم که ایراد کار در قسمت مرتب سازی صف هست. برای مرتب سازی از MergeSort استفاده کردم. قبل از اینکه کدهای لازم رو بذارم بزارین اینو بهتون بگم:
در قسمتی که قراره گره با کمترین هزینه بسط داده بشه، در ابتدا فقط این شرط رو بررسی کرده بودم که الگوریتم فقط گره هایی رو بسط بده(به صف اضافه کنه) که مسیر باز باشه( در نقشه ی من 1 یعنی مسیر باز)مثلا:
if (matrix[x][y + 1] == 1)
Node n1(1, x, y + 1, desx, desy, depth, n);
q -> AddQueue(n1);
وقتی که خروجی گرفتم دیدم همه چیز درست کار کرده. گره ها به شکل درستی به صف اضافه شدن، مرتب سازی درست انجام شده و کلا همه چیز OK بود. اما وقتی که به شرط بالا این مورد رو هم اضافه کردم که گره هایی که قبلا بررسی شدن و از صف حذف شده بودن، دوباره اضافه نشن، این مشکل شروع شد. تابع بسط من به این صورته:
void expand(Node n, Node array_node[8], int desx, int desy, Queue *q)
q به صف اشاره می کنه. در این تابع من تابعی به نام similar رو فراخونی کردم. این تابع هم به این شکل:
bool similar(int i, int j, Queue *qu)
نحوه فراخوانی این تابع در expand به این صورت:
similar(x, y + 1, &q);
دیدم خطا ظاهر شد، بی خیال اشاره گر شدم و مقدار صف رو داخل یک صف دیگه کپی کردم:
bool similar(int i, int j, Queue qu
similar(x, y + 1, *q);
دیدم دوباره اون پیغام بالا ظاهر شد. به این صورت تغییر دادم:
bool similar(int i, int j, Queue *qu)
similar(x, y + 1, &(*q));
گفتم این بار دیگه حله. چون داشتم از یه اشاره گر دیگه به همون صف استفاده می کردم. اما بازم همون آش و همون کاسه.. خواستم با لگد برم تو لپ تاپ بعد یادم اومد الان دیگه نمیشه لپ تاپ خرید. خلاصه جونم بهتون بگه رفتم سراغ trace کردن. این جا بود که دیگه برق از سرم پرید. دیدم مشکل similar حل شده و ایراد از تابع مرتب سازیمه. تابعی که داشت درست عمل می کرد! مشکل اونجا هم مربوط به همین اشاره گر ها بوده. کد تابع مرتب سازیم رو پایین ملاحضه کنین.برای مثال فرض کنین که دارین یک صف ۶ عنصری رو مرتب می کنین. صف اول به ۲ قسمت چپ و راست ۳ عنصری تبدیل و بعد صف چپیه به ۲ قسمت ۱ عنصری(چپ) و ۲ عنصری(راست) تقسیم میشه. وقتی که MergeSort برای صف چپی(۱ عنصری) فراخوانی میشه و از این تابع بر میگرده خطا اتفاق می افته و پیغام بالا ظاهر میشه.
void MergeSort(int size, Queue *q)
{
int left_size = size / 2;
int right_size = size - left_size;
Queue left(left_size), right(right_size);
int i;
int f = q -> GetFront() + 1;
if (size > 1)
{
for (i = 0; i < left_size; i++)
{
left.AddQueue(q -> GetNode(f));
f++;
}
for (i = 0; i < right_size; i++)
{
right.AddQueue(q ->GetNode(f));
f++;
}
MergeSort(left_size, &left);
MergeSort(right_size, &right);
merge(left_size, right_size, left, right, q);
}
}
void merge(int left_size, int right_size, Queue left, Queue right, Queue *q)
{
int i, j, r;
i = 0;
j = 0;
r = q -> GetRear() - (left_size + right_size);
q -> SetRear(r);
while (i < left_size && j < right_size)
{
if (left.GetNode(i).getTotal() < right.GetNode(j).getTotal())
{
q -> AddQueue(left.GetNode(i));
i++;
}
else
{
q -> AddQueue(right.GetNode(j));
j++;
}
}
if (i >= left_size)
while (j < right_size)
{
q ->AddQueue(right.GetNode(j));
j++;
}
else
while (i < left_size)
{
q ->AddQueue(left.GetNode(i));
i++;
}
}
اگه خوب نتونستم توضیح بدم منو ببخشین... هر جا ابهامی هست بهم بگین. فقط امیدوارم جوابم رو بگیرم:لبخندساده:
من دارم الگوریتم A* (که مربوط به جستجوی آگاهانه در مبحث هوش مصنوعی هست) رو با ++c پیاده سازی می کنم. البته هنوز کامل نشده. می خوام خروجی بگیرم تا ببینم آیا برنامه تا جایی که نوشتم درست عمل می کنه یا نه؟ اما بعد از کامپایل شدن این خطا ظاهر می شه:
119563
متوجه شدم که ایراد کار در قسمت مرتب سازی صف هست. برای مرتب سازی از MergeSort استفاده کردم. قبل از اینکه کدهای لازم رو بذارم بزارین اینو بهتون بگم:
در قسمتی که قراره گره با کمترین هزینه بسط داده بشه، در ابتدا فقط این شرط رو بررسی کرده بودم که الگوریتم فقط گره هایی رو بسط بده(به صف اضافه کنه) که مسیر باز باشه( در نقشه ی من 1 یعنی مسیر باز)مثلا:
if (matrix[x][y + 1] == 1)
Node n1(1, x, y + 1, desx, desy, depth, n);
q -> AddQueue(n1);
وقتی که خروجی گرفتم دیدم همه چیز درست کار کرده. گره ها به شکل درستی به صف اضافه شدن، مرتب سازی درست انجام شده و کلا همه چیز OK بود. اما وقتی که به شرط بالا این مورد رو هم اضافه کردم که گره هایی که قبلا بررسی شدن و از صف حذف شده بودن، دوباره اضافه نشن، این مشکل شروع شد. تابع بسط من به این صورته:
void expand(Node n, Node array_node[8], int desx, int desy, Queue *q)
q به صف اشاره می کنه. در این تابع من تابعی به نام similar رو فراخونی کردم. این تابع هم به این شکل:
bool similar(int i, int j, Queue *qu)
نحوه فراخوانی این تابع در expand به این صورت:
similar(x, y + 1, &q);
دیدم خطا ظاهر شد، بی خیال اشاره گر شدم و مقدار صف رو داخل یک صف دیگه کپی کردم:
bool similar(int i, int j, Queue qu
similar(x, y + 1, *q);
دیدم دوباره اون پیغام بالا ظاهر شد. به این صورت تغییر دادم:
bool similar(int i, int j, Queue *qu)
similar(x, y + 1, &(*q));
گفتم این بار دیگه حله. چون داشتم از یه اشاره گر دیگه به همون صف استفاده می کردم. اما بازم همون آش و همون کاسه.. خواستم با لگد برم تو لپ تاپ بعد یادم اومد الان دیگه نمیشه لپ تاپ خرید. خلاصه جونم بهتون بگه رفتم سراغ trace کردن. این جا بود که دیگه برق از سرم پرید. دیدم مشکل similar حل شده و ایراد از تابع مرتب سازیمه. تابعی که داشت درست عمل می کرد! مشکل اونجا هم مربوط به همین اشاره گر ها بوده. کد تابع مرتب سازیم رو پایین ملاحضه کنین.برای مثال فرض کنین که دارین یک صف ۶ عنصری رو مرتب می کنین. صف اول به ۲ قسمت چپ و راست ۳ عنصری تبدیل و بعد صف چپیه به ۲ قسمت ۱ عنصری(چپ) و ۲ عنصری(راست) تقسیم میشه. وقتی که MergeSort برای صف چپی(۱ عنصری) فراخوانی میشه و از این تابع بر میگرده خطا اتفاق می افته و پیغام بالا ظاهر میشه.
void MergeSort(int size, Queue *q)
{
int left_size = size / 2;
int right_size = size - left_size;
Queue left(left_size), right(right_size);
int i;
int f = q -> GetFront() + 1;
if (size > 1)
{
for (i = 0; i < left_size; i++)
{
left.AddQueue(q -> GetNode(f));
f++;
}
for (i = 0; i < right_size; i++)
{
right.AddQueue(q ->GetNode(f));
f++;
}
MergeSort(left_size, &left);
MergeSort(right_size, &right);
merge(left_size, right_size, left, right, q);
}
}
void merge(int left_size, int right_size, Queue left, Queue right, Queue *q)
{
int i, j, r;
i = 0;
j = 0;
r = q -> GetRear() - (left_size + right_size);
q -> SetRear(r);
while (i < left_size && j < right_size)
{
if (left.GetNode(i).getTotal() < right.GetNode(j).getTotal())
{
q -> AddQueue(left.GetNode(i));
i++;
}
else
{
q -> AddQueue(right.GetNode(j));
j++;
}
}
if (i >= left_size)
while (j < right_size)
{
q ->AddQueue(right.GetNode(j));
j++;
}
else
while (i < left_size)
{
q ->AddQueue(left.GetNode(i));
i++;
}
}
اگه خوب نتونستم توضیح بدم منو ببخشین... هر جا ابهامی هست بهم بگین. فقط امیدوارم جوابم رو بگیرم:لبخندساده: