請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/81093完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Feng-Ming Chang | en |
| dc.contributor.author | 張峯銘 | zh_TW |
| dc.date.accessioned | 2022-11-24T03:30:12Z | - |
| dc.date.available | 2021-09-17 | |
| dc.date.available | 2022-11-24T03:30:12Z | - |
| dc.date.copyright | 2021-09-17 | |
| dc.date.issued | 2021 | |
| dc.date.submitted | 2021-08-23 | |
| dc.identifier.citation | [1] M. Dorigo and G. Di Caro, Ant colony optimization: a new metaheuristic, in Proceedings of the 1999 Congress on Evolutionary Computation (CEC), pp. 1470–1477, 1999. [2] M. Dorigo and L. M. Gambardella, Ant colony system: a cooperative learning approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, pp. 53–66, 1997. [3] Huw Lloyd, Martyn Amos, Solving sudoku with ant colony optimization, IEEE Transactions on games, pp. 302–311, 2020 [4] James Kennedy, Russell Eberhart, Particle swarm optimization, in Proceedings of the IEEE international conference on neural networks IV, pp. 1942–1948, 1995 [5] Alberto Moraglio, Julian Togelius, Geometric Particle Swarm Optimization for the Sudoku Puzzle, Genetic and Evolutionary Computation Conference, pp. 118–125, 2007 [6] Muzaffar Eusuff, Kevin Lansey, and Fayzul Pasha, Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Engineering Optimization, pp. 129– 154, 2006. [7] P. Norvig, Solving every sudoku puzzle. Available at http://norvig.com/sudoku.html, accessed March 13, 2018. [8] Xue-hui Luo, Ye Yang, Xia Li, Solving TSP with shuffled frog-leaping algorithm. Eighth International Conference on Intelligent Systems Design and Applications, pp. 228–232, 2008 [9] I. Sabuncu, Work-in-progress: solving sudoku puzzles using hybrid ant colony optimization algorithm, in 1st International Conference on Industrial Networks and Intelligent Systems (INISCom), pp. 181–184, 2015. [10] M. Ercsey-Ravasz and Z. Toroczkai, The chaos within sudoku, Sci. Rep., pp. 725– 733, 2012. [11] A. Inkala, AI Escargot - the most difficult sudoku puzzle. Lulu.com, Finland, 2007. [12] R. Lewis, Metaheuristics can solve sudoku puzzles, Journal of Heuristics, pp. 387–401, 2007. [13] N. Musliu and F. Winter, A hybrid approach for the sudoku problem: using constraint programming in iterated local search, IEEE Intelligent Systems, pp. 52–62, 2017. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/81093 | - |
| dc.description.abstract | 數獨是一個自2004年以來非常受歡迎的一個解謎遊戲，時常能在各大報紙上發現數獨題目的蹤跡，隨著智慧型手機和網路的普及，更多人了解數獨這個遊戲，也衍生出了不同的解法。本篇論文提出運用跳蛙演算法來解數獨題目，利用啟發示算法來產生數獨的正確答案，將每個尚未解完的數獨盤面當作一隻青蛙，依照尚未填入的格子數排序完後分配到若干個迷因複合體，每個迷因複合體演化後再重新排序一次，重複上述動作直到產生出正確答案為止，而本篇論文除了用常見的9x9大小的數獨題目來討論外，也引用較難的16x16和25x25大小的數獨盤面，和其他的啟發示演算法來比較效能。 | zh_TW |
| dc.description.provenance | Made available in DSpace on 2022-11-24T03:30:12Z (GMT). No. of bitstreams: 1 U0001-1808202122281000.pdf: 710277 bytes, checksum: b3353c9c6a98a8205a4d6d8c80c0deda (MD5) Previous issue date: 2021 | en |
| dc.description.tableofcontents | 口試委員會審定書 iii 誌謝 v 摘要 vii Abstract ix 1 Introduction 1 2 Heuristic algorithm for sudoku 3 2.1 Ant colony optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Particle swarm optimization . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Shuffled frog-leaping algorithm 7 4 Experiments 15 4.1 Experimental environment . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Logic-solvable 9x9 instances . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 General instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5 Conclution and the future work 21 Bibliography 23 | |
| dc.language.iso | en | |
| dc.subject | 元啟發算法 | zh_TW |
| dc.subject | 跳蛙演算法 | zh_TW |
| dc.subject | 數獨 | zh_TW |
| dc.subject | 解謎遊戲 | zh_TW |
| dc.subject | 迷因演算法 | zh_TW |
| dc.subject | Memetic algorithm | en |
| dc.subject | Meta-heuristic | en |
| dc.subject | Shuffled frog-leaping algorithm | en |
| dc.subject | Sudoku | en |
| dc.subject | Puzzle Games | en |
| dc.title | 利用跳蛙演算法解數獨問題 | zh_TW |
| dc.title | Solving sudoku with shuffled frog-leaping algorithm | en |
| dc.date.schoolyear | 109-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王弘倫(Hsin-Tsai Liu),吳彥緯(Chih-Yang Tseng) | |
| dc.subject.keyword | 跳蛙演算法,數獨,解謎遊戲,迷因演算法,元啟發算法, | zh_TW |
| dc.subject.keyword | Shuffled frog-leaping algorithm,Sudoku,Puzzle Games,Memetic algorithm,Meta-heuristic, | en |
| dc.relation.page | 24 | |
| dc.identifier.doi | 10.6342/NTU202102495 | |
| dc.rights.note | 同意授權(限校園內公開) | |
| dc.date.accepted | 2021-08-24 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-1808202122281000.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 693.63 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。