\n Map Coloring Problem\n <\/p>\n<\/div>\n
Map Coloring Problem
\n6.10 Generate random instances of map-coloring problems as follows: scatter n points on the unit square; select a point X at random, connect X by a straight line to the nearest point Y such that X is not already connected to Y and the line crosses no other line; repeat the previous step until no more connections are possible. The points represent regions on the map and the lines connect neighbors. Now try to find k-colorings of each map, for both k=3 and k =4, using min-conflicts, backtracking, backtracking with forward checking, and backtracking with MAC. Construct a table of average run times for each algorithm for values of n up to the largest you can manage. Comment on your results. Notes: Each point represents a country. An edge between two points represents a border between two countries, i.e., the two points should have different colors. This type of graph, no crossings, is called\u00a0Planar Graph. By the\u00a0Four Color Theorem,\u00a0every planar graph is four-colorable. It is fairly easy to determine whether a graph is 2-colorable or not. To determine whether a graph is 3-colorable is\u00a0NP-complete. The objective of this exrcise to try to see if you can solve with 3 colors using CSP.<\/p>\n","protected":false},"excerpt":{"rendered":"
Map Coloring Problem Map Coloring Problem 6.10 Generate random instances of map-coloring problems as follows: scatter n points on the unit square; select a point X at random, connect X by a straight line to the nearest point Y such that X is not already connected to Y and the line crosses no other line; […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_joinchat":[]},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/posts\/285537"}],"collection":[{"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/comments?post=285537"}],"version-history":[{"count":0,"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/posts\/285537\/revisions"}],"wp:attachment":[{"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/media?parent=285537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/categories?post=285537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qualityassignments.net\/wp-json\/wp\/v2\/tags?post=285537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}