پیدا کردن الگو

[iut.ali]

سلام من میخوام برنامه ای بنویسم که یه الگویی رو تو یه ماتریس پیدا کنه. فرض کنید ماتریسی مثل زیر داشته باشیم


156
4
156
4
78
83


0
156
69
39
69
4


78
5
78
5
78
117


117
72
117
0
117
5


0
30
39
30
0
78


82
78
78
80
156
30


همونطور که در جدول میبینید اعداد ۴و ۵و ۳۰ با ترتیب خاصی (بین هر کدوم یه عدد قرار گرفته) توی ستونها که اونم ترتیب داره اومده(بین هر الگو یک ستون قرار گرفته) حالا من باید این الگو ها رو پیدا کنم در ضمن چون حافظه برام اهمیت داره نمیتونم تموم حالات رو بررسی کنم. راستش هیچ ایده ای واسه انجامش به جز در نظر گرفتن تمام حالت ها ندارم تا اونجایی هم که میدونم یه ربطایی به هوش مصنوعی داره که خب چیزی هنوز ازش نمیدونم. ممنون میشم اگه بهم ایده بدید یا حداقل سرنخی واسه رسیدن به جواب :متفکر:

[rahnema1]

سلام، الان این چه الگوییه؟ یعنی در ابتدا مشخص نیست الگو چیه و بعدا پیدا می شه و یا اینکه ابتدا لگو را می دهیم و می خواهیم جستجو کنیم؟ فکر کنم یه کم لازمه بیشتر توضیح بدید

[ali chegini]

سلام. اگر فرضا عدد ها رو به صورت زیر ببینیم .

a a 4 a 4 a
4 a a a a a

می تونیم عبارت منظم زیر رو در نظر بگیریم.و x رو از ستون اول ردیف های فرد به دست بیاریم.
aaxaxa

فکر نکنم نیاز به هوش مصنوعی باشه .
سوالت رو دقیقتر مطرح کن .

[iut.ali]

سلام، الان این چه الگوییه؟ یعنی در ابتدا مشخص نیست الگو چیه و بعدا پیدا می شه و یا اینکه ابتدا لگو را می دهیم و می خواهیم جستجو کنیم؟ فکر کنم یه کم لازمه بیشتر توضیح بدید
ابتدا الگو رو نداریم و میخوایم که الگو رو پیدا کنیم. در واقع اعداد از کاربر گرفته میشه و بعد بدنبال الگو میگردیم به عنوان مثال دیگه ماتریس زیر رو در نظر بگیرید


16
3
25
2


2
14
2
3


3
8
3
5


5
12
36
10


تو جدول بالا اعداد ۲و ۳و ۵ به عنوان یک الگو در نظر گرفته میشه شابد فک کنید که ۲و ۳ از ستون اول و دوم هم میتونه یه الگو باشه ولی نکته این جاس که توی ستون ها هم باید این ترتیب وجود داشته باشه یعنی اگه قراره بعنوان یه الگو در نظر گرفته بشه باید توی همه ی ستون ها وجود داشته باشه. در واقع اگه اختلاف بین دو ستون رو هم بعنوان معیار در نظر بگیریم پس توی تموم ستون ها باید الگو تکرار شده باشه. تو مثال اولی که زدم اختلاف بین ستون ها دو شده که میبینید توی ستون های فرد الگو تکرار شده. توی همین مثال اگه هفت تا ستون داشتیم توی هفتمین ستون هم باید همین الگو یعنی ۲و ۳و ۵ با همین ترتیب تکرار میشد تا بعنوان الگوی صحیح در نظر گرفته بشه. نمیدونم تونستم منظورمو برسونم یا نه؟ اگه بازم نیاز به توضیح هست بگید تا بگم

[iut.ali]

سلام. اگر فرضا عدد ها رو به صورت زیر ببینیم .

a a 4 a 4 a
4 a a a a a

می تونیم عبارت منظم زیر رو در نظر بگیریم.و x رو از ستون اول ردیف های فرد به دست بیاریم.
aaxaxa

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

[rahnema1]

توضیح کافی نیست. با چه معیاری؟
لطفا سوال را دقیق توضیح بدید تا جواب دقیق بگیرید.
-نوع و تعداد ورودی کاملا مشخص کنید
-نوع و تعداد خروجی کاملا مشخص کنید
-الگو ها با چه معیاری باشند
-اصلا به چه دردی می خوره
اگه هر معیاری مد نظر ما باشه بی نهایت الگو می شه پیدا کرد
عدد 5 چرا جزء اعداد حساب شده؟

[iut.ali]

