الگوریتم مسئله Knight Cover با BFS [بایگانی]

sa1378

چهارشنبه 19 آذر 1393, 16:12 عصر

سلام
من متن usaco که درباره الگوریتم این مسئله بود رو متوجه نشدم
گفته که میایم اول یه خونه رو به صف اضافه میکنیم و تا وقتی که صف خالی نشده خونه های بعدیش(next state) رو اضافه میکنیم و برای اونا هم همین کارو انجام میدیم...
منظور از این خونه های بعدی چیه؟
اینم متنشه:http://paste.ubuntu.com/9456301/

omid_kma

چهارشنبه 19 آذر 1393, 20:06 عصر

BFS میاد هر مرحله راس های مجاور یک راس رو به آخر Queue اضافه می کنه.
منظورش از next states همون راس های مجاور هست که بستگی به مسئله داره
مثلا برای همین سوال همون طوری که توضیح داده next states میشه حالتی که یک knight بیشتر داره
یعنی این جا به این شکل BFS انجام میشه :
اول یک knight اضافه می کنیم بعد next states میشه همه ی حالت هایی که میشه یک knight دیگه اضافه کرد همه این حالت ها رو به صف اضافه می کنیم. بعد یک state از اول صف بر می داریم واین کارو تا رسیدن به Goal تکرار می کنیم (که goal این جا همون مورد حمله قرار گرفتن همه خونه هاست )

sa1378

چهارشنبه 19 آذر 1393, 20:47 عصر

BFS میاد هر مرحله راس های مجاور یک راس رو به آخر Queue اضافه می کنه.
منظورش از next states همون راس های مجاور هست که بستگی به مسئله داره
مثلا برای همین سوال همون طوری که توضیح داده next states میشه حالتی که یک knight بیشتر داره
یعنی این جا به این شکل BFS انجام میشه :
اول یک knight اضافه می کنیم بعد next states میشه همه ی حالت هایی که میشه یک knight دیگه اضافه کرد همه این حالت ها رو به صف اضافه می کنیم. بعد یک state از اول صف بر می داریم واین کارو تا رسیدن به Goal تکرار می کنیم (که goal این جا همون مورد حمله قرار گرفتن همه خونه هاست )
یعنی در هر مرحله باید به ازای همه خونه ها انجام بدیم اینو؟
هر مرحله هم باید همه خونه هارو چک کنیم؟
اینجوری که اوردرش نجومیه

omid_kma

چهارشنبه 19 آذر 1393, 23:13 عصر

یعنی در هر مرحله باید به ازای همه خونه ها انجام بدیم اینو؟ هر مرحله هم باید همه خونه هارو چک کنیم؟
آره همین طوره

اینجوری که اوردرش نجومیه
آره اصولا هم این جور مسئله ها رو الگوریتم های دیگه ای مثل *A یا hell climbing حل می کنن نه BFS چون BFS علاوه بر کند بودن حافظه فوق العاده زیادی مصرف می کنه و عملا برای n های بزرگ غیر قابل استفادست .
این الگوریتم هم آره اگر قرار بود پیمایش تا آخر ادامه پیدا بکنه خیلی نجومی بود و اوردر هم میشه n^2 فاکتوریل
ولی این جا چون هر اسب که میزاریم بین 2 تا 8 تا خونه رو پوشش میده تعداد حداقل اسب های مورد نیاز کوچیکه و سریع به جواب میرسیم .