راهنمایی در مورد کد برنامه 8 وزیر به زبان Prolog - Artificial Intelligence

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

سلام به همه دوستان عزیز ، از دوستانی که به پرولوگ آشنایی کامل دارند میخواستم

نحوه عملکرد کد زیر رو توضیح دهند : (هریک از relation ها چه کاری انجام میدهند؟)

كد:

    queens(N, Qs) :-
         range(1, N, Ns),
         queens(Ns, [], Qs).

     queens(UnplacedQs, SafeQs, Qs) :-
         select(Q, UnplacedQs, UnplacedQs1),
         \+ attack(Q, SafeQs),
         queens(UnplacedQs1, [Q|SafeQs], Qs).
         queens([], Qs, Qs).

     attack(X, Xs) :- attack(X, 1, Xs).

     attack(X, N, [Y|_Ys]) :- X is Y + N.
     attack(X, N, [Y|_Ys]) :- X is Y - N.
     attack(X, N, [_Y|Ys]) :-
         N1 is N + 1,
         attack(X, N1, Ys).

     range(M, N, [M|Ns]) :-
         M < N,
         M1 is M + 1,
         range(M1, N, Ns).
     range(N, N, [N]).

     show_solution(Tcl, L) :-
         reverse(L, LR),
         tcl_eval(Tcl, [show_solution, br(LR)], _),
         tk_do_all_events.

     tk_do_all_events :-
         tk_do_one_event, !,
         tk_do_all_events.
     tk_do_all_events.

ممنون از راهنمایی شما . (دوستان هرچه سریعتر راهنمایی کنند ، ممنون میشم)

**alijy** · ۰۴-۱۲-۱۳۸۹, ۰۵:۲۳ بعد از ظهر

سلام

range/2 : عدد N رو میگیره و لیست [1,...,N] رو تولید میکنه.

queens/2 : تعداد وزیرها رو میگیره و راه حل مسئله رو تولید میکنه.

queens/3 : این predicate در واقع کار اصلی برنامه رو انجام میده. با گرفتن لیست [1,...,N] ، ازش به عنوان شماره ستون های جدول (نه شماره وزیر!) استفاده میکنه. این گزاره بصورت iteration و با فراخوانی مجدد خودش، در هر مرحله ستون محل قرار گیری وزیر هر سطر رو انتخاب (select)میکنه. سپس چک میکنه که وزیر جدید با وزیرهای انتخاب شده برای سطرهای قبل برخورد (attack) نداشته باشه. اگر این شرط برقرار باشه، شماره ستون به لیست راه حل (SafeQs) اضافه میشه. در غیر اینصورت هم ستون دیگه ای برای وزیر سطر کنونی انتخاب میشه. اگر هیچ ستون جدیدی که قابل قبول باشه پیدا نشه، آخرین گزاره queens/3 فراخوانی شده fail میشه و در نتیجه گزاره queens/3 قبلی که اون رو فراخوانی کرده بوده دوباره اجرا میشه و ستون جدیدی رو برای وزیر قبلی انتخاب میکنه. این برگشت تا جایی که بشه یه ستون جدید قابل قبول برای وزیر همون سطر انتخاب کرد ادامه پیدا میکنه و به محض انتخاب جدید برگشت متوقف شده و پیشروی دوباره ادامه پیدا میکنه. در نهایت هم وقتی لیست سطرها (وزیرها) خالی شد، لیست ستونهایی که به ترتیب برای سطرها (وزیرها) انتخاب شده به عنوان خروجی به queens/2 برمیگرده.

attack/2 : با فراخوانی گزاره کمکی attack/3 احتمال برخورد رو یک وزیر با وزرای قبلی رو چک میکنه.

