Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:pllib:map_colouring2 [2019/06/27 15:50] |
pl:prolog:pllib:map_colouring2 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== Map colouring2 ====== | ||
| + | {{tag>map problem_solving}} | ||
| + | ===== Description ===== | ||
| + | Map coloring | ||
| + | |||
| + | {{:prolog:pllib:map_colouring2.png|}} | ||
| + | |||
| + | **Source**: "The Art of Prolo | ||
| + | |||
| + | |||
| + | ===== Download ===== | ||
| + | Program source code: {{map_colouring2.pl}} | ||
| + | ===== Listing ===== | ||
| + | <code prolog> | ||
| + | /* | ||
| + | |||
| + | color_map(Map,Colors) :- | ||
| + | |||
| + | Map is colored with Colors, so that no two neighbors have the same | ||
| + | |||
| + | color. The map is represented as an adjacency-list of regions | ||
| + | |||
| + | region(Name,Color,Neighbors), where Name is the name of the | ||
| + | |||
| + | region, Color is its color, and Neighbors are the colors of the | ||
| + | |||
| + | neighbors. | ||
| + | |||
| + | */ | ||
| + | |||
| + | color_map([Region|Regions],Colors) :- | ||
| + | |||
| + | color_region(Region,Colors), | ||
| + | |||
| + | color_map(Regions,Colors). | ||
| + | |||
| + | color_map([],Colors). | ||
| + | |||
| + | /* | ||
| + | |||
| + | color_region(Region,Colors) :- | ||
| + | |||
| + | Region and its neighbors are colored using Colors so that the | ||
| + | |||
| + | region's color is different from the color of any of its neighbors. | ||
| + | |||
| + | */ | ||
| + | |||
| + | color_region(region(Name,Color,Neighbors),Colors) :- | ||
| + | |||
| + | select(Color,Colors,Colors1), | ||
| + | |||
| + | members(Neighbors,Colors1). | ||
| + | |||
| + | |||
| + | |||
| + | select(X,[X|Xs],Xs). | ||
| + | |||
| + | select(X,[Y|Ys],[Y|Zs]) :- select(X,Ys,Zs). | ||
| + | |||
| + | |||
| + | |||
| + | members([X|Xs],Ys) :- member(X,Ys), members(Xs,Ys). | ||
| + | |||
| + | members([],Ys). | ||
| + | |||
| + | |||
| + | |||
| + | /* Test data */ | ||
| + | |||
| + | |||
| + | |||
| + | test_color(Name,Map) :- | ||
| + | |||
| + | map(Name,Map), | ||
| + | |||
| + | colors(Name,Colors), | ||
| + | |||
| + | color_map(Map,Colors). | ||
| + | |||
| + | |||
| + | |||
| + | map(test,[region(a,A,[B,C,D]), region(b,B,[A,C,E]), | ||
| + | |||
| + | region(c,C,[A,B,D,E,F]), region(d,D,[A,C,F]), | ||
| + | |||
| + | region(e,E,[B,C,F]), region(f,F,[C,D,E])]). | ||
| + | |||
| + | |||
| + | |||
| + | map(west_europe, | ||
| + | |||
| + | [ region(portugal,P,[E]), region(spain,E,[F,P]), | ||
| + | |||
| + | region(france,F,[E,I,S,B,WG,L]), region(belgium,B,[F,H,L,WG]), | ||
| + | |||
| + | region(holland,H,[B,WG]), region(west_germany,WG,[F,A,S,H,B,L]), | ||
| + | |||
| + | region(luxembourg,L,[F,B,WG]), region(italy,I,[F,A,S]), | ||
| + | |||
| + | region(switzerland,S,[F,I,A,WG]), region(austria,A,[I,S,WG])]). | ||
| + | |||
| + | |||
| + | |||
| + | colors(X,[red,yellow,blue,white]). | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | % Program 14.4: Map coloring | ||
| + | |||
| + | %?- test_color(west_europe,X). | ||
| + | |||
| + | |||
| + | |||
| + | </code> | ||
| + | ===== Comments ===== | ||
