代写C/C++ programmers|代写人工智能算法

日期：2018-04-18 07:52

Fall 2017 - CSC545 Artificial Intelligence - Assignment 4

Due date: Wednesday, October 25, 2017, 3:30 pm (ET), upload to home folder of class.1

The Four Color problem is one of the most famous problems in Mathematics. The problem consists

of the question whether any map can be colored using four colors in such a way that adjacent regions

(i.e. those sharing a common boundary segment, not just a point) receive different colors. This

problem has been formulated first by Francis Guthrie in 1852 (published in 1878) and was unsolved

for roughly a century. Wolfgang Haken und Kenneth Appel could prove the four color theorem with

the help of a computer program in 1977 [Ken77].

Exercise 4.1 [4 points]

Read chapter 4.1 – 4.2 and 6.2 of the textbook.

1. Define in your own words the terms constraint satisfaction problem, constraint, back-tracking

search, back-jumping, and min-conflicts. [2.5 points]

2. How many solutions are there for the three-color map-coloring problem in Figure 1? Elaborate

your answer. [1.5 points]

(a) States and Territories (b) Constraint-graph

Figure 1: a) The principal states and territories of Australia. b) The map-coloring problem represented

as a constraint graph.

1Please upload into a folder called assignment4. You need to mkdir the subdirectory yourself in your home folder.

For all qualitative (i.e. non-code) answers, create a text file called ex4.txt (case sensitive) within the assignment4

directory. Create a subdirectory named src under assignment4 (case sensitive) that will contain your program(s).

Include a README file, that briefly explains how your code works. C/C++ programmers: have an executable file named

main (note the case). Your code will be tested using: ./main Java programmers: name the file containing the main

class as main.java (note the case). Your code will be tested using: java main. Significant credit will be deducted

for assignments with the wrong filename or wrong format.

Exercise 4.2 [16 points]

Consider the political map of the South-Eastern states of the US (states North Carolina, South

Carolina, Virginia, Tennessee, Kentucky, West Virginia, Georgia, Alabama, Mississippi, and Florida,

see Figure 2). How can we color this map with the four color theorem using a Genetic Algorithm?

Figure 2: South-Eastern

states of the US

1. How is this problem represented in general (write in your own

words). Define the states, the goal-test, and the successor function

of your problem.

[2 points]

2. Implement your algorithm and show the results. You may want to

use the framework provided by Alexander H¨artl (download Java, C++, C).[14 points]

References

[Ken77] Kenneth Appel and Wolfgang Haken. Every planar map is four colorable. Part I. Discharging.

Illinois Journal of Math, 21:429–490, 1977.