１３
一类约束满足问题的ＬＩＮＧＯ算法
ａ　Ｃｌａｓｓ　ｏｆ　Ｃｏｎｓｔｒａｉｎｔ　Ｓａｔｉｓａｆａｃｔｉｏｎ　Ｐｒｏｂｌｅｍｓ　ａｎｄ　ＬＩＮＧＯ　Ａｌｇｏｒｉｔｈｍｓ
李朝阳
Ｌｉ　Ｚｈａｏｙａｎｇ
（北京工商大学数理系，　北京１０００３７）
（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｐｈｙｓｉｃｓ，Ｂｅｉｊｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｂｕｓｉｎｅｓｓ　Ｕｎｉｖｅｒｓｉｔｙ，　Ｂｅｉｊｉｎｇ１０００３７）

摘要：　ＬＩＮＧＯ主要用来求解大型数学规划问题，而利用它求解约束满足问题尚未见到文献报道。本文以著名的“斑
马”问题为例，将这类约束满足问题转化为０－１规划求可行解的问题，利用ＬＩＮＧＯ求解，取得了满意的结果。
关键词：　约束满足问题；ＬＩＮＧＯ；斑马问题；０－１规划；可行解
中图分类号：Ｏ２２１．１文献标识码：Ａ文章编号：１６７１－４７９２－（２００６）７－００４７－０２
Ａｂｓｔｒａｃｔ：　ＬＩＮＧＯ　ｉｓ　ｍａｉｎｌｙ　ｕｓｅｄ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｌａｒｇｅ　ｓｃａｌｅ　ｌｉｎｅａｒ　ｐｒｏｇｒａｍｍｉｎｇ，　ｂｕｔ　ｔｏ　ｓｏｌｖｅ　ａ　ｃｏｎｓｔｒａｉｎｔ
ｓａｔｉｓａｆａｃｔｉｏｎ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ＬＩＮＧＯ　ｈａｓ　ｎｅｖｅｒ　ｂｅｅｎ　ｒｅｐｏｒｔｅｄ　ｂｅｆｏｒｅ．　Ｔｈｉｓ　ｐａｐｅｒ　ｔａｋｅ　ａ　ｗｅｌｌ－ｋｎｏｗｎ　ｐｒｏｂｌｅｍ－ｚｅｂｒａ
ｐｒｏｂｌｅｍ　ａｓ　ａｎ　ｅｘａｍｐｌｅ，　ｃｏｎｖｅｒｔｅｄ　ｔｈｅ　ｃｏｎｓｔｒａｉｎｔ　ｓａｔｉｓａｆａｃｔｉｏｎ　ｐｒｏｂｌｅｍ　ｏｆ　ｔｈｉｓ　ｃｌａｓｓ　ｔｏ　ａ　ｆｉｎｄｉｎｇ　ｆｅａｓｉｂｌｅ
ｓｏｌｕｔｉｏｎ　ｏｆ　ｂｉｎａｒｙ　ｉｎｔｅｇｅｒ　ｐｒｏｇｒａｍｍｉｎｇ，　ａｎｄ　ｔｈｅ　ｒｅｓｕｌｔ　ｗａｓ　ｓａｔｉｓｆａｃｔｏｒｙ．
Ｋｅｙｗｏｒｄｓ：　Ｃｏｎｓｔｒａｉｎｔ　Ｓａｔｉｓａｆａｃｔｉｏｎ　Ｐｒｏｂｌｅｍ；ＬＩＮＧＯ；Ｚｅｂｒａ　Ｐｒｏｂｌｅｍ；Ｂｉｎａｒｙ　Ｉｎｔｅｇｅｒ　Ｐｒｏｇｒａｍｍｉｎｇ；Ｆｅａｓｉｂｌｅ
Ｓｏｌｕｔｉｏｎ

１约束满足问题
求解约束满足问题就是寻找该问题的可行解。约束满足
问题在不同的领域均有着广泛的应用，如资源配置、地图着
色等。“斑马”问题［１］是一个著名的约束满足问题：　在五
个颜色各异的房子中，居住着不同国籍的人，他们饲养的宠
物、喜欢的饮料以及拥有的汽车各不相同，且有如下信息：
①英国人住在红房子里；　②西班牙人养狗；　③居住在绿房子
里的人喝可乐；　④乌克兰人喝酒；　⑤绿房子是白色房子的右
邻；　⑥拥有老爷车的人养蜗牛；　⑦拥有福特汽车的人住在黄
房子里；　⑧住在中间房子里的人喝牛奶；　⑨挪威人住在最左
边的房子里；　⑩拥有雪佛莱汽车的人与养狐狸的人是邻居；
⑾拥有福特汽车的人与养马的人是邻居；　⑿拥有奔驰汽车的
人爱喝橙汁；　⒀日本人开大众汽车；　⒁挪威人的邻居住在蓝
房子里。问题是：　斑马属于谁？谁爱喝矿泉水？
２“斑马”问题的ＬＩＮＧＯ模型
根据问题所给的条件，将五种颜色、国籍、饮料、车及
宠物分别标号（如表一所示）。
房间的标号为１－５，且规定从左至右的顺序为１、２、３、
４、５。
定义０－１变量如下：　ｘ（ｉ，ｊ）表示房子ｊ的颜色是否为ｉ
（若是则其值为１，否则其值为０，下同），ｙ（ｉ，ｊ）表示住在房
子ｊ的人的国籍是否为ｉ，ｚ（ｉ，ｊ）表示住在房子ｊ的人喝的饮
料是否为ｉ，ｖ（ｉ，ｊ）表示住在房子ｊ的人拥有的车是否为ｉ，
ｗ（ｉ，ｊ）表示住在房子ｊ的人养的宠物是否为ｉ。显然这些变

量须满足如下两组基本约束：
这里Ａ（ｉ，ｊ）分别取ｘ（ｉ，ｊ）、ｙ（ｉ，ｊ）、ｚ（ｉ，ｊ）、ｖ（ｉ，ｊ）和
ｗ（ｉ，ｊ）。下面用等式和不等式表示问题所给的各个约束：
约束（１）英国人住在红房子里可表示为：

；
同理，约束（３）、（４）可分别表示为：　
１４

和
和