Artificial intelligence experiment report
Experimental picture search strategy
1. Experimental purpose
1. Deepen the understanding of various graph search strategies
2. Further understand the heuristic search
3. Compare the difference between various search strategies
II. Experimental content and steps
Searching for a variety of search strategies (including brevity search, depth priority search, deep-priority search, best search, pre-sector search, pre-sexy search, preferred search strategy, etc., requires programs to have certain generals Sex, the focus is to clear the algorithm described.
IV. Rearrange the definition of the nine uterus issues
Place 8 sets of 1, 2, 3, 4, 5, 6, 7, and 8, left a space (represented by 0) on a 3 × 3 checkered checkerboard.
It is specified that the cards adjacent to the empty upper left and right can be moved into spaces. The problem is required to find a mobile phone movement from a initial state S0 to the target status SG.
route.
5. I have a description of the problem
Node status
I use a 10-yuan array A = (A0, A1, A2, A3, A4, A5, A6, A7, A8, A9) to describe every state of the nine palace map. The nine plaids of the Jiuguan map were numbered 1, 2, 3, 4, 5, 6, 7, 8, 9. The A0 representative space in the array is located in the lattice of the nine palace. A1-A9 nine elements represent what will be on nine plaids. For example, arrays (5, 2, 8, 3, 1, 0, 4, 7, 6, 5) represent the following state:
2 8 3
1 4
7 6 5
This representation is slightly different from the book, and I personally think that this will make it easy to program.
2. Generator function
I defined the generator function consisting of the following four operations:
(1) Move the space on the current state
(2) Move the space of the current state
(3) Left the space of the current state
(4) Right down the space of the current state
The above generator functions, I used four classes in the program (Java) to implement. A node can extend up to 4 nuts, and the expanded nodes are not necessarily adopted, which is related to the specific circumstances.
By defining node status and generator functions, the generation of implicit graphs of the rearrangement of the Nine-palace issues are solved. The next is to search.
6. Search strategy of the figure
After my analysis, the search strategy that can be used to rearrange the Jiuguan problem is: 1. Search, 2. Deep priority search, 2. Deep priority search, 4. It is best to search for, 5. Local selection A total of five. Among them, the breadth priority search method is adopted, and it is incomplete, and it is preferred to prioritize and partially selecting the search method.
Search for various search strategies:
Guangsheng priority search
Step 1 put the initial node S0 into the OPEN table
Step 2 If the OPEN table is empty, the search failed, the problem is unpublished
Step 3 Take the front node n in the OPEN table in the Close table, and crown to order N
Step 4 If the target node SG = N, the search is successful, the problem is solved.
Step 5 If N no child node, then step 2
Step 6 Extended node n, equipped with all the sub-nodes to the N to put the pointer, and put it in the tail of the OPEN table, step 2
Depth priority search
Step 1 put the initial node S0 into the OPEN table
Step 2 If the OPEN table is empty, the search failed, the problem is unpublished
Step 3 Take the front node n in the OPEN table in the Close table, and crown to order N
Step 4 If the target node SG = N, the search is successful, the problem is solved.
Step 5 If N no child node, then step 2
Step 6 Extended Node N, with all of its subjunction points to the N to put back the pointer, and put it in the head of the OPEN table, step 2
3. Deep priority search
Step 1 put the initial node S0 into the OPEN table, set the depth D (S0) = 0
Step 2 If the OPEN table is empty, the search failed, the problem is unpublished
Step 3 Take the front node n in the OPEN table in the Close table, and crown to order N
Step 4 If the target node SG = N, the search is successful, the problem is scheduled to step 5 if the depth D (n) == DM (depth limit value), then step 2
Step 6 If N no child node, then step 2
Step 7 extended node N, with all sub-nodes Ni pointing to N to put back the pointer, and set D (ni) = d (n) 1, then put it in the tail of the OPEN table, step 2
4. It is best to give priority search
Step 1 put the initial node S0 into the OPEN table
Step 2 If the OPEN table is empty, the search failed, the problem is unpublished
Step 3 Take the front node n in the OPEN table in the Close table, and crown to order N
Step 4 If the target node SG = N, the search is successful, the problem is solved.
Step 5 If N no child node, then step 2
Step 6 Extended Node N, equipped all of its sub-nodes to the N to put the pointer, calculate f (ni), put it in the OPEN table, then reorder the Open table (small in front), turn Step 2
5. Local selection search
Step 1 put the initial node S0 into the OPEN table
Step 2 If the OPEN table is empty, the search failed, the problem is unpublished
Step 3 Take the front node n in the OPEN table in the Close table, and crown to order N
Step 4 If the target node SG = N, the search is successful, the problem is solved.
Step 5 If N no child node, then step 2
Step 6 Extension Node N, equipped all of its subjunction points to the reset pointer to N, and calculates F (Ni). Press F (Ni) to sort (small in front), then sequentially placed in the tail of the OPEN table (F (Ni) small), step 2
The estimation function used by heuristic search method
In the heuristic search, the estimated function I use is F (n) = d (n) h (n), D (n) is the depth of the node, and H (n) is calculated by the following:
H (n) = p (n) 3s (n).
The definition of P (n) is that it is the sum of each of the N-patterns in each of the shortest distances.
S (n) is calculated as this: along the surrounding inverse squares to check each of the slings in the n pattern, if it is tightly followed, the card is just a target. After the successor, the card will be 0 points, otherwise 2 points; 1 point for the card in the middle side, otherwise 0 points. All the card score is S (N).
7. Compare between various search strategies
Both pre-priority search and depth priority search are searching for a relatively low efficiency, both can find solutions, is complete, and breadth priority search can find the best solution. A boundary-depth priority search is an improvement to depth priority search method, but it may not find solution. It is best to prioritize and local choice laws are heuristic searches. The search efficiency is high. It can find solutions quickly, but it is not necessarily the best solution.
Eight. Source program
The source program is written in the Eclips environment in the Java language.
In the entire program, I define and implement four classes respectively:
1. "Table" Class: This class inherits from the Vector class, implements all the features of the table, use it to create the "Open table" and "Close Table" objects to implement the function of the OPEN table and the Close table.
2. "Nine Palace Map Node" Class: This class represents the status node of the nine palace map, with status data and generator functions, and can generate a state space map through this class.
3. "Nine-palace map" class: This type of nine palace rearranged this problem, with "Open Table", "Close Table", "Start Status", "Target Status" and other properties, and implements all of the previously mentioned Five search methods. Use this class to complete search solving for Jiuguan rearrangement issues.
4. "Program Interface" Class: This class implements the graphical program interface of the applet, using animation technology, and convenient setting various search parameters, easy to use. All source code for the source program can be found in the compressed package, the source code is clear, and the comment is added in the appropriate place, which can be easily read and understood.
Nine. Experimental summary and thinking
Personally think that they are doing well, all five search laws are all achieved, and the effect of the program operation is quite good, and it is also very convenient to use. In practice, you can understand the knowledge on the courses. I passed this experiment, I have a basic graph search strategy is "eating".
The entire program has about 3,000 lines of code, the huge project (for me), to be completed within 6 lessons, it is impossible to complete the task, people vomiting blood. But I still stand the pressure, and fought for three days and night, I finally got it. This is benefited from the pursuit of programming, usage, and the master's mastery of the Java language.
It should be said that this experiment has made me benefit from all aspects, not just in the course of artificial intelligence.
Ten. About me
Northwestern Polytechnical University School of Computer 11424 Class Chen Kai Studies 022301
Contact RockCarry@163.com
Http://rockcarry.home.sunbo.net
Attached: a set of experimental results
The following data is generated by this program:
The system is initialized!
You have selected the preset start state
The system is initialized!
You have chosen search methods: Guangsheng priority search
Automatic search start
Search is working, please wait patiently ...
Search is complete!
Nine palace map search
Start node:
2 8 3 1 6 4 7 0 5
Target Node:
1 2 3 8 0 4 7 6 5
Search has been completed
Found the best solution
Union path:
2 8 3 1 6 4 7 0 5
2 8 3 1 0 4 7 6 5
2 0 3 1 8 4 7 6 5
0 2 3 1 8 4 7 6 5
1 2 3 0 8 4 7 6 5
1 2 3 8 0 4 7 6 5
Operating sequence:
Space
Space
Space left shift
Split
Space right
2735 nodes in the search process
Among them, 35 junctions were examined.
The length of the decompression is 6 junctions
Search efficiency is: 0.0967741935483871
The system is initialized!
You have selected the start state of the random generated
The system is initialized!
You have selected the search method: a world depth priority search method
You put the boundary depth of the boundary to the priority search: 10
Automatic search start
Search is working, please wait patiently ...
Search is complete!
Nine palace map search
Start node:
2 8 3
1 6 4
7 0 5
Target Node:
1 2 3
8 0 4
7 6 5
Search has been completed
Find out
Union path:
2 8 3
1 6 4
7 0 5
2 8 3
1 0 4
7 6 5
2 0 3
1 8 4
7 6 5
0 2 3
1 8 4
7 6 5
1 2 3
0 8 4
7 6 5
1 2 3
8 0 4
7 6 5
Operating sequence:
Space
Space
Space left shift
Split
Space right
A total of 1490 nodes were produced during the search.
Among them, 490 nodes were examined.
The length of the decompression is 6 junctions
Search efficiency is: 0.012219959266802444
The system is initialized!
You have selected the search method: best priority search method
Automatic search start
Search is working, please wait patiently ...
Search is complete!
Nine palace map search
Start node:
2 8 3
1 6 4
7 0 5
Target Node:
1 2 3
8 0 4
7 6 5
Search has been completed
Find out
Union path:
2 8 3
1 6 4
7 0 5
2 8 3
1 0 4
7 6 5
2 0 3
1 8 4
7 6 5
0 2 3
1 8 4
7 6 5
1 2 3
0 8 4
7 6 5
1 2 3
8 0 4
7 6 5
Operating sequence:
Space
Space
Space left shift
Split
Space right
A total of 66 nodes were generated during the search
Among them, 6 nodes were examined.
The length of the decompression is 6 junctions
Search efficiency is: 0.5
The system is initialized!
You have selected the search method: local selection
Automatic search start
Search is working, please wait patiently ...
Search is complete!
Nine palace map search
Start node:
2 8 3
1 6 4
7 0 5
Target Node:
1 2 3
8 0 4
7 6 5
Search has been completed
Find out
Union path:
2 8 3
1 6 4
7 0 5
2 8 3
1 0 4
7 6 5
2 0 3
1 8 4
7 6 5
0 2 3
1 8 4
7 6 5
1 2 3
0 8 4
7 6 5
1 2 3
8 0 4
7 6 5
Operating sequence:
Space
Space
Space left shift
Split
Space right
2734 nodes were generated during the search
Among them, 34 nodes were examined.
The length of the decompression is 6 junctions
Search efficiency is: 0.09836065573770492