در این پروژه آرایه ای دو بعدی مربعی با سایز دلخواه حداقل ۴ از کاربر گرفته میشه. ویژگی های الگو بصورت زیر است:
در ستون ها سه عدد وجود دارند که به تناوب فاصله ی عمودی و افقی تکرار می شوند.ولی در این جدول ها الگو های زیادی وجوددارند.ولی باید الگوی اول را پیدا کنید.در صورت پیدا کردن الگوی اشتباهی مساله ی شما اشتباه خواهد بود.فاصله ی دو ستونی کهدارای الگو هستد d نامیده می شود.همچنین سه عدد پیدا شده به عنوان الگو را a,b,c در نظر می گیریم.اگر d و a,b,c رادرست پیدا کنید سایر عدد ها در ستون ها طوری قرار داده شده اند که ضریبی بین d-7 و d+7 دارند و شما باید این اعداد را درجدول صفر کنید.سه عدد a,b,c را نیز صفر کنید.در صورت درست انجام دادن این کار در هر ستون فقط یک عدد می ماند کهصفر نمی شود.باید این اعداد را از جدول استخراج کنید و آن را به حروف الفبای متناظرشان تبدیل کنید . خروجی برنامه ی شماباید کنار هم چیدن این حروف به ترتیب شماره ی ستون باشد.اعداد طوری چیده شده اند که اگر اعداد را درست پیدا کنیدخروجی شما خروجی معنا داری خواهد شد.
خب حالا اگه این فرمولو روی مثال اول(مثال دوم فقط برای تفهیم بدست آوردن الگو بود وگرنه از شرایط بالا پیروی نمیکنه) پیاده کنیم به یه جدول مثه زیر میرسیم:


0
0
0
0
0
83


0
0
69
0
69
0


0
0
0
0
0
0


0
72
0
0
0
0


0
0
0
0
0
0


82
0
0
80
0
0


که اگه معادل کاراکتری اعداد رو بدست بیاریم کلمه ی SEPEHR بدست میاد.
این متن پروژه بود. نمیدونم کافی بود یا نه...

[iut.ali]

بعنوان یه مثال دیگه جدول زیر رو در نظر بگیرید:


7
0
112
82
112
0
77


6
112
90
28
72
69
28


15
28
0
7
-56
-28
0


28
65
0
6
56
84
7


0
168
112
15
28
0
6


68
140
168
28
0
28
15


84
28
112
0
0
84
28



توی این جدول الگوی ما میشه اعداد ۷و ۶و ۱۵(در واقع ۷و ۶و ۱۵و ۲۸ تکرار شده اند ولی چون دنباله ی تناوب ۳ تایی است پس تناوب اول در نظر گرفته میشه). اگه فرمول بالا رو روش اجرا کنیم آخر سر به کلمه ی MEHRZAD میرسیم

[Desaghi]

در مثال اول چرا 156 صفر شده ؟یا 39 ؟

[rahnema1]

لازم نیست کل جدول جستجو بشه
مثلا در ستونها تا نصف ستونها لازم نیست جلو تر بریم یعنی از تا نصف تعداد ستونها جستجو کردیم و پیدا نشد دیگه پیدا نمی شه!

[iut.ali]

لازم نیست کل جدول جستجو بشه
مثلا در ستونها تا نصف ستونها لازم نیست جلو تر بریم یعنی از تا نصف تعداد ستونها جستجو کردیم و پیدا نشد دیگه پیدا نمی شه!
ولی باز هم باید برای نصف ستون ها تمام حالات رو در نظر گرفت یعنی هر ترکیب سه تایی از ستون اول رو باید با نصف ستون ها مقایسه کنیم اگه نبود سراغ ستون دوم بریم و همین روال ادامه پیدا میکنه. فک نکنم این مشکلو حل کنه

[rahnema1]

ولی باز هم باید برای نصف ستون ها تمام حالات رو در نظر گرفت یعنی هر ترکیب سه تایی از ستون اول رو باید با نصف ستون ها مقایسه کنیم اگه نبود سراغ ستون دوم بریم و همین روال ادامه پیدا میکنه. فک نکنم این مشکلو حل کنه

ترکیب خالی که نیست. ترتیب هم داره.
فکر نکنم ابعاد مساله چندان زیاد بشه

[iut.ali]

در مثال اول چرا 156 صفر شده ؟یا 39 ؟
مثلا واسه ۳۹.
39-4=35, 35-5=30, 30-30=0;

[iut.ali]

مثلا واسه ۳۹.
39-4=35, 35-5=30, 30-30=0;
شما بد ترین حالت رو در نظر بگیرید. فرض کنید یه ماتریس ۴*۴ داشته باشیم که االگو تو ستون اول و آخر فقط تکرار شده باشه الگو میتونه توی ستون اول سه حالت داشته باشه حالا این سه حالت باید توی تمام ستون ها تست بشه تا اینکه به ستون آخر برسیم و جواب رو پیدا کنیم که فک کنم ۴^۳ حالت یعنی ۸۱ حالت میشه اونم تو یه ماتریس ۴*۴

[rahnema1]

شما بد ترین حالت رو در نظر بگیرید. فرض کنید یه ماتریس ۴*۴ داشته باشیم که االگو تو ستون اول و آخر فقط تکرار شده باشه الگو میتونه توی ستون اول سه حالت داشته باشه حالا این سه حالت باید توی تمام ستون ها تست بشه تا اینکه به ستون آخر برسیم و جواب رو پیدا کنیم که فک کنم ۴^۳ حالت یعنی ۸۱ حالت میشه اونم تو یه ماتریس ۴*۴

در هر ستون 2 تا می شه
بعد هم چون فاصله بین ستونها باید یکسان باشه خود بخود تعدادی از رده خارج می شن که از این تعدادی که شما حساب کردید کمتر می شه. می خواستم برنامه اش را بنویسیم حوصله نکردم! چیز خاصی نداره

[iut.ali]

در هر ستون 2 تا می شه
بعد هم چون فاصله بین ستونها باید یکسان باشه خود بخود تعدادی از رده خارج می شن که از این تعدادی که شما حساب کردید کمتر می شه. می خواستم برنامه اش را بنویسیم حوصله نکردم! چیز خاصی نداره
همینقدر هم که کمکم کردید ممنونم بقیش رو خودم انجام میدم ولی نمیدونم چرا بازم به نظرم میاد که این در نظر گرفتن تمام حالت ها میشه بازم ممنون

[iut.ali]

مثلا اگه مثال اول رو در نظر بگیریم میبینیم که توی ستون اول ترتیب ۳ از ۶ حالت داریم خب حالا اگه بخوایم این حالت ها رو برای ستون های بعدی امتحان کنیم تا وقنی که به یه الگو برسیم که تناوب رو بمون بده تعداد حالات زیادی رو باید حساب کنیم. تو این مثال ۱۲۰ حالت میشه حالا این ۱۲۰ حالت رو باید با ستون بعدی مقایسه کرد که اگه حالت مثال اول رو در نظر بگیریم توی این ستون هم تناوب وجود نداره

[rahnema1]

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

[iut.ali]

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

[rahnema1]

آخه سوال را باز هم کامل مطرح نکردید !قسمت اولش را نمیگم منظورم قسمت دومشه. این جمله را در سوال جا انداخته بودید که وقتی سه عدد به دست اومد با هم جمع می شوند و اعداد دیگه ضریبی از از مجموع سه عدد هست که اصلا این را نگفته بودید احتمالا کسی که سوال را به شما داده به صورت شفاهی به شما توضیح داده یا فرصت نکرده کاملا مکتوب کنه
یک نکته دیگه اینکه امکانش هست در یک ستون اعداد تکراری هم باشند؟ یعنی ممکنه اون سه عددی که در نهایت پیدا می شن در هر ستون هر کدوم بیشتر از یکبار تکرار شده باشند؟
در هر صورت فکر می کنم تنها کار مهمی که برای این سوال می شه کرد اینه که یک لیست سیاه درست کنیم که هر عنصر شامل سه عدد به همراه فاصله سطری بین اونها هست
لیست سیاه برای این به کار می ره که اگه سه تا عدد را بررسی کردیم که شامل شرط ذکر شده نبودند جزء لیست سیاه قرار بگیرند که بعدا اگه با چنین سه عددی مواجه شدیم دیگه لازم نباشه جستجو کنیم
این لیست سیاه می تونه به صورت درخت یا یک map یا دیکشنری تودوتو پیاده سازی بشه
البته ممکنه بعضی بهینه سازی های دیگه هم اضافه کرد که به نظرم اولویت لیست سیاه، از اونها بیشتره

[iut.ali]

