กฎของวานดอล์ฟ (อังกฤษ: Warnsdorff's rule) เป็นวิธีการแบบฮิวริสติกสำหรับการหาวิธีการเดินม้าหมากรุก กล่าวโดยสรุปคือในการเดินม้าแต่ละครั้งนั้นจะต้องเป็นไปตามกฎ กล่าวคือ กำหนดให้ ในทุกช่องที่สามารถเดินไปจากช่องปัจจุบัน(ซึ่งไม่นับรวมถึงช่องที่เคยเดินผ่านไปแล้ว) จะมีค่าเท่ากับจำนวนช่องที่ช่องดังกล่าวสามารถเดินต่อไปได้ตามกฎของการเดินม้าหมากรุก(ซึ่งไม่นับรวมถึงช่องที่เคยเดินผ่านไปแล้ว) การเลือกช่องต่อไปสำหรับการเดินม้าจะพิจารณาเลือกช่องที่มีค่าน้อยที่สุด ซึ่งหากมีหลายช่องที่มีค่าน้อยที่สุดเท่ากันก็อาจมีทางเลือกได้หลายทาง นอกจากกลวิธีดังกล่าวในการแก้ปัญหานี้ยังมีกลวิธีอื่นๆอีกหลายหลายวิธี เช่น กลวิธีของโพ และกลวิธีของสไควเออร์และคูล โดยทั่วไปกฎของวานส์ดอล์ฟ จะนำไปประยุกต์ใช้กับเรื่องกราฟได้ ในเรื่องของทฤษฎีกราฟ การเดินม้าหมากรุกแต่ละครั้ง จะเดินไปยังปมที่อยู่ติดกันด้วยดีกรีที่น้อยที่สุด ถึงแม้ว่าปัญหาทางเดินของแฮมิลตันจะจัดอยู่ในเรื่องของกลุ่มปัญหาเอ็นพีแบบยาก โดยปกติแล้วในการใช้วิธีการแบบฮิวริสติกในหลายๆกราฟสามารถแก้ปัญหาได้ด้วยอัตราการเติบโตแบบเชิงเส้น แต่สำหรับปัญหาทางเดินม้าหมากรุกนี้จัดเปนกรณีพิเศษ
รูปภาพตาราง แสดงวิธีการเดินม้าหมากรุกตามกฎของวานส์ดอล์ฟ
กฎของวานดอล์ฟสามารถใช้ได้กับจุดเริ่มต้นที่ช่องใดก็ได้ของตารางหมากรุก จำนวนครั้งที่เดินได้ก็คือจำนวนตัวเลขที่บรรจุในแต่ละช่อง ซึ่งตามกฎแล้ว จะต้องเดินไปยังช่องที่มีตัวเลขน้อยที่สุดนั่นเอง จากนั้นก็เลือกเดินตามกฎต่อไปจนกว่าจะเดินได้ครบทุกช่อง
- ข้อตกลง
- ตำแหน่ง Q จะเข้าถึงจากตัวแหน่ง P ได้ ถ้าหากว่า P สามารถเคลื่อนที่ไปยัง Q ได้ด้วยการเคลื่อนที่เพียงครั้งเดียว และ Q ยังเป็นตำแหน่งที่ยังไม่ได้เยี่ยม
- ความสามารถในการเข้าถึงตำแหน่ง P เท่ากับ จำนวนของตำแหน่งที่สามารถเข้าถึงได้จากตำแหน่ง P
- ขั้นตอนวิธี
- กำหนดให้ P เป็นจำแหน่งเริ่มต้นของการเดินม้าหมากรุก โดยเลือกจุดเริ่มต้นนี้แบบสุ่ม
- กำหนดให้จุดเริ่มต้นมีเลขกำกับการเคลื่อนที่เป็น 1
- สำหรับทุกการเคลื่อนที่ที่มีเลขกำกับการเคลื่อนที่เป็น 2 ขึ้นไป
- กำหนดให้ S เป็นตำแหน่งที่เข้าถึงได้จากตำแหน่งที่ส่งเข้าไป
- กำหนดตำแหน่ง P ให้เป็นตำแหน่ง ที่ตำแหน่ง S มีความสามารถที่จะการเข้าถึงได้น้อยที่สุด
- ทำเครื่องหมายแสดงเลขกำกับการเคลื่อนที่บนตำแหน่ง P
- คืนค่าตารางหมากรุกที่ได้รับการทำเครื่องหมายแล้ว โดยแต่ละช่องจะถูกทำเครื่องหมายด้วยเลขกำกับการเคลื่อนที่ที่มันถูกเยี่ยม
ตัวอย่างโปรแกรมในภาษาซีเพิ่มเติม กฎของวานดอล, บทความน, หร, อส, วนน, ของบทความต, องการปร, บร, ปแบบ, งอาจหมายถ, องการจ, ดร, ปแบบข, อความ, ดหน, แบ, งห, วข, ดล, งก, ภายใน, และ, หร, อการจ, ดระเบ, ยบอ, ณสามารถช, วยแก, ไขป, ญหาน, ได, โดยการกดท, แก, ไข, านบน, จากน, นปร, บปร, งหร, อจ, ดร, ปแบบอ, ในบทค. bthkhwamnihruxswnnikhxngbthkhwamtxngkarprbrupaebb sungxachmaythung txngkarcdrupaebbkhxkhwam cdhna aebnghwkhx cdlingkphayin aela hruxkarcdraebiybxun khunsamarthchwyaekikhpyhaniidodykarkdthipum aekikh danbn caknnprbprunghruxcdrupaebbxun inbthkhwamihehmaasmkdkhxngwandxlf xngkvs Warnsdorff s rule epnwithikaraebbhiwristiksahrbkarhawithikaredinmahmakruk klawodysrupkhuxinkaredinmaaetlakhrngnncatxngepniptamkd klawkhux kahndih inthukchxngthisamarthedinipcakchxngpccubn sungimnbrwmthungchxngthiekhyedinphanipaelw camikhaethakbcanwnchxngthichxngdngklawsamarthedintxipidtamkdkhxngkaredinmahmakruk sungimnbrwmthungchxngthiekhyedinphanipaelw kareluxkchxngtxipsahrbkaredinmacaphicarnaeluxkchxngthimikhanxythisud sunghakmihlaychxngthimikhanxythisudethaknkxacmithangeluxkidhlaythang nxkcakklwithidngklawinkaraekpyhaniyngmiklwithixunxikhlayhlaywithi echn klwithikhxngoph aelaklwithikhxngsikhwexxraelakhul odythwipkdkhxngwansdxlf canaipprayuktichkberuxngkrafid ineruxngkhxngthvsdikraf karedinmahmakrukaetlakhrng caedinipyngpmthixyutidkndwydikrithinxythisud thungaemwapyhathangedinkhxngaehmiltncacdxyuineruxngkhxngklumpyhaexnphiaebbyak odypktiaelwinkarichwithikaraebbhiwristikinhlaykrafsamarthaekpyhaiddwyxtrakaretibotaebbechingesn aetsahrbpyhathangedinmahmakruknicdepnkrniphiessrupphaphtarang aesdngwithikaredinmahmakruktamkdkhxngwansdxlfwithidaeninkarephuxprayuktkbkddngklaw aekikhkdkhxngwandxlfsamarthichidkbcuderimtnthichxngidkidkhxngtaranghmakruk canwnkhrngthiedinidkkhuxcanwntwelkhthibrrcuinaetlachxng sungtamkdaelw catxngedinipyngchxngthimitwelkhnxythisudnnexng caknnkeluxkedintamkdtxipcnkwacaedinidkhrbthukchxng khxtklngtaaehnng Q caekhathungcaktwaehnng P id thahakwa P samarthekhluxnthiipyng Q iddwykarekhluxnthiephiyngkhrngediyw aela Q yngepntaaehnngthiyngimideyiym khwamsamarthinkarekhathungtaaehnng P ethakb canwnkhxngtaaehnngthisamarthekhathungidcaktaaehnng Pkhntxnwithikahndih P epncaaehnngerimtnkhxngkaredinmahmakruk odyeluxkcuderimtnniaebbsum kahndihcuderimtnmielkhkakbkarekhluxnthiepn 1 sahrbthukkarekhluxnthithimielkhkakbkarekhluxnthiepn 2 khunip kahndih S epntaaehnngthiekhathungidcaktaaehnngthisngekhaip kahndtaaehnng P ihepntaaehnng thitaaehnng S mikhwamsamarththicakarekhathungidnxythisud thaekhruxnghmayaesdngelkhkakbkarekhluxnthibntaaehnng P khunkhataranghmakrukthiidrbkarthaekhruxnghmayaelw odyaetlachxngcathukthaekhruxnghmaydwyelkhkakbkarekhluxnthithimnthukeyiymtwxyangopraekrminphasasi aekikhhttps web archive org web 20110912213543 http chinmaylokesh wordpress com 2011 06 20 knights tour using warnsdorffs algorithm a heuristic approach ephimetim aekikhhttp www wou edu broegb Cs345 KnightTour pdf Archived 2015 09 20 thi ewyaebkaemchchin ekhathungcak https th wikipedia org w index php title kdkhxngwandxlf amp oldid 10031219, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