attack/3 : این گزاره کمکی بصورت iteration و با فراخوانی مجدد خودش امکان برخورد وزیر جدید رو با تک تک وزرای قبلی چک میکنه. نکته مهم در مورد این predicate اینه که تک تک حالات برخورد ممکن تا جایی چک میشه که یه برخورد پیدا بشه. در غیر اینصورت attack/3 بعد از بررسی تمامی حالات ممکن fail میشه که مطلوب هست. برای بررسی حالات ممکن در هر مرحله آیتم اول لیست SafeQs (لیست ستونهای وزرای قبلی) انتخاب میشه. اولین انتخاب، شماره ستون وزیر سطر قبلی رو نشون میده. برای این شماره ستون چک میشه که وزیر جدید در ستون قبلی یا بعدی این ستون قرار میگیره یا نه. سپس سطر قبل تر (سطری که با سطر کنونی 2 تا فاصله داره. مثلا سطر 4 و سطر 6) از اون رو چک میکنه تا ببینه که ستون انتخاب شده برای سطر (وزیر) جدید (مثلا سطر 6) در دو ستون قبل یا 2 ستون بعد از ستون سطر چک شونده (مثلا سطر 4) قرار نگیره، و به همین ترتیب تا سطر 1 همه انتخابهای قبلی با انتخاب کنونی چک میشه. این نکته رو هم خوبه بگم که لازم نیست هم ستون بودن هیچ دو وزیری رو چک کنیم، چون در موقع انتخاب شماره ستون انتخاب شده برای هر وزیر از لیست امکان انتخاب برای وزرای بعدی حذف میشه.

** دو predicate آخر هم هیچ ربطی به برنامه N وزیر داده شده نداره و احتمالا مربوط به برنامه یا بخش دیگه از یه برنامه مفصل تر هست. ضمن اینکه برای tk_do_one_event هم هیچ تعریفی ارائه نشده و در واقع اجرای جداگانه tk_do_all_events در این برنامه همیشه با error همراهه.

امیدوارم که توضیحات مفهوم بوده باشه. اگر سؤالی در مورد قسمت بخصوصی از برنامه هست خوشحال میشم جواب بدم.

salar_cpp_cs · ۰۴-۱۲-۱۳۸۹, ۰۹:۲۹ بعد از ظهر

دوست عزیز ، alijy ، وقعا نمیدونم با چه زبونی ازتون تشکر کنم . خدا همیشه یار و یاورتون باشه .

سوالات من :

1- +\ چه معنایی داره ؟

2- رابطه show_solution چه جوری عمل میکنه ؟

**alijy** · ۰۴-۱۲-۱۳۸۹, ۰۹:۴۳ بعد از ظهر

1. +\ به صورت نفی عمل میکنه. این یعنی اینکه گزاره ای که این علامت جلوش باشه باید fail بشه تا کل اون خط از برنامه successful باشه. میتونیم بگیم این علامت معنی «وجود ندارد .... » باشه. در نتیجه در این برنامه هر موقع به این خط میرسه، attack/2 رو فراخوانی میکنه. اگر attack/2 موفقیت آمیز باشه یعنی اینکه یه برخورد وجود داشته، پس علامت +\ این رو نتیجه رو برعکس میکنه تا تبدیل به fail بشه و در نتیجه اون ستون انتخاب شده بعنوان ستونی که برخورد داره در نظر گرفته میشه و select دوباره اجرا میشه و یه ستون دیگه رو انتخاب میکنه. امیدوارم توضیحاتم روشن و واضح بوده باشه.

2. همونطوری که گفتم show_solution اصلا مربوط به برنامه N وزیر نیست و در هیچ جایی از برنامه استفاده نشده. شما میتونید show_solution و همینطور tk_do_all_events رو با خیال راحت حذف کنید و برنامه رو بدون هیچ مشکلی اجرا کنید.

اگر بازم سؤالی داشتید حتما بپرسید.

batman2013 · ۰۲-۱۶-۱۳۹۲, ۱۰:۰۴ بعد از ظهر

سلام به همه عزیزان ، از دوستانی که به پرولوگ آشنایی کامل دارند میخواستم

نحوه عملکرد کد زیر رو توضیح دهند : (خط به خط چی کار می کند ؟) خواهشن سریع جواب بدین همین کد رو باید برای استاد توضیح بدم

/* queens(N,Queens) :-
Queens is a placement that solves the N queens problem,
Represented as a permutation of the list of numbers [1,2,…,N]. */
queens(N,Qs) :- range(1,N,Ns), permutation(Ns,Qs), safe(Qs).
/* safe(Qs) :- the placement Qs is safe. */
safe([Q|Qs]) :- safe(Qs), not attack(Q,Qs).
safe([]).
attack(X,Xs) :- attack (X,1,Xs).
attack(X,N,[Y|Ys]) :- X is Y+N ; X is Y-N.
attack (X
permutation(Xs,[Z|Zs]) :- select(Z,Xs,Ys), permutation(Ys,Zs).
permutation([],[]).
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :- select(X,Ys,Zs).
range(M,N,[M|Ns]) :- M < N, M1 is M+1, range(M1,N,Ns).
range(N,N,[N]).