程序代写代做代考 algorithm data structure PowerPoint Presentation

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