To check for near cycles you must trace through the route looking for intersections that appear later in the route.
EXTREMELY IMPORTANT!!!
Make a working copy of your
assignment #2 code to use for testing at the end. At the end of
this assignment you should have 2 versions of the program. You
will only be required to turn in the second.
In the last assignment you wrote a ms-go-from-to function which stored, retrieved, and adapted routes. You may have discovered, however, that the routes acquired by a breadth-first search (BFS) were in general better than the routes acquired using a case-based method. The reason for this is that a BFS strategy will provide an optimal path from the start intersection to the goal, while a case-based strategy does not guarantee one. You should also have discovered that the case-based strategy arrived at an answer much faster than a search strategy in most cases. One of the goals of this assignment is to improve the optimality of your case-based system, so that it retains the time efficiency of a case-based strategy, but also provides routes which are closer to the optimality of a search based strategy.
In this assignment you will add three modules to your multi-strategy system: evaluation, repair, and strategy selection. The evaluation module will look at an adapted case and determine if the case is OK (e.g. does it have cycles). The repair module will take cases that are not OK and fix them (e.g. remove cycles), and the strategy selection module will determine which strategy to use at a given time. Each of these three modules will depend upon the use of heuristics. Your new multi-strategy route planner will have 6 modules (the emphasized modules are new).
Your route planner at present takes a parameter to determine which strategy to use. So, as the system user, you are choosing which strategy the system should try. This requires some intelligence, and is an intelligent process which can be automated. The process of choosing a strategy is called: strategy selection. For this module you will write a function (or set of functions) which determines which strategy to use. Because we don't want a system that makes arbitrary choices of strategies, your system will need to have some knowledge that helps it determine which strategy to use. For this assignment, you will encode that knowledge in the form of rules. The rules will be based on knowledge which is acquired from the modules which you have written thus far. Examples:
The ADAPTATION module in your route planner uses search (or possibly a case) to adapt a retrieved case to the new case. These adapted cases, however, often provide long or circular routes. This module should do 2 things:
Once you have identified cycles and near cycles in your route,
you must then repair them. To do this you will need to write a
function (or set of functions) which takes the output of the evaluation
module and returns a new repaired case. Repair is done by removing
cycles and near-cycles.
Stage 1: Run the following using your program from assignment #2.
Stage 2: Repeat steps 1 through 4 using your new improved program.
