a) (10pts) Talbi #1.11 and (5 pts) Talbi #1.17 “VRP”
b) (40 pts) Best-First Search
(i) (5pts) Solve a NPC MIS, SCP, or VRP problem using A*, Z* or a BF* variation. This problem can be one of your project’s NPC problems instead. Define NPC Problem in mathematical/logical detail. Discuss PD complexity. Use references!
(ii) (20pts) Show the detailed top-down design development and integration of the selected algorithm and Problem Domain using the gs_bfs template {critical} with your specific heuristics. Use references!
(iii) (10pts) Develop your code or USE/MODIFY available code or do it by hand. For your example problem let it be small (or even medium or even large?). Discuss refined data structures and sub-algorithms employed.
(iv)(5pts) Trace search graph tree evolution for the small dimensional problem and relate to search landscape properties - objective function (Talbi, Section 2.2.2). Address AD complexity issues via gs_bfs search.
(v) (5 pts) Report and Analyze experimental performance results (Barr, MF, Talbi) via a NPC problem.
COMMENT: For all questions requesting an algorithm, put it in the form of the standard algorithmic structure used by Talbi. Also embed the CSCE686 standard search constructs via comments and regarding code use headers (Name, Developers, History, ….) even with exiting code.
