| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| public:t-622-arti-11-1:program_1 [2011/01/27 10:36] – hannes | public:t-622-arti-11-1:program_1 [2024/04/29 13:33] (current) – external edit 127.0.0.1 |
|---|
| - Download and unzip the file {{:public:t-622-arti-11-1:search.zip|search.zip}} into your working directory. You will use the file **''search.lisp''** as a starting point. It contains some useful structures and functions. Read the comments above each function in order to have an overall idea before you start.\\ **NOTE**: you should take a look at this file also if you are using a different programming language. You might implement the same functions in order to have the same settings, in addition you can take inspiration on how to define/create environments. | - Download and unzip the file {{:public:t-622-arti-11-1:search.zip|search.zip}} into your working directory. You will use the file **''search.lisp''** as a starting point. It contains some useful structures and functions. Read the comments above each function in order to have an overall idea before you start.\\ **NOTE**: you should take a look at this file also if you are using a different programming language. You might implement the same functions in order to have the same settings, in addition you can take inspiration on how to define/create environments. |
| - Formulate the problem as a basic **search problem** (initial state, goal test, successor function) - write this information clearly as comments at the beginning of your file. | - Formulate the problem as a basic **search problem** (initial state, goal test, successor function) - write this information clearly as comments at the beginning of your file. |
| - Implement a **breadth-first** (**BF**), **depth-first** (**DF**) and **iterative-deepening** (**ID**) search strategies. Try to re-use your search mechanism as much as possible (i.e. see if you can plug the search strategy into a general mechanism). | - Implement a **breadth-first** (**BF**), **depth-first** (**DF**) and **iterative-deepening depth-first** (**ID**) search strategies. Try to re-use your search mechanism as much as possible (i.e. see if you can plug the search strategy into a general mechanism). |
| - Compare your strategies by collecting **performance measures**, both for particular environments and averaged over runs of the search with **different environments** (a set of environments is provided into the assets file). The measures should include whether the gold was found (**completeness**), the length of the chosen path to the gold (**optimality**), the number of node expansions (**time**) and the maximum number of search nodes in the search tree (**memory**).\\ **NOTE**: if you are not using **LISP**, you could define several environments in a text file using your own notation (i.e. you can have several lines describing each one a row in your environment. In each line, you can use '0' for empty squares, 'W' for impassable walls and 'G' for gold. You can separate different environments with an empty line). Then you can read the environments from that file and you should be able to experiment different performances by simply changing the file contents and running again your program without any change to your source code. | - Compare your strategies by collecting **performance measures**, both for particular environments and averaged over runs of the search with **different environments** (a set of environments is provided into the assets file). The measures should include whether the gold was found (**completeness**), the length of the chosen path to the gold (**optimality**), the number of node expansions (**time**) and the maximum number of search nodes in the search tree (**memory**).\\ **NOTE**: if you are not using **LISP**, you could define several environments in a text file using your own notation (i.e. you can have several lines describing each one a row in your environment. In each line, you can use '0' for empty squares, 'W' for impassable walls and 'G' for gold. You can separate different environments with an empty line). Then you can read the environments from that file and you should be able to experiment different performances by simply changing the file contents and running again your program without any change to your source code. |
| - Write a **summary** of your findings - inside a comment block in the returned LISP file. | - Write a **summary** of your findings - inside a comment block in the returned LISP file. |
