سفر اسب

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
سفر اسب در صفحهٔ شطرنج
سفر اسب در یک صفحهٔ ۵×۵

سفر اسب به دنباله‌ای از حرکات یک مهرهٔ اسب در یک صفحهٔ شطرنج گفته می‌شود به طوری که از هر خانه دقیقاً یک بار بگذرد. اگر اسب به خانه‌ای برسد که از ابتدای سفر از آن گذشته‌است، سفر بسته است. در غیر این صورت، سفر باز است. تعداد دقیق سفرها در یک صفحهٔ شطرنج ۸×۸ هنوز مشخص نیست.

مسألهٔ سفر اسب یک مسألهٔ ریاضیات شطرنجی برای پیدا کردن یک سفر اسب است. ساخت یک برنامه برای پیدا کردن یک سفر اسب یک مسألهٔ رایج برای دانشجویان علوم کامپیوتر است.[۱] انواع مختلف مسألهٔ سفر اسب به خاطر تفاوت در اندازهٔ صفحه‌های شطرنج و هم‌چنین صفحه‌های غیرمربعی است.

نظریه[ویرایش]

گراف اسب تمام مسیرهای ممکن برای یک سفر اسب را در یک صفحهٔ شطرنج استاندارد ۸×۸ نشان می‌دهد. عددهای هر رأس بیان‌گر تعداد حرکات ممکن که می‌توانند از آن رأس شروع شوند هستند.

مسألهٔ سفر اسب نمونه‌ای از مسألهٔ کلّی‌تر مسیر همیلتونی در نظریهٔ گراف است. مشابهاً، مسألهٔ پیدا کردن یک سفر بسته برای اسب، یک نمونه از مسألهٔ دور همیلتونی است. برخلاف مسألهٔ مسیر همیلتونی، مسألهٔ سفر اسب می‌تواند در زمان خطی حل شود.[۲]

تعداد سفرهای بسته[ویرایش]

در یک صفحهٔ ۸×۸، دقیقاً ۲۶,۵۳۴,۷۲۸,۸۲۱,۰۶۴ سفر بستهٔ جهت‌دار وجود دارد. (برای مثال دو سفر در طول مسیر یکسان که دارای جهت‌های مخالف هستند جداگانه شمارش می‌شوند، چرخش‌ها و تقارن‌ها هم به همین صورت هستند.)[۳][۴][۵] تعداد سفرهای بستهٔ غیرجهت‌دار نصف این عدد است زیرا هر سفر می‌تواند در جهت عکس نیز به‌حساب‌بیاید. ۹,۸۶۲ سفر بستهٔ غیرجهت‌دار در یک صفحهٔ ۶×۶ وجود دارد.[۶]

کدام صفحه‌ها دارای سفر هستند[ویرایش]

چْوِنْک[۷] ثابت کرد برای هر صفحهٔ m×n که در آن m کم‌تر یا مساوی n است، یک سفر بستهٔ اسب همیشه وجود دارد مگر این که حداقل یکی از این شروط برقرار باشند:

  1. m و n هر دو فرد باشند. n مساوی ۱ نباشد.
  2. m = ۱، ۲ یا ۴. n مساوی ۱ نباشد.
  3. m = ۳ و n = ۴، ۶ یا ۸.

کول و د کورتینز اثبات کردند در هر صفحهٔ مربعی که کوچک‌ترین بعد آن حداقل ۵ باشد، یک سفر (احتمالاً باز) اسب وجود دارد.[۸]

پیدا کردن سفرها با کامپیوتر[ویرایش]

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

الگوریتم‌های جامع[ویرایش]

یک جستجوی جامع برای یک سفر اسب برای تمامی صفحه‌ها غیر از صفحه‌های کوچک غیرعملی است. برای مثال، در یک صفحهٔ ۸x۸ تقریباً ۴x۱۰۵۱ دنبالهٔ حرکت ممکن وجود دارد[۹] و انجام عملیات روی چنین مجموعهٔ بزرگی فرای ظرفیت کامپیوترهای امروزی (یا شبکه‌هایی از کامپیوترها) است.

الگوریتم‌های تقسیم و حل[ویرایش]

با تقسیم صفحه به قسمت‌های کوچک‌تر، ساخت سفر در هر قسمت و وصل کردن قسمت‌ها به یکدیگر، می‌توان در بیش‌تر صفحه‌های مربعی در زمان چندجمله‌ای سفرها را پیدا کرد.[۱۰][۱۱]

راه حل شبکه‌های شبکه عصبی[ویرایش]

مسألهٔ سفر اسب با یک شبکهٔ عصبی نیز قابل حل است.[۱۲] شبکه به صورتی ساخته می‌شود که هر حرکت مجاز اسب با یک نرون نمایش داده‌می‌شود، و به هر نرون به صورت تصادفی مقدار اولیهٔ «فعال» یا «غیرفعال» (خروجی ۱ یا ۰) داده می‌شود، که ۱ نشان‌دهندهٔ این است که نرون قسمتی از راه حل نهایی است. هر نرون یک تابع وضعیت نیز دارد (در زیر توضیح داده شده) که مقدار اولیهٔ ۰ را دارد.

وقتی شبکه اجازهٔ اجرا دارد، طبق قوانین گذار مرحله زیر، هر نرون می‌تواند وضعیت خودش، خروجی بسته به خروجی‌های خودش و همسایه‌هایش را تغییر دهد (آن‌هایی که دقیقاً به اندازهٔ یک حرکت با اسب فاصله دارند).


U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - \sum_{N \in G(N_{i,j})} V_t(N)

V_{t+1} (N_{i,j}) = \left\{
\begin{array}{ll}
1 & \mbox{if}\,\, U_{t+1}(N_{i,j})> 3\\
0 & \mbox{if}\,\, U_{t+1}(N_{i,j}) <0\\
V_t(N_{i,j}) & \mbox{otherwise},
\end{array} \right.

که t نشان‌دهندهٔ وقفه‌های مجزای زمان، U(N_{i,j}) وضعیت نرونی که خانهٔ i را به خانهٔ j وصل می‌کند، V(N_{i,j}) خروجی نرونِ از i تا j و G(N_{i,j}) مجموعه‌ای از همسایه‌های نرون است.

گرچه ممکن است سری واگرا باشد، اما شبکه باید در نهایت همگرا شود که این هنگامی رخ می‌دهد که هیچ نرونی وضعیتش را از زمان t تا t+1 تغییر ندهد. هنگامی که شبکه همگرا می‌شود، شبکه یا یک سفر اسب یا یک سری از دو یا بیش‌تر از دورهای مستقل در همان صفحه را رمز می‌کند.

قانون وارنزدروف[ویرایش]

Solid white.svg a b c d e f g h Solid white.svg
8  black king  black king  black king  black king  black king  black king  black king  black king 8
7  black king  black king  black king  black king  black king  black king  black king  black king 7
6  three  black king  seven  black king  black king  black king  black king  black king 6
5  black king  black king  black king  seven  black king  black king  black king  black king 5
4  black king  white knight  black king  black king  black king  black king  black king  black king 4
3  black king  black king  black king  seven  black king  black king  black king  black king 3
2  two  black king  five  black king  black king  black king  black king  black king 2
1  black king  black king  black king  black king  black king  black king  black king  black king 1
Solid white.svg a b c d e f g h Solid white.svg
یک نمایش از قانون وارنزدروف. هر خانه حاوی یک عدد صحیح است که بیان‌گر تعداد حرکاتی است که اسب می‌تواند از ان خانه انجام دهد. در این صورت، قانون به ما می‌گوید به خانه‌ای برویم که کوچک‌ترین عدد صحیح در آن قرار دارد، یعنی ۲.

قانون وارنزدروف یک شیوهٔ ابتکاری برای پیدا کردن یک سفر اسب است. ما اسب را طوری حرکت می‌دهیم که همیشه به خانه‌ای برسم که طی آن مسیر اسب «کم‌ترین» حرکات رو به جلو را داشته باشد. هنگام محاسبهٔ تعداد حرکات رو به جلو برای هر خانهٔ موردنظر، حرکت‌هایی را که خانه‌های قبلاً پیموده‌شده‌اند را می‌پیمایند، نمی‌شماریم. هنگامی که تعداد حرکت‌های رو به جلو برابر است، ممکن است بیش‌تر از یک انتخاب داشته‌باشیم؛ روش‌های گوناگونی برای انتخاب مسیر مناسب وجود دارد. از جملهٔ آن‌ها می‌توان به روشی که توسط پل [۱۳] و روشی دیگر که به وسیلهٔ اسکیرل و کول [۱۴] ابداع شد اشاره کرد.

این قانون همچنین ممکن است به طور کلّی برای هر گرافی به کار رود. در ... هر حرکت به رأس مجاور با کم‌ترین درجه (گراف) انجام می‌شود. گرچه مسألهٔ مسیر همیلتونی به طور کلّی ان‌پی سخت است، امّا در بسیاری از گراف‌ها این شیوهٔ ابتکاری قادر است یک راه حل در زمان خطی پیدا کند.[۱۳] سفر اسب یک مورد خاص است.[۱۵]

منابع[ویرایش]

  1. H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326–328. 2003.
  2. Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics 50 (2): 125–134. DOI:10.1016/0166-218X(92)00170-Q. 
  3. Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics 3 (1): R5.  Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532 and this number is repeated in Wegener's 2000 book.
  4. Brendan McKay (1997). "Knight's Tours on an 8x8 Chessboard". Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 
  5. Wegener, I. (2000). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3. 
  6. Eric W. Weisstein, Knight's Tour at MathWorld.
  7. Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight’s Tour?". Mathematics Magazine: 325–332. 
  8. Cull, Paul. "Knight's Tour Revisited". Fibonacci Quarterly. Retrieved 5 August 2012. 
  9. "Enumerating the Knight's Tour". 
  10. Cull, P.; DeCurtins, J. (June 1978). "Knight's Tour Revisited". Fibonacci Quarterly 16: 276–285. 
  11. Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem". Discrete Applied Mathematics 73: 251–260. DOI:10.1016/S0166-218X(96)00010-8. 
  12. Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.
  13. ۱۳٫۰ ۱۳٫۱ Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM 10 (7): 446–449. DOI:10.1145/363427.363463. 
  14. Squirrel, Douglas; Cull, P. (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards". Retrieved 2011-08-21. 
  15. Alwan, Karla; Waters, K. (1992). "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF). ACM Southeast Regional Conference. New York, New York: ACM. pp. 377–382. DOI:10.1145/503720.503806. Retrieved 2008-10-28. 

پیوند به بیرون[ویرایش]

جستجو در ویکی‌انبار در ویکی‌انبار پرونده‌هایی دربارهٔ سفر اسب موجود است.

پیاده‌سازی‌ها[ویرایش]