PowerPoint Presentation
1
159.302 Tips for Assignment #1
Search Algorithms
159302
1
Several Algorithms and their variants
Breadth-First Search without the Visited List
Breadth-First Search with the Visited List
PDS without the Visited List
Uniform Cost Search with the Expanded List
A* with the Strict Expanded List (h=MisplacedTiles)
A* with the Strict Expanded List (h= Sum of Manhattan distances)
2
Algorithm Experiments
Test all algorithms on the given 6 Start & Goal states.
Tabulate the results.
Compare the algorithms’ performance.
Use the given batch files to run the experiments.
Run the algorithms until:
a solution is found/Q turned empty
the program ran out of memory
Optional enhancements (to get some Bonus marks)
Excess bonus marks will be added to total final marks.
Original Heap data structure implementation, and correct use with A*
Original Hash function & table for the Visited List and Expanded List.
3
4
8-Puzzle
Start-up codes for Assignment #1 (2019)
4
Main.exe : Main.o graphics.o puzzle.o algorithm.o
g++ -std=c++11 -o Main.exe Main.o graphics2.o puzzle.o algorithm.o -l gdi32 -static-libgcc -static-libstdc++
Main.o : Main.cpp graphics2.h puzzle.h algorithm.h
g++ -std=c++11 -c -Wno-write-strings Main.cpp
puzzle.o : puzzle.cpp puzzle.h
g++ -std=c++11 -c -Wno-write-strings puzzle.cpp
algorithm.o : algorithm.cpp algorithm.h
g++ -std=c++11 -c -Wno-write-strings algorithm.cpp
graphics2.o : graphics2.cpp graphics2.h
g++ -std=c++11 -c -Wno-write-strings graphics2.cpp
clean:
del *.o
del *.exe
5
SEARCH
Start-up Codes (2019)
The start-up system is comprised of multiple files.
The program requires that you “build” it using a makefile.
(Ctrl+F7 for ScITE)
Must be preceded by a tab.
back
5
-static-libgcc or -static-libstdc++, to avoid run-time dependencies on libgcc or libstdc++
http://www.mingw.org/category/wiki/gcc DLLs
Skeleton functions are provided in the start-up codes.
6
SEARCH
Start-up Codes
Place your algorithm implementations inside algorithm.cpp
Include the function prototypes inside algorithm.h
algorithm.cpp algorithm.h
#include “algorithm.h”
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////
// Search Algorithm: Breadth-First Search
////////////////////////////////////////////////////////////////////////////////////////////
string breadthFirstSearch_with_VisitedList(string const initialState, string const goalState,
int &numOfStateExpansions, int& maxQLength, float &actualRunningTime){
// put your implementation codes here…
}
This is to avoid writing a cluttered program. The batch files also rely on specific algorithm names as parameters
back
6
SEARCH
Main function (required arguments)
int main( int argc, char* argv[ ] ){
string path;
cout << "=========<< SEARCH ALGORITHMS >>=========” << endl;
if(argc < 5){
cout << "SYNTAX: main.exe ALGORITHM_NAME \”INITIAL STATE\” \”GOAL STATE\” ” << endl;
…
…
}
The program requires 4 arguments.
back
7
8
SEARCH
Main function (required arguments)
int main( int argc, char* argv[ ] ){
string path;
cout << "=========<< SEARCH ALGORITHMS >>=========” << endl;
if(argc < 5){
cout << "SYNTAX: main.exe ALGORITHM_NAME \”INITIAL STATE\” \”GOAL STATE\” ” << endl;
…
…
}
Batch files are provided to run all the experiments.
The program requires 4 arguments.
main.exe "batch_run" “breadth_first_search_vlist" "042158367" "012345678"
Example:
type of run = "batch_run" or "single_run"
INITIAL STATE GOAL STATE
Algorithm name
Batch_run – for tabulation of results (run_all.bat)
Single_run – for animated solution (run_one.bat)
Running the program:
back
8
9
"breadth_first_search"
"breadth_first_search_vlist"
"pds_no_vlist"
"uniformcost_expandedlist"
"astar_explist_misplacedtiles"
"astar_explist_manhattan"
SEARCH
Main function (required arguments)
main.exe "batch_run" “breadth_first_search_vlist" "042158367" "012345678"
Example:
type of run = "batch_run" or "single_run"
INITIAL STATE GOAL STATE
Algorithm name
Batch_run – for tabulation of results (run_all.bat)
Single_run – for animated solution (run_one.bat)
Running the program:
Algorithm name
back
10
Batch files for quick testing
run_all.bat
run_one.bat
back
SEARCH
Batch run (run_all.bat)
Running the algorithms
Batch run
This type of run is used for running all the experiments required for all the algorithms.
Results are tabulated nicely, according to the requirements of the assignment.
Example:
Extra information for those who can implement the original Heap data structure for A* to get some bonus marks.
back
11
12
SEARCH
Batch run (run_all.bat)
Specific algorithm names are provided in the start-up codes to identify all the algorithms.
Running the algorithms
main.exe "batch_run" “breadth_first_search_vlist" "042158367" "123804765"
Example:
type of run = "batch_run" or "single_run"
INITIAL STATE GOAL STATE
Algorithm name
main.exe "batch_run" "Breadth_First_Search" "042158367" "123804765"
main.exe "batch_run" "Breadth_First_Search_VList" "042158367" "123804765"
main.exe "batch_run" "PDS_No_VList" "042158367" "123804765"
main.exe "batch_run" "uniformcost_expandedlist" "042158367" "123804765"
main.exe "batch_run" "aStar_ExpList_MisplacedTiles" "042158367" "123804765"
main.exe "batch_run" "aStar_ExpList_Manhattan" "042158367" "123804765"
back
12
13
SEARCH
Animated Solution (run_one.bat)
if(algorithmSelected == "breadth_first_search_vlist" ){
path = breadthFirstSearch_with_VisitedList(initialState, goalState, numOfStateExpansions, maxQLength, actualRunningTime);
} else if(…){
}…
…
if(typeOfRun == "single_run"){
if(path != "") {
AnimateSolution(initialState, goalState, path);
}
}
The “single_run” parameter invokes the AnimateSolution function.
An animation function is provided for you.
Using graphics to show the animated solution
e.g. path=“URRDLURRDLR”
Skeleton function
back
13
SEARCH
Animated Solution (run_one.bat)
.
Try run_one.bat
back
14
SEARCH
Some notes on implementing the Progressive Deepening Search
C=1
Do Depth-limited DFS to max. depth C. If path is found, return it.
Otherwise, increment C and go to Step 2.
Pseudocode
back
15
16
Example: Depth-limited Depth-First Search
Successor generator: Left, Up, Right, Down
Note: the complete search tree is not shown here.
…
…
…
goal
start
At depth bound = 5
The algorithm is looking for a sequence of moves that will arrange any given initial board configuration to match the goal state.
17
Depth-limited Depth-First Search
Successor generator: Left, Up, Right, Down
The successors of a state are to be generated in a FIXED order, to be drawn from left to right, namely move the blank tile: Up, Right, Down, then Left.
There are 9! states but not all of them are reachable from a given board position.
6 2 8
3 5
4 7 1
S
6 2 8
3 5
4 7 1
2 8
6 3 5
4 7 1
6 2 8
3 5
4 7 1
6 2 8
4 3 5
7 1
Up
Right
Down
Left
A move corresponds to moving the blank ‘0’-tile
The states are the board configurations
In the start-up codes, I am providing a class named Puzzle to give the class some clue on how to approach the problem using an object-oriented programming style.
The class Puzzle is not complete, if you intend to use it in your assignment, you will have to fill-in the missing functions.
void Puzzle::updateFCost(){
//fCost = ?
}
//Heuristic function implementation
int Puzzle::h(heuristicFunction hFunction){
int sum=0;
int h=0;
int numOfMisplacedTiles=0;
switch(hFunction){
case misplacedTiles:
//place your implementation here
//h = ??? //numOfMisplacedTiles;
break;
case manhattanDistance:
//place your implementation here
//h = ??? //sum of manhattan distance;
break;
};
return h;
}
Note that it is not required to use the class Puzzle when implementing the different algorithms - you may design your own class from scratch.
class Puzzle
class Puzzle{
private:
string path; //moves generated (e.g. URDL..)
int pathLength;
int hCost;
int fCost;
int depth;
int goalBoard[3][3]; //goa board configuration
int x0, y0; //coordinates of the blank or 0-tile
int board[3][3]; //current board configuration
1 2 3
8 4
7 6 5
Goal
//used by A*
class Puzzle
6 2 8
3 5
4 7 1
x
y
0
1
2
0
1
2
Feel free to add more variables and functions that you may require.
Puzzle(const Puzzle &p); //constructor; creates a copy of a given puzzle
Puzzle(string const elements, string const goal); //constructor; generates 2D-array versions corresponding to an initial board configuration and a goal configuration.
void printBoard(); //prints the content of a puzzle
int h(heuristicFunction hFunction); //computes for the heuristic value of a state
void updateFCost(); //computes for the f-cost of a search node
bool goalMatch(); //returns true if the current board configuration matches the goal state; otherwise, false
bool canMoveLeft();
bool canMoveRight();
bool canMoveUp();
bool canMoveDown();
Puzzle * moveUp();
Puzzle * moveRight();
Puzzle * moveDown();
Puzzle * moveLeft();
//checks to see if the blank 0-tile could be moved in a specific direction (codes provided)
//creates an instance of a Puzzle (including memory allocation), representing the result of the move taken. It also keeps track of the sequence of moves taken (or the partial path). The function returns a Puzzle object. (codes provided)
a Q is a container for the partial paths (search nodes) being considered for expansion.
depending on the algorithm you are implementing, you may be needing a Queue, Stack or a Priority Queue to implement this Q container.
( )( )( )
6 2 8
3 5
4 7 1
2 8
6 3 5
4 7 1
6 2 8
3 5
4 7 1
6 2 8
3 5
4 7 1
6 2 8
3 5
4 7 1
6 2 8
4 3 5
7 1
Q
Tips: The class Puzzle may be extended with a few additional variables and functions, to implement a class Search_Node.
When extending a node, moveUp(), moveRight(), moveDown(), moveLeft() comes handy.
Within a search node, there shouldn’t be any repeating nodes/no local loops allowed (i.e. add variables and test functions to do this).
Search node
23
SEARCH
Admissible Heuristics
Alternative underestimates of “distance” (number of moves) to goal:
8 Puzzle: Move tiles to reach goal. Think of a move as moving an “empty” tile.
6 2 8
3 5
4 7 1
1 2 3
8 4
7 6 5
S
G
Number of misplaced tiles (7 in the example above).
Sum of Manhattan Distance of tile to its goal location (17 in example above).
Manhattan Distance between (x1, y1) and (x2, y2) is │x1 – x2│ and │y1 – y2│.
Each move can only decrease the distance of exactly one tile.
The second of these is much better at predicting actual number of moves.
23
24
SEARCH
Admissible Heuristics
8 Puzzle: Move tiles to reach goal. Think of a move as moving an “empty” tile.
1 2 3
8 4
7 6 5
S
G
Number of misplaced tiles
1 3
8 2 4
7 6 5
Are we supposed to include the blank tile in the counting of misplaced tiles?
What will be the consequence if we include it? Examine the case above.
No.
The heuristic will no longer be admissible. A* will miss finding the optimal solution if the heuristic is not admissible.
24
25
SEARCH
Hash function
Keys
Hash function
Hash Values
123456
123457
123458
123459
.
.
.
.
.
.
Search Nodes
Fixed length
A hash function could be used to map large data sets of variable length, called keys to hash values that are of a fixed length. The hash values may serve as indexes to an associative array.
However, hash values may have duplicates; therefore, may cause collision between keys.
Hash(key)
false
true
true
true
A quick look-up of the status of states
e.g.
index
We can implement the Visited List/Expanded List using a hash table.
26
SEARCH
Hash function
Keys
Hash function
Hash Values
000001
362879
200000
300879
.
.
.
.
.
.
Search Nodes
Fixed length
Hash()
false
true
true
true
A quick look-up of the status of states
e.g.
Visited List / Expanded List
Given a state, we can quickly check whether or not we have visited/expanded it previously.
STATE
362880
true
.
.
.
.
.
.
/docProps/thumbnail.jpeg