Subject: Program to Find Thread Colors for Weaving
AI HOMEWORK 4 二技子三甲 A9011031 林家瑜
- Heuristic program
############################################################################
#
#File: unravel.icn
#
#Subject: Program to find thread colors for weaving
#
#Author: Gregg M. Townsend
#
#Date: May 26, 1999
#
############################################################################
#
# This file is in the public domain.
#
############################################################################
#
#Unravel solves a coloring problem inspired by weaving. Given a
#multicolored rectangular pattern, assign colors to warp and weft
#threads that will allow the pattern to be woven on a loom.
#We ignore questions of structural integrity and insist only
#that each cell's color be matched by either the corresponding
#warp thread (column color) or weft thread (row color).
#
############################################################################
#
#Usage: unravel [-bdnv] filename
#
#-b: run in batch mode (don't show results in window)
#-d: show details of solution on &error
#-n: no shortcuts: retain solid & duplicate rows & cols
#-r: raw output on &output of columns, rows, grid data
#-t: include timing breakdown in result message
#-v: write verbose commentary on &output
#
#Input is an image file (GIF, XBM) to be mapped to the c1 palette
#(these require graphics, even in batch mode) or an image string
#acceptable to readims(). The maximum size is 256 x 256.
#
#After analysis, the pattern is declared "solved" or "insoluble".
#This result is displayed in the title of the result window and
#printed on standard error output.
#
#The output window shows an enlarged copy of the pattern with row
#and column color assignments along the top, bottom, and sides.
#With an insoluble or pattern, colors just reflect the program
#state at termination. Type "q" in the window to exit.
#
#A one-line result summary is always written to &errout. The -d
#option adds two more lines giving the row and column assignments,
#with the colors coded by the "c1" color palette.
#
#With the -r option, three lines are written to &output:
#column colorings
#row colorings
#grid data
#
############################################################################
#
# Requires: Version 9 graphics
#
############################################################################
#
# Links: graphics, imscolor, imsutils, numbers, options, random
#
############################################################################
link graphics
link imscolor
link imsutils
link numbers
link options
link random
record vector(# one row or column
index,# index of this row/column (1-based)
label,# row/column label: "rnnn" or "cnnn"
mchar,# char used in mapping
cells,# string of colors in row/column cells
live,# string of colors in active row/column cells
fam,# color family
ignored# non-null if to be ignored (if solved, or if redundant)
)
record family(# a family of vectors that must all be the same color
vset,# set of vectors
color# assigned color (null if not yet set)
)
global opts# command options
global fname# input file name
global logfile# output file for logging, if -v specified
global t1,t2,t3,t4,t5# &time measurements
global imstring# image string of original pattern specification
global data# raw cell data
global rows# list of row vectors
global cols# list of column vectors
global mapchars# string of chars used for col & row mapping
global rowvalid# valid columns in row
global colvalid# valid columns in column
############################## CONTROL ##############################
procedure main(args)
local n, v
opts := options(args, "bdnrtv")
if \opts["v"] then
logfile := &output
else
log := 1# disable logging function
*args = 1 | stop("usage: ", &progname, " [-bdnrtv] imsfile")
fname := get(args)
imstring := load(fname) | abort("can't load file")
t1 := &time
setpattern(imstring) | abort("can't parse pattern string")
setmaps()# initialize mapping strings
loggrid()# show problem diagram
t2 := &time
if /opts["n"] then {# if not -n, then reduce problem
while dupls(rows | cols) | solids() do
setmaps()# reduce problem size
loggrid()# show reduced problem
}
t3 := &time
# check for quads until no longer worthwhile
while (not trivial()) & quad(rows | cols) do {
setmaps()# reduce problem size
loggrid()# show reduced problem
}
t4 := &time
log("choosing colors arbitrarily")
every v := active(rows | cols) do# will solve or show impossible
setcolor(v, ?v.live)
setmaps()# should detect solved problem
abort("didn't finish!")
end
擷取部分程式.詳細程式:
2. Map-Coloring Problem
For example, let's consider the map coloring problem: we have a number N of countries in a map and we want to assign a color to each country from a given palette, such that each country has a different color with respect to all the neighboring countries.
In this problem, we can consider a variable for each country in the map. Each variable can be assigned a color, so the domains will be the range of colorsNot every assignment is feasible, because of the constraint that imposes different color for neighboring countries. The constraint graph can be represented as a set of nodes, which represent the countries, and arcs connecting the nodes which represent the constraints between two neighboring countries.
相關網站: