1.Heuristic Problem

An Inherently Parallel Method for Heuristic Problem-Solving: Part I-General Framework

Abstract—The class of NP-hard problems contains many problems of considerable practical importance. The complexity of these problems is so overwhelming that exhaustive search of the solution space is not possible even using massively parallel search techniques, particularly for problems of super-exponential complexity such as flow-shop and job-shop scheduling. This two-part paper discusses a novel, inherently parallel heuristic solution technique. Part I presents this technique, known as Parallel Dynamic Interaction (PDI), as a general solution framework that is applicable to a number of computationally intractable problems, and gives details of its general methodology. From a parallel processing standpoint, PDI is interesting because it is inherently based upon the dynamic interplay between simultaneously executing subproblems. As such, PDI has no direct serial analog, and is not directly amenable to conventional parallel processing speedup analysis. This may provide an indication that parallel processing can offer opportunities beyond simply speeding up the solution of sequentially specified algorithms. From a practical problem-solving perspective, PDI shows promise as a method capable of generating high quality solutions to exponentially and super-exponentially hard problems. For large problems, PDI is often able to find a near-optimal solution many orders of magnitude faster than the time taken for a conventional parallel branch-and-bound search to find a solution of comparable quality. The successful application of PDI to three NP-hard problems is described in Part II of this paper.

Index Terms-NP-hard problems, heuristic problem solving, inherently parallel, dynamic interaction, locally applied heuristics

2.Map coloring problem

TheMap Colorer

Description

By coloring maps that they are given, and maps that they make, students will:

  • Understand the questions behind the map coloring problem
  • Experience map coloring problems by coloring maps and making maps to color

Materials

  • Copies of the maps that students will color. Students will probably color more than one map during a class period. It is good to have a variety of maps for them to choose from and attempt to color. The following maps can be used, or you can make others.
  • Coloring materials. Crayons are usually better than markers because they don't run out when coloring large areas.
  • Colored marking pieces, such as poker chips or unifix cubes. They are useful for planning how to color a map without actually marking the paper, so it is easy to make changes.
  • Overhead transparencies of maps that students will color are useful for demonstration purposes.

Instructions

  1. Read the story of The Young Map Colorer
  2. Invite the children to work singly or in groups (whichever they prefer) to try to discover the smallest number of colors needed to color the map.
  3. After some problem-solving, have the students discuss (and perhaps write about) their results, their strategies and reasoning and the observations that they made about the problem.
  4. Replay with more complex maps. In order to have a variety of maps to work with, you can draw additional ones that will be appropriate for your students.
  5. Show children that they can draw their own maps to share with one another and try to color them.
  6. Show students how they can experiment with various colorings without using up so many maps, or having to take the time to color them by marking regions with unifix cubes or other colored marking pieces instead of coloring them in.
  7. Read or tell A Television Story . What does the problem in this story have in common with the map coloring problem?

Ideas for Discussion

  1. Talk about the maps that you colored. How many colors did you use to color each of them?
  2. How did you go about coloring the maps? On the chalkboard, write down descriptions of the strategies that the students used. It might be useful to give the strategies names.
  3. Are there certain strategies that worked better for one map than they did for another?
  4. Is there any strategy that works for all maps?
  5. Are there good strategies for determining if a particular number of colors is enough?
  6. Can you look at a map and tell for certain how many colors it will need?
  7. Can you find a map which you are sure will require 3 colors, or 4 colors to color properly?
  8. Show students some maps and have them guess how many colors they think it will take. What do you pay attention to when you are making such a guess?
  9. What other maps did you make that were interesting to try and color? What made them interesting? Were they easy or hard to do?
  10. How is the A Television Story like the story of The Map Colorer?.