آخه سوال را باز هم کامل مطرح نکردید !قسمت اولش را نمیگم منظورم قسمت دومشه. این جمله را در سوال جا انداخته بودید که وقتی سه عدد به دست اومد با هم جمع می شوند و اعداد دیگه ضریبی از از مجموع سه عدد هست که اصلا این را نگفته بودید احتمالا کسی که سوال را به شما داده به صورت شفاهی به شما توضیح داده یا فرصت نکرده کاملا مکتوب کنه
یک نکته دیگه اینکه امکانش هست در یک ستون اعداد تکراری هم باشند؟ یعنی ممکنه اون سه عددی که در نهایت پیدا می شن در هر ستون هر کدوم بیشتر از یکبار تکرار شده باشند؟
در هر صورت فکر می کنم تنها کار مهمی که برای این سوال می شه کرد اینه که یک لیست سیاه درست کنیم که هر عنصر شامل سه عدد به همراه فاصله سطری بین اونها هست
لیست سیاه برای این به کار می ره که اگه سه تا عدد را بررسی کردیم که شامل شرط ذکر شده نبودند جزء لیست سیاه قرار بگیرند که بعدا اگه با چنین سه عددی مواجه شدیم دیگه لازم نباشه جستجو کنیم
این لیست سیاه می تونه به صورت درخت یا یک map یا دیکشنری تودوتو پیاده سازی بشه
البته ممکنه بعضی بهینه سازی های دیگه هم اضافه کرد که به نظرم اولویت لیست سیاه، از اونها بیشتره
راستش من متن سوال رو مستقیم گذاشتم اینجا. TA هم واسه حل سوال اشاره به درس هوش مصنوعی کرده بود با یه کم سرچ فهمیدم که یه درسی توی هوش مصنوعی هست به اسم pattern recognition که فک کنم واسه حل سوال من راهکاری داشته باشه ولی خب چیز زیادی پیدا نکردم. اگه کسی این درسو گذرونده ممنون میشم کمک کنه. قسمت دوم رو هم یکی از دوستان پرسیده بودن و جواب داده بودم که بقیه اعداد ضریبی از مجموع سه عدد هستن البته نه بطور شفاهی واسه همین عذر خواهی میکنم الگوریتمی که شما گفتید هم با یه کم سرچ فهمیدم که واسه حذف یه سری از حالت ها به کار میره که البته اون حالت ها رو باید از قبل داشته باشیم و با یه سرچ حذفشون کنیم که خب فک نکنم به درد من بخوره البته این چیزیه که من فهمیدم اگه میشه یه کم بیشتر توضیح بدید چون اگه من درست فهمیده باشم حالت هایی که چک میشن و اشتباهن رو دوباره تست نکنیم که اگه شما یه ماتریس 5*5 رو در نظر بگیرید و فرض کنیم که الگو توی ستون 1 و 3 قرار گرفته باشه باز هم باید تمام حالت ها تست بشه. در هر صورت ممنونم از جوابتون اگه کسی در مورد هوش مصنوعی و درس pattern recognition اطلاعاتی داره که منو به حل مسئله نزدیک کنه ممنون میشم جواب بدید...

[rahnema1]

بحث pattern recognition بیشتر مباحث آماری هست که در اینجا کاربردی نداره
برنامه زیر را در نظر بگیرید
مثلا می خواهیم شماره سطر و ستون عناصری از جدول که مقدارشون برابر با 3 هست با روس سریع پیدا کنیم که از multimap استفاده می کنیم
برای لیست سیاه هم می تونیم از set استفاده کنیم مثلا سه عدد 7 و 8 و 4 که شماره سطر اونها برابر با 0 و 2و 3 هست را داخل لیست سیاه می گذاریم توجه کنید شماره سطر اولین عنصر همیشه با صفر در نظر می گیریم و شماره سطر دو عنصر بعدی اختلاف شماره سطر آن عنصر با عنصر اول می باشد

#include <map>
#include <set>
#include <iostream>
using namespace std;
int main()
{
int mat[5][5] = {
{1, 7, 5, 6, 7},
{7, 6, 4, 2, 2},
{3, 8, 2, 5, 1},
{8, 4, 1, 3, 5},
{4, 9, 7, 1, 5},
};
multimap<int, pair<int, int>> dic;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
dic.insert(pair<int, pair<int, int>> ({mat[i][j], {i, j}}));

auto ret = dic.equal_range(3);
for(auto it = ret.first; it != ret.second; it++)
cout<< it->second.first << "," << it->second.second << endl;

// mesal black_list:
set<tuple<pair<int, int>, pair<int, int>, pair<int, int>>> black_list;
typedef tuple<pair<int, int>, pair<int, int>, pair<int, int>> black_list_element;
black_list.insert(black_list_element({7, 0},{8, 2},{4, 3}));
black_list.insert(black_list_element({5, 0},{2, 1},{7, 4}));
if ( black_list.find(black_list_element({7, 0},{8, 2},{4, 3})) != black_list.end())
cout << "dar set mojood ast!";
}