Search
A Guide for the Seminar
Authors: Milan Rollo, Eduard Semsch, Štěpán Urban, Viliam Lisý a Petr Benda Translation: Radek Píbil Edit: Tibor Strašrybka
Practice the informed state-space search solutions. It is important for students to understand the UCS algorithm, the greedy algorithm and the A* algorithm and that they are capable of discussing their features and limitations. The seminar plan is:
You are given a map of the maze. Black squares are inaccessible. Cost of passing through grey squares is 3, while cost of passing through white is 1. The task is to plan a path from square A to square B (or C) with a smallest cost.
Use the UCS algorithm to find a path from square A to square B. Is the solution going to be optimal?
Apply the best-first search algorithm. Use the distance to the target expressed as the taxicab (Manhattan) norm (sum of the absolute differences in coordinates also known as Manhattan distance). If there are multiple squares within the same distance, white squares are preferred, if there are still more than more square, pick at random.
The task is identical to the previous one. The only difference is the algorithm to be used.
Apply the A algorithm. The heuristic function is the taxicab norm again.
The task is identical to the previous ones. Compare the number of steps and optimality of solutions given by these three algorithms we have shown.
A factory needs to plan (schedule) the production of 50 types of products on the manufacturing line. The constraints are the capacity of the line in units/hour and for each of the product types and shipping orders for units of a product type (hundreds of orders). The profit (optimality) is given by uniformity of the line load (price of overtimes and pauses) and storing price for each of the early manufactures products per day.
For practical reasons (machine setup) it is important to keep manufacturing continuously a single product for as long possible. The storage is empty at the beginning.
Propose a formal description of the task, describe the state-space and constrains, design a heuristic and discuss the features of the A* algorithm.
Airplane: The airplane may fly in one of the four flight altitudes. The fuel consumption in the first one is 5 units of fuel per a unit of distance. The second one has 4 units etc. The fuel consumption during transition between levels is 10, when going up, 1 when down. The airplane has to travel between airports 10 units of distance far from each other. The plane’s fuel capacity is 50 units of fuel. Optimize the fuel consumption.