Pegboard Solver
该程序是2020年秋季在Old Dominion University的CS 580 – 人工智能导论课程的作业。
Old Dominion University during the Fall 2020 semester.
该程序使用搜索算法解决各种尺寸（4×4 至 8×8）的Pegboard谜题
包括
- 广度优先搜索
- 深度优先搜索
- 贪婪最佳优先搜索
- A*搜索
执行
该程序最初是用Python编写的，现已重写为Dart；其SDK可以在此安装。此外，该程序通过执行以下命令在命令行中运行
here. Additionally, the program is run in the command-line
by executing the following command
可执行文件位于 bin 目录中。
# Unix-based
./solver [argument]
# Windows
solver.exe [argument]
以下参数是有效的，并且不区分大小写
| 参数 | 搜索算法 |
|---|---|
breadth |
广度优先搜索 |
depth |
深度优先搜索 |
greedy |
贪婪最佳优先搜索 |
a_star |
A*搜索 |
此外，可以使用--help标志作为参数来显示搜索算法列表。
algorithms.
报告
注意：对于较大的Pegboard，时间差异很大。为了节省时间，我选择了
快速解决方案；通常需要更长的时间。4×4的Pegboard与结果一致，但
consistant with the results however.
广度优先搜索
在所有搜索算法中，广度优先搜索耗时最长，因为它是一代一代地在展开树上工作的。
generation by generation.
Source: https://en.wikipedia.org/wiki/Breadth-first_search
这导致在用于4×4以上的Pegboard时，找到解决方案需要相当长的时间。
on pegboards with dimensions above 4×4. When running the algorithm on 4×4 pegboards,
solutions were found after 1869 unique states and either 1686 or 2114 if there
were none.
4×4 Solution
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
-- Goal State found --
Unique states explored: 1869
Total search time: 0:00:00.308898
深度优先搜索
深度优先搜索是沿着展开树，从左到右进行搜索。与广度优先搜索相比，这在内存使用上更有效率。
chance to make the search mroe memory efficient when compared to Breadth First. However,
if the solution is not found or is farther right in the fringe, the benefits are lost.
When running this search algorithm against the pegboards, I found that solutions were
found much faster than Breadth First search. When a solution was found, usually under
100 unique states were visited. Another finding to note is that solutions for larger
pegboards were more realistic to achieve.
4×4 Solution
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
-- Goal State found --
Unique states explored: 37
Total search time: 0:00:00.018837
5×5 Solution
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
-- Goal State found --
Unique states explored: 45711
Total search time: 0:00:46.585281
6×6 Solution
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
-- Goal State found --
Unique states explored: 575
Total search time: 0:00:00.171659
贪婪最佳优先搜索
贪婪最佳优先搜索是在深度优先搜索的基础上加入了可接受的启发式函数。启发式函数
allows for pegboards that appear more “promising” to be selected over others, resulting in
a solution being found quicker in some cases. Heuristics do not guarentee an optimal path
is being taken.
For this program, Manhatten Distance is
used as a heuristic. This heuristic was selected as it is more likely for a solution to be
obtained when pegs are more towards the center.
4×4 Solution
0 0 0 0
0 0 0 1
0 0 0 0
0 0 0 0
-- Goal State found --
Unique states explored: 21
Total search time: 0:00:00.019271
4×4 Solution
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
-- Goal State found --
Unique states explored: 15
Total search time: 0:00:00.018762
5×5 Solution
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
-- Goal State found --
Unique states explored: 711
Total search time: 0:00:00.167668
6×6 Solution
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
-- Goal State found --
Unique states explored: 3257
Total search time: 0:00:00.857798
A*搜索
A* search extends Greedy Best First
search by applying path cost alongside the heuristic, Manhatten Distance. In the case
of pegboards, states with less moves are generally favored, allowing for the optimal path
to be much more likely be found. In smaller boards, such as 4×4, the effects of the
algorithm were not really noticable; however, it becomes effective in the other dimensions.
4×4 Solution
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
-- Goal State found --
Unique states explored: 18
Total search time: 0:00:00.053961
4×4 Solution
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
-- Goal State found --
Unique states explored: 15
Total search time: 0:00:00.016254
5×5 Solution
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-- Goal State found --
Unique states explored: 1116
Total search time: 0:00:00.088612
6×6 Solution
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
-- Goal State found --
Unique states explored: 46367
Total search time: 0:00:49.095035
