当前位置:文档之家› A constraints satisfaction approach to the robust spanning tree problem with interval data

A constraints satisfaction approach to the robust spanning tree problem with interval data

A constraints satisfaction approach to the robust spanning tree problem with interval data
A constraints satisfaction approach to the robust spanning tree problem with interval data

A Constraint Satisfaction Approach

to the Robust Spanning Tree Problem with Interval Data

Ionut?Aron and Pascal Van Hentenryck

Brown University,Department of Computer Science,

Providence,RI,02912

E-mail:{ia,pvh}https://www.doczj.com/doc/4517455765.html,

Abstract.Robust optimization is one of the fundamental approaches to deal with

uncertainty in combinatorial optimization.This paper considers the robust span-

ning tree problem with interval data,which arises in a variety of telecommunica-

tion applications.It proposes a constraint satisfaction approach using a combina-

torial lower bound,a pruning component that removes infeasible and suboptimal

edges,as well as a search strategy exploring the most uncertain edges?rst.The

resulting algorithm is shown to produce very dramatic improvements over the

mathematical programming approach of Yaman et al.and to enlarge consider-

ably the class of problems amenable to effective solutions.

In particular,it runs several hundred times faster than the MIP approach on the instance data proposed in [Yaman et al.,2001].It also exhibits even more signif-icant speed-ups on other instances which have more structure.In addition,the constraint satisfaction ap-proach signi?cantly broadens the class of instances that are amenable to effective solutions.Observe also that the constraint satifaction approach should apply equally well to other robust optimization problems,such as ro-bust matching and robust shortest paths,which also arise in telecommunications and computational ?https://www.doczj.com/doc/4517455765.html,-binatorial lower bounds can be obtained similarly and the challenge is mainly to ?nd effective characterizations of suboptimal solutions.As a consequence,we believe that constraint satisfaction approaches are likely to play a fundamental role in the solving of robust optimization problems in the future.We also believe that the concept of suboptimality pruning,i.e.,removing values that can-not appear in any optimal solution,is fundamental and deserves further study for optimization problems in gen-eral.

The rest of the paper is organized as follows.Sections 2and 3de?ne the problem and discuss prior work.Sec-tions 4,5,6,and 7discuss the search algorithm,the lower bound,suboptimality pruning,and branching.Section 8presents the experimental results,and Section 9con-cludes the paper.2

The Problem

Informally speaking,the robust spanning tree prob-lem,given an undirected graph with interval edge costs,

amounts to ?nding a tree whose cost is as close as possi-ble to that of a minimum spanning tree under any possi-ble assignment of costs.This section de?nes the problem formally and introduces the main concepts and notations used in the paper.

We are given an undirected graph G =(V,E )with |V |=n nodes and |E |=m edges and an interval [c e c e ]for the cost of each edge e ∈E .A scenario s is a partic-ular assignment of a cost c e ∈[c e c e ]to each edge e ∈E .We use c s e to denote the cost of edge e under a given sce-nario s .

Recall that a spanning tree for G =(V,E )is a set of edges T ?E such that the subgraph G =(V,T )is acyclic and ?i ∈V,?j ∈V :(i,j )∈T .The cost of a spanning tree T for a scenario s ,denoted by c s T ,is the sum of the costs of all edges under scenario s :

c s T = e ∈T

c s e .

A minimum spanning tree for scenario s ,denoted by

MST s ,is a spanning tree with minimal cost for sce-nario s and its cost is denoted by c MST s .Following [Yaman et al.,2001],we now de?ne the worst case sce-nario for a spanning tree T and the robust deviation of T ,two fundamental concepts for this paper.

Figure 1.The relative worst case scenario determines the robust deviation ?T of a

given spanning tree T .Our goal is to ?nd a tree T ?for which this deviation (distance)is minimal.

De?nition 2.1(Relative worst case scenario).Given a spanning tree T ,a scenario w (T )which maximizes the difference between the cost of T and the cost of a mini-mum spanning tree under w (T )is called a relative worst case scenario for T .More precisely,a relative worst case scenario w (T )satis?es

w (T )∈arg-max s ∈S

(c s T ?c MST s )

(1)

where S is the set of all possible scenarios.Note that arg-max s ∈S f (s )denotes the set

{e ∈S |f (e )=max s ∈S

f (s )}.

and arg-min is de?ned similarly.

De?nition 2.2(Robust Deviation).The robust deviation

of a spanning tree T ,denoted by ?T ,is the distance be-tween the cost of T and the cost of a minimum spanning tree under the relative worst case scenario of T :

?T =c w (T )

T

?c MST w (T ).

(2)

The goal of this paper is to compute a robust spanning tree,i.e.,a spanning tree whose robust deviation is mini-mal.

De?nition 2.3(Robust Spanning Tree).A (relative)ro-bust spanning tree is a spanning tree T ?whose robust deviation is minimal,i.e.,

T ?∈arg-min T ∈ΓG max s ∈S

(c s T ?c MST s )

where ΓG is the set of all spanning trees of G and S is the set of all possible scenarios.According to the de?nition of w (T )(Eq.1),this is equivalent to:

T ?∈arg-min T ∈ΓG

(c w (T )

T

?c MST w (T )).

2

Figure 1depicts these concepts graphically.The horizon-tal axis depicts various scenarios.For each scenario s ,it shows the cost c s T of T under s and the cost c MST s of an MST under s .In the ?gure,scenario s 5is a worst-case

scenario,since the distance c s 5

T ?c MST s 5is maximal and

this distance is then the robust deviation of T .Such a ?g-ure can be drawn for each spanning tree and we are in-terested in ?nding the spanning tree with the smallest ro-bust deviation.[Kouvelis and Yu,1997]conjectured that the robust spanning tree problem with interval edges is NP-complete.3

Prior Work

[Yaman et al.,2001]proposed an elegant MIP formula-tion for the RSTPIE problem.The formulation combines the single commodity model of the minimum spanning tree with the dual of the multicommodity model for the same problem.In addition,they introduced the concept of weak and strong edges and used them for prepro-cessing.They showed that preprocessing signi?cantly enhances the performance of their MIP implementation.We now summarize their relevant results.

We ?rst introduce the concept of weak edges,i.e.,the only edges that need to be considered during the search.De?nition 3.1(Weak Tree).A tree T ?E is weak if there exists at least one scenario under which T is a minimum spanning tree of G .

De?nition 3.2(Weak Edge).An edge e ∈E is weak if it lies on at least one weak tree.

Strong edges are edges that are necessarily part of a ro-bust spanning tree.

De?nition 3.3(Strong Edge).An edge e ∈E is strong if it lies on a minimum spanning tree of G for all possible scenarios.

The following propositions characterize weak and strong edges in terms of the minimum spanning trees of two scenarios.

Proposition 3.4.An edge e ∈E is weak if and only if there exists a minimum spanning tree using edge e when its cost is at the lowest bound and the costs of the remaining edges are at their highest bounds.

Proposition 3.5.An edge e ∈E is strong if and only if there exists a minimum spanning tree using edge e when its cost is at the highest bound and the costs of the remaining edges are at their lowest bounds.

As a consequence,[Yaman et al.,2001]showed that it is possible to use a slightly modi?ed version of Kruskal’s algorithm to ?nd all the weak and strong edges of a given graph in O (m 2log m )time.In Section 6,we give an im-proved algorithm for ?nding weak edges,which runs in O (mlogm ).The following two propositions capture the intuition we gave earlier on weak and strong edges.

procedure Search ( S,R )begin

if |S |

S,R =P runeInfeasible ( S,R ); S,R =P runeSuboptimal ( S,R );if LB ( S,R )≤f ?then

e =SelectEdge (E \(S ∪R ));Search( S,R ∪{e } );Search( S ∪{e },R );

else

if ?S

T ?=S ;f ?=?S

end

Figure 2.The Search Algorithm

Proposition 3.6.A relative robust spanning tree T is a weak tree.Thus an edge can be part of a relative robust spanning tree only if it is a weak edge.

Proposition 3.7.There exists a relative robust tree T such that every strong edge in the graph lies on T.

The next result is also fundamental:it makes it possi-ble to characterize precisely the worst case scenario of a spanning tree T .

Proposition 3.8.The scenario in which the costs of all edges in a spanning tree T are at upper bounds and the costs of all other edges are at lower bounds is a relative worst case scenario for T .In other words,w (T )is speci?ed as

c w (T )e =

,e ∈E \T (3)

In other words,once we select a tree T ,we can easily ?nd the worst-case scenario for T by assigning to the edges in T their upper bounds and to the edges not in T their lower bounds.We use Proposition 3.8in our new algo-rithm.In the rest of the paper,we also use the notation w (S )to denote the scenario where c e =

otherwise even when S is not a tree.4

The Search Algorithm

Figure 2gives a high-level description of the search al-gorithm.A node in the search tree is called a con?gu-ration to avoid confusion with the nodes of the graph.A con?guration is a pair S,R ,where S represents the set of selected edges and R represents the set of rejected edges.The algorithm receives a con?guration as input.If the con?guration is not a spanning tree,the algorithm prunes infeasible and suboptimal edges.Both steps re-move edges from E \(S ∪R )and adds them to R .If the lower bound of the resulting con?guration is smaller than the best found solution,the algorithm selects an edge and explores two subproblems recursively.The

3

c s T the cost of tree T under scenario s

c s T=P e∈T c s e

w(T)worst case scenario for edge set T:

= ,e∈E\T

c w(T)

e

ΓG the set of all spanning trees of graph G T(S,R)the set of spanning trees derived from

S,R

T(S,R)={T∈ΓG|S?T?E\R} M s(S,R)the set of spanning trees from T(S,R)

with mimimal cost under scenario s

M s(S,R)=arg-min T∈T(S,R)c s T

MST s(S,R)an arbitrary tree from M s(S,R)

M s M s(?,?)

MST s an arbitrary tree from M s(?,?)

Proposition 6.1.Let s be a scenario and T ∈M s .Let e =(u,v )/∈T and f =(x,y )be the edge of maximal cost on the path from u to v .Consider ?s the scenario s where c s e is replaced

by c ?s e ,all other costs remaining the same.Then T ∈M ?s if c ?s e ≥c ?s f .

Proof:By contradiction.Assume that there exists a tree

T containing e such that c ?s T

s T .Removing e from T produces two connected components C 1and C 2.If x ∈C 1and y ∈C 2,then we can construct a tree

T =T \{e }∪{f }

and we have

c ?s T =c ?s T ?(c ?s e ?c ?s f )

Since e ∈T and e ∈T ,we have

c s T =c ?s T

T

which contradicts the fact that T ∈M s .If x,y ∈C 1(resp.C 2),since there exists a cycle in the graph containing e and f ,there exists at least one edge g on the path from u to v in T such that g ∈T (otherwise T would not be a

tree).By hypothesis,c s g ≤c s f and hence c ?s e ≥c ?

s g .We can thus apply the same construction as in the case x ∈C 1and y ∈C 2with f replaced by g .

Proposition 6.2.Let s be a scenario and T be an MST s .Let e =(u,v )/∈T and f =(x,y )be the edge of maximal cost on the path from u to v .Then,T \{f }∪{e }∈M s ({e },?).The proof of this result is similar to the proof of Proposi-tion 6.1.We are now ready to present a new characteri-zation of weak edges.The characterization only uses the scenario ˉs where all costs are at their upper bounds.Proposition 6.3.Let ˉs be the scenario where all costs are at

their upper bounds and T ∈M ˉ

s .An edge e =(u,v )is weak if e ∈T or if an edge f of maximal cost on the path from u to v in T satis?es c e c f .

Proof:Let ?s the scenario ˉs where c ˉs e is replaced by c ?

s e .If

e ∈T ,then T ∈M ?

s as well and hence e is weak by

Proposition 3.4.If e /∈T and c e

c f ,then T ∈M ?

s by Proposition 6.1.By Proposition 6.2,T \{f }∪{e }∈M ˉs ({e },?)and its cost is greater than c T since c e c f .Hence e is not weak.If e /∈T and c e c f ,then T \{f }∪

{e }is an MST ˉ

s and hence e is weak.The same holds for the case where e ∈T and c e c f .

We now describe how to use Proposition 6.3to obtain an O (m log m )algorithm on dense graphs.The key idea

is to compute MST ˉ

s ,i.e.,the MST when all costs are at their upper bounds.All edges in this MST are weak.In addition,for each e =(u,v )not in the MST,we com-pute the largest cost of any edge on the path from u to v .This can be done easily by upgrading Prim’s algorithm slightly to associate a level and a parent to each vertex.When an edge e =(u,v )with u ∈T and v /∈T is added to T in Prim’s algorithm,we set

function MaxCost(u ,v vertices):int

begin

if u =v then

return 0;

else if level (u )

return max(cost (v,p (v )),MaxCost(u ,p (v )));else if level (u )>level (v )then

return max(cost (u,p (u )),MaxCost(p (u ),v ));else

max

edge,MaxCost(p (u ),p (v )));

end

Figure 3.Finding the Largest Cost of an Edge

level(v)=level(u)+1;

parent(v)=u;

These modi?cations do not affect the complexity of the algorithm.It now suf?ces to apply the algorithm de-picted in Figure 3to compute the cost of the maxi-mal edge and to apply Proposition 6.3.The algorithm in Figure 3simply follows the paths from u and v to their common ancestor,computing the cost of the max-imal edge on the way.Since algorithm MaxCost takes O (n )in the worst case,the overall complexity becomes O (m log m +mn ).However,it is easy to reduce this complexity to O (m log m +n 2)by amortizing the com-putation of the maximal costs.It suf?ces to cache the results of MaxCost in an n ×n matrix M .For each edge e =(u,v )∈E \T we ?rst examine entry M [u,v ]and call MaxCost (u ,v )only if this entry is uninitialized.Since there are at most n 2entries and each call to MaxCost (u ,v )costs O (1)per entry it ?lls,the overall complexity com-plexity becomes O (m log m +n 2).We proved the follow-ing theorem.

Theorem 6.4.All weak edges of a graph can be computed in O (m log m +n 2)time.7

Branching Strategy

It is well-known that a good branching heuristic may improve performance signi?cantly.We now show a branching heuristic adapting the ?rst-fail principle [Haralick and Elliot,1980]to robust optimization.The key idea is to explore the most uncertain edges ?rst,i.e.,to branch on an edge e with the maximal difference

.Indeed,rejecting e (i.e.,adding e to R )allows MST w (S ∪L )

to select e at a low cost,possibly giving a large deviation.Hence this branch is likely to fail early.However,this is only important if MST w (S ∪L )is likely to select e which may not necessarily the case if c e

c e ?c e

Figure4.A Class7

Network

Figure5.A Class8Network

branching strategy.

De?nition7.1(Branching Strategy).Let S,R be a con-?guration,L?=L∩MST w(S∪L),and L?=L\ MST w(S∪L).The branching strategy selects an edge s de?ned as follows:

s= arg-max e∈L?if L?=?

arg-max e∈L?otherwise.

8Experimental Results

We now report experimental results comparing the constraint atisfaction and the MIP approaches.The com-parison uses the instances in[Yaman et al.,2001],as well as some new instances which capture additional struc-ture arising in practical applications.

The experimental setting of[Yaman et al.,2001]uses complete graphs with n vertices and six classes of prob-lems.Three of the six classes use tight intervals for edge costs,while the other three allowed larger differences be-tween the lower and upper bounds.The edge intervals were chosen as follows.The values of c e c e are uni-formly distributed in the intervals:

class1:c e c e∈(c e

∈[0,15],,15]

class3:c e c e∈(c e

∈[0,10],,20]

class5:c e c e∈(c e

∈[0,20],,40]

Note that the size of the search space to explore is O(2300) for a complete graph of25nodes.Of course,our con-straint satisfaction algorithm will only explore a small

fraction of that space.In addition to these six classes, we also generate instances(Classes7and8)whose cost structure is not the same for all the edges.Class7con-tains instances which represent a two-level network.The lower level consists of clusters of5nodes whose edges are generated according to Class1above.The upper level links the clusters and these edges have higher costs, i.e.,Class1costs shifted by a constant which is larger than the Class1edges.This captures the fact that,in net-works,there are often various types of edges with dif-ferent costs.See Figure4for an instance of Class7with 35nodes.Class8contains instances which are similar to Class7,except that the upper-level layer is organized as a binary tree.See Figure5for an instance of Class8with35 nodes.In general,classes7and8are signi?cantly harder than classes1to6,since preprocessing is less effective than in Classes1to6because of the additional structure. Observe also that these instances are sparser for the same number of nodes.

Table2compares the ef?ciency of the two approaches. It reports the computation times in CPU seconds of the MIP implementations,the constraint satisfaction algo-rithm with suboptimality pruning at the root node only (CSR),and the constraint satisfaction algorithm with suboptimality pruning at every node(CSF).The times are given on a Sun Sparc440Mhz processor and the av-erage is computed over10instances for each class and each size.We used CPLEX6.51for solving the MIP,after preprocessing of the weak and strong edges.

Observe that the constraint satisfaction approach produces extremely dramatic speedups over the MIP approach.On Class1,CSR runs about134times faster than the MIP on graphs with15nodes and about217times faster on graphs with20nodes.On Classes7and8,the speed-ups are even more impressive.On graphs with20nodes for classes7and8,CSR runs about3500and200times faster than the MIP.(Recall that these graphs are not com-plete).The MIP times are not given for graphs with more than20nodes,since they cannot be obtained in reason-able time.The results indicate that the constraint satis-faction approach is also better at exploiting the network structure,which is likely to be fundamental in practice. Observe also that the constraint satisfaction approach is able to tackle much large instances in reasonable times.

Figures6,7,and8plot the execution times of the two constraint satisfaction algorithms.Observe also that ap-plying suboptimality pruning at every node is not cost-effective on Classes1to6.This is due to the fact that the graphs are complete and the costs are uniformly dis-tributed in these instances.Classes7and8,which add a simple additional cost structure,clearly indicate that suboptimality pruning becomes increasingly important when the network is more heterogeneous.The bene?ts of suboptimality pruning clearly appears on large graphs for class8,where CSF is about three times as fast in the average.In fact,CSF is signi?cantly faster(e.g.,10times faster)than CSR on some instances,while the two algo-

6

Algo.Class1Class3Class5Class7 CSR0.120.080.060.06 CSF0.140.120.090.07 MIP 6.59 4.10 4.68 2.29 CSR 1.82 1.090.86 1.76 CSF 2.53 2.15 2.01 1.83 MIP245.19136.8891.33730.20 CSR39.728.91 2.097.37 CSF74.8612.66 4.69 5.28 MIP8620.6614385.5512862.2918547.27 CSR121.8568.4212.2391.89 CSF244.18145.1130.5597.94 CSR926.65942.3863.851719.61 CSF2100.431811.88167.58804.78 CSR4639.552304.36188.3632511.77 CSF10771.374183.22548.0114585.73 CSR27206.3815059.391122.5757309.23 CSF29421.7022084.003241.0428432.91

C P U s e c o n d s

Graph size - number of edges

Execution time for problems of class 8

Figure 8.Constraint Satisfaction on Class 8.

O (m log m )algorithm for detecting strong edges,to quantify the bene?ts of incremental MST algorithms,to investigate more sophisticated feasibility pruning,and to evaluate the approach on sparser graphs.Finally,it would be interesting to study whether suboptimal con-ditions can be derived for a wide variety of (robust)com-binatorial optimization problems given the ubiquity of these problems in practice.In particular,robust match-ing and robust shortest paths have fundamental appli-cations in computational ?nance and networks and are worth investigating.

Acknowledgments

Ionut Aron is supported by NSF ITR Award ACI-0121497.Pascal Van Hentenryck is partially supported by NSF ITR Award DMI-0121495.References

[Bertsimas and Sim,2002]Bertsimas,D.and Sim,M.(2002).Robust discrete optimization.Working Paper,Operations Research Center,MIT.[Birge and Louveaux,1997]Birge,J.and Louveaux,F.(1997).Intro-duction to stochastic programming.In Verlag,S.,editor,Springer Verlag Series in Operations Research ,New York.[Haralick and Elliot,1980]Haralick,R.and Elliot,G.(1980).Increas-ing tree search ef?ciency for constraint satisfaction problems.Arti?-cial Intelligence ,14:263–313.[Kouvelis and Yu,1997]Kouvelis,P .and Yu,G.(1997).Robust Discrete Optimization and Its Applications .Kluwer Academic Publishers.[Kozina and Perepelista,1994]Kozina,G.and Perepelista,V .(1994).Interval spanning tree problem:Solvability and computational com-plexity.Interval Computing ,1:42–50.[Rauch et al.,1997]Rauch,Henzinger,M.,and V .,K.(1997).Maintain-ing minimum spanning trees in dynamic graphs.In Proceedings of the 24th International Colloquim on Automata,Languages and Programming (ICALP 1997),pages 594–605.[Walsh,2001]Walsh,T.(2001).Stochastic constraint programming.In AAAI Fall Symposium on Using Uncertainty within Computation .[Yaman et al.,2001]Yaman,H.,Karasan,O.E.,and Pinar,M.C.(2001).The robust spanning tree problem with interval data.Operations Re-search Letters ,29:31–40.

8

关于颜色的英语单词

关于颜色的英语单词: blue蓝色 green绿色 purple紫色 yellow黄色 red红色 pink粉红色 palegoldenrod 苍麒麟色palegreen 苍绿色 paleturquoise 苍绿色palevioletred 苍紫罗蓝色 pansy 紫罗兰色 papayawhip 番木色 peachpuff 桃色 peru 秘鲁色 pink 粉红色 salmon pink 橙红色 baby pink 浅粉红色 shocking pink 鲜粉红色 brown 褐色, 茶色 beige 灰褐色 chocolate 红褐色, 赭石色 sandy beige 浅褐色 camel 驼色 amber 琥珀色 khaki 卡其色 maroon 褐红色 green 绿色 moss green 苔绿色 emerald green 鲜绿色 olive green 橄榄绿 blue 蓝色 turquoise blue 土耳其玉色 cobalt blue 钴蓝色, 艳蓝色 navy blue 藏青色, 深蓝色, 天蓝色aquamarine blue 蓝绿色 red 红色 scarlet 绯红, 猩红 mauve 紫红 wine red 葡萄酒红 purple, violet 紫色 lavender 淡紫色

lilac 浅紫色 antique violet 古紫色pansy 紫罗兰色 white 白色 off-white 灰白色 ivory 象牙色 snowy white 雪白色oyster white 乳白色gray 灰色 charcoal gray 炭灰色smoky gray 烟灰色misty gray 雾灰色 plum 杨李色powderblue 粉蓝色purple 紫色 red 红色 rosybrown 褐玫瑰红royalblue 宝蓝色rubine 宝石红saddlebrown 重褐色salmon 鲜肉色salmon pink 橙红色sandy beige 浅褐色sandybrown 沙褐色sapphire 宝石蓝scarlet 猩红色seagreen 海绿色seashell 海贝色shocking pink 鲜粉红色sienna 赭色 silver 银白色 skyblue 天蓝色slateblue 石蓝色slategray 灰石色smoky gray 烟灰色snow 雪白色springgreen 春绿色steelblue 钢蓝色 stone 石色 tan 茶色 teal 水鸭色 thistle 蓟色 tomato 番茄色

颜色的英语单词大全

颜色的英语单词大全1 一.红色类 红色 red 朱红 vermeil; vermilion; ponceau 粉红 pink; soft red; rose bloom 梅红 plum;crimson;fuchsia red 玫瑰红 rose madder; rose 桃红 peach blossom; peach; carmine rose 樱桃红 cherry; cerise 桔红 reddish orange; tangerine; jacinth; salmon pink; salmon 石榴红 garnet 枣红 purplish red; jujube red; date red 莲红 lotus red 浅莲红 fuchsia pink 豉豆红 bean red 辣椒红 capsicum red 高粱红 Kaoliang red 芙蓉红 hibiscus red; poppy red; poppy 胭脂红 rogue red ; carmine; cochineal; lake 鲑鱼红 salmon 玳瑁红 hawksbill turtle red 海螺红 cadmium orange 宝石红 ruby red 玛瑙红 agate red 珊瑚红 coral 金红 bronze red 铁红 iron oxide red 铁锈红 rust red 镉红 cadmium red 铬红 chrome red 砖红 brick red 土红 laterite; reddle 郎窑红 lang-kiln red 均红 Jun-kiln red 釉底红 underglaze red 威尼斯红 Venetian red 法国红 French vermilion 茜红 alizarin red; madder red 洋红 carmine; magenta 品红 pinkish red; magenta 猩红 scarlet red; scarlet; blood red 油红 oil red 紫红 purplish red; madder red; wine red; wine; carmine;amaranth; claret;

关于颜色的英语单词大全

关于颜色的英语单词大全 red红色 silver 银 sand 沙子色 gunmetal 青铜色 stone浅橄榄灰色 D/melange 米灰色 cream米黄色 coffee咖啡色 wine酒红色 gold金 yellow 黄色 black黑色 olive橄榄色 pink粉红色 anti gold 古铜色 natural 自然色 peach 桃色 daffod 水仙黄 coral 珊瑚色

gilt 青铜色 pewter蓝灰色 turq 湖水蓝 bronze 红古铜色fuchsia 粉玫色 pistac 淡黄绿色rainbow 彩虹色shocking red 憬红色pink 粉红色 salmon pink 橙红色baby pink 浅粉红色shocking pink 鲜粉红色brown 褐色, 茶色 beige 灰褐色chocolate 红褐色, 赭石色sandy beige 浅褐色camel 驼色 amber 琥珀色 khaki 卡其色 maroon 褐红色 green 绿色 moss green 苔绿色

emerald green 鲜绿色 olive green 橄榄绿 blue 蓝色 turquoise blue 土耳其玉色cobalt blue 钴蓝色, 艳蓝色 navy blue 藏青色, 深蓝色, 天蓝色aquamarine blue 蓝绿色 scarlet 绯红, 猩红 mauve 紫红 wine red 葡萄酒红 purple, violet 紫色 lavender 淡紫色 lilac 浅紫色 antique violet 古紫色 pansy 紫罗兰色 white 白色 off-white 灰白色 ivory 象牙色 snowy white 雪白色 oyster white 乳白色 gray 灰色 charcoal gray 炭灰色

选修六unit1词汇检测

UNIT1 Ⅰ.重点单词 1.______________ adj.抽象的;深奥的n.摘要 2.______________n.雕塑 3.______________ n.目标;目的v i.& v t.瞄准;(向某方向)努力 4.______________ adj.卓越的;杰出的;极好的 5.______________n.技术;方法;技能 6.______________ n.巧合(的事);(事情、口味、故事等)相合 7.______________ n.阴影;影子 8.______________ adj.荒谬的;可笑的 9.______________ adj.争论的;争议的 10.______________n.努力;尝试;企图v t.尝试;企图 11.______________ n.信任;信心;信念→______________ adj.忠诚的→______________ad v.忠实地① 12.______________adj.常规的;传统的;因循守旧的→______________ n.传统② 13.______________ adj.典型的;有代表性的→______________ n.类型 14.______________ adj.明显的;明白的→______________ n.证据③ 15.______________ v t.采用;采纳;收养→______________n.采用;收养④ 16.______________v t.拥有;具有;支配→______________n.拥有;(尤作复数)所有17.______________ v t.预言;预告;预测→______________ n.预告;预言 Ⅱ.核心短语 1.______________ 巧合地 2.______________ 大量 3._____________ _ (可是)另一方面 4._____________ _以一种更加现实的方式 5.____________ __ 集中精力于…… 6.____________ _ _导致;通向;通往 7._____________ _ 逃脱;摆脱;脱离 Ⅰ.重点单词 1.______________ adj.确切的;特定的 2.______________n.画像;身材;数字 3.______________ v t.雕刻;刻记 4.______________ adj.脆弱的;容易生病的;精致的

超完整颜色英语词汇大全

超完整颜色英语词汇大全 一.红色类 红色 red 朱红 vermeil; vermilion; ponceau 粉红 pink; soft red; rose bloom 梅红 plum;crimson;fuchsia red 玫瑰红 rose madder; rose 桃红 peach blossom; peach; carmine rose 樱桃红 cherry; cerise 桔红 reddish orange; tangerine; jacinth; 石榴红 garnet 枣红 purplish red; jujube red; date red 莲红 lotus red 浅莲红 fuchsia pink 豉豆红 bean red 辣椒红 capsicum red 高粱红 Kaoliang red 芙蓉红 hibiscus red; poppy red; poppy 胭脂红 rogue red ; carmine; cochineal; lake 鲑鱼红 salmon

玳瑁红 hawksbill turtle red 海螺红 cadmium orange 宝石红 ruby red 玛瑙红 agate red 珊瑚红 coral 金红 bronze red 铁红 iron oxide red 铁锈红 rust red 镉红 cadmium red 铬红 chrome red 砖红 brick red 土红 laterite; reddle 郎窑红 lang-kiln red 均红 Jun-kiln red 釉底红 underglaze red 威尼斯红 Venetian red 法国红 French vermilion 茜红 alizarin red; madder red 洋红 carmine; magenta 品红 pinkish red; magenta 猩红 scarlet red; scarlet; blood red 油红 oil red

颜色英语的大全

颜色英语大全 red红色 silver 银 sand 沙子色gunmetal 青铜色stone浅橄榄灰色 D/melange 米灰色cream米黄色 coffee咖啡色 wine酒红色 gold金 yellow 黄色 black黑色 olive橄榄色 pink粉红色 anti gold 古铜色natural 自然色peach 桃色 daffod 水仙黄 coral 珊瑚色 gilt 青铜色 pewter蓝灰色 turq 湖水蓝 bronze 红古铜色fuchsia 粉玫色pistac 淡黄绿色rainbow 彩虹色shocking red 憬红色pink 粉红色 salmon pink 橙红色baby pink 浅粉红色shocking pink 鲜粉红色 brown 褐色, 茶色beige 灰褐色chocolate 红褐色, 赭石色 sandy beige 浅褐色camel 驼色 amber 琥珀色 khaki 卡其色maroon 褐红色 green 绿色 moss green 苔绿色 emerald green 鲜绿色 olive green 橄榄绿 blue 蓝色 turquoise blue 土耳其 玉色 cobalt blue 钴蓝色, 艳 蓝色 navy blue 藏青色, 深 蓝色, 天蓝色 aquamarine blue 蓝绿 色 scarlet 绯红, 猩红 mauve 紫红 wine red 葡萄酒红 purple, violet 紫色 lavender 淡紫色 lilac 浅紫色 antique violet 古紫色 pansy 紫罗兰色 white 白色 off-white 灰白色 ivory 象牙色 snowy white 雪白色 oyster white 乳白色 gray 灰色 charcoal gray 炭灰色 smoky gray 烟灰色 misty gray 雾灰色 BABY BLUE 浅蓝 TIGERLILY 橘红 STORM 雾灰 WINTER SKY 天蓝 VAPOR BLUE 烟灰 OYSTER GREY 米灰 JESTER RED 大红 CANDY PINK 粉红 JAFFA ORANGE 橘黄 pale taupe 浅灰褐色 cracker khaki 杏色 tulip yellow 黄色 thirsty blue 浅蓝色 green mint 浅绿 banana cream 香蕉黄 Acid blue 湖色 Amber 琥珀色 Amethyst 紫水晶色 Antique 古紫色 Apple green 苹果绿 Apricot 杏黄 Aqua green 水绿色 Aquamarine blue 蓝绿 色 Auburn 赤褐色 Azure green 碧绿色 Bay 枣色 Baby blue 浅蓝色 Baby pink 浅粉红色 Beige 灰棕色 Benzo blue 靛蓝色 Black 黑色 Blue 蓝色 Blue green 竹青色 Blue grey 蓝灰色 Bluish white 青白色 Bluish yellow 青黄色 Brick red 青莲色 Bronze black 射光黑色 Bronze blue 射光绀蓝 Bronze violet 射光紫蓝 Brown 棕色 Buff 浅黄色 Calamine blue 淡蓝色 Caramel 酱色 Cardinal 深红色 Carmine 紫红色 Carnation 肉色 Celeste 天青色 Chalky 白垩 Charcoal grey 炭灰色 Cherry 樱桃红 Chestnut 栗褐色

英语常用的颜色单词

英语常用的颜色单词 英语中有red(红),white(白),black(黑),green(绿),yellow(黄),blue(蓝),purple(紫),gray(灰),brown(棕)。 beige 米色 black 黑色 brown 咖啡色 cream 雪白 khaki 卡其色 grey 灰色 navy 丈青色 offwhite 灰白色 palegoldenrod 苍麒麟色 palegreen 苍绿色 paleturquoise 苍绿色 palevioletred 苍紫罗蓝色 pansy 紫罗兰色 papayawhip 番木色 peachpuff 桃色 peru 秘鲁色 pink 粉红 plum 杨李色 powderblue 粉蓝色 purple 紫色

red 红色 rosybrown 褐玫瑰红royalblue 宝蓝色rubine 宝石红saddlebrown 重褐色salmon 鲜肉色salmon pink 橙红色sandy beige 浅褐色sandybrown 沙褐色sapphire 宝石蓝scarlet 猩红色seagreen 海绿色seashell 海贝色shocking pink 鲜粉红色sienna 赭色 silver 银白色 skyblue 天蓝色slateblue 石蓝色slategray 灰石色smoky gray 烟灰色snow 雪白色springgreen 春绿色

steelblue 钢蓝色stone 石色 tan 茶色 teal 水鸭色 thistle 蓟色 tomato 番茄色turquoise 青绿色turquoise blue 翠蓝色violet 紫色 wheat 浅黄色 white 白色 wheat 土黄色whitesmoke 烟白色winered 葡萄酒红yellow 黄色yellowgreen 黄绿色

超完整颜色英语词汇大全

超完整颜色英语 词汇大全 一.红色类 红色red 朱红vermeil; vermilion; ponceau 粉红pink; soft red; rose bloom 梅红plum;crimson;fuchsia red 玫瑰红rose madder; rose 桃红peach blossom; peach; carmine rose 樱桃红cherry; cerise 桔红reddish orange; tangerine; jacinth; 石榴红garnet 枣红purplish red; jujube red; date red 莲红lotus red 浅莲红fuchsia pink 豉豆红bean red 辣椒红capsicum red 高粱红Kaoliang red 芙蓉红hibiscus red; poppy red; poppy 胭脂红rogue red ; carmine; cochineal; lake

鲑鱼红salmon

玳瑁红hawksbill turtle red 海螺红cadmium orange 宝石红ruby red 玛瑙红agate red 珊瑚红coral 金红 bronze red 铁红iron oxide red 铁锈红 rust red 镉红cadmium red 铬红chrome red 砖红brick red 土红laterite; reddle 郎 窑红lang-kiln red 均红Jun-kiln red 釉底 红underglaze red 威尼斯红Venetian red 法国红French vermilion 茜红 alizarin red; madder red 洋红carmine; magenta 品红pinkish red; magenta 猩红 scarlet red; scarlet; blood red 紫红purplish red; madder red; wine red; 玫瑰紫红rose carmine; rose mauve 深紫红prune; mulberry 深藕红conch shell 棕红henna 暗红dark red; dull red 鲜红scarlet red; scarlet; bright red; 血红blood red; incarnadine 血牙红shell pink; peach beige 绯红scarlet; crimson; geranium pink 米红silver pink 深红deep red; crimson 淡红light red; carnation 油红oil red

高中英语《satisfaction guaranteed》优质课教案、教学设计

【教学流程设计】 环节一。热身运动,导入主题 Enjoy a group of pictures of robots, and discuss their usage. (industrial robots and household robots) The teacher shows the pictures and students guess what they are, what they do and give their opinions. 追问:What is special about Asimove’s robot? Do you think it’s possible for a human-like robot to have feelings? And would it be possible for a human to fall in love with robots? (设计意图)因为这是一个关于机器人的故事,所以在导入部分自然 地用机器人的话题导入。在图片部分,展示了工业用机器人和家庭用机 器人甚至最近几年出现的仿真机器人伴侣等。这些机器人引起了学生的 极大兴趣,并且在机器人伴侣这个环节,提问学生这样的机器人是否有 情感,人类是否会爱上这种仿真机器人伴侣,这与阅读内容相呼应。 环节二。阅读前两段,回答三个问题 1.Why did the couple bring a household robot in their house? 2.What attitude did Claire take towards the idea that the robot would go to their house? Why? 3.How did Claire feel at the sight of Tony? Why? (设计意图)了解故事发生的背景及女主人公初次听到消息和初次看 到机器人的态度,这也为后面处理女主人公感情变化这条主线做好铺垫。尤其是第二个问题的后半问句“在男主人公不在家的三个周期间女主人

satisfaction guaranteed2018年4月公开课 教学教案及反思

Unit2 Teaching plan: Satisfaction Guaranteed Teaching Aims: 1. Talk about robots 2. Get to know a short story about robot 3. Learn words used to describe people’s feeling 4. Practice reading skill: scanning(careful-reading) Teaching important and difficult points: 1. Learn words used to describe people’s feeling 2. Practice reading skill: scanning(careful-reading) Teaching steps: Step1. lead-in and Aims 1).Look at some pictures and answer questions 2). Revise the contents of skimming(fast-reading) in the last period. Step2. Self-study and Exercise Do some scanning(careful-reading) and then finish the tasks: Task1、How Claire’s Feelings change to Tony? Task2、Change them into Scene Play with your partners, and then show them to us. Step3. Explanation The show time to the scene play Filling: The Change of Claire’s Feelings to Tony in each occasion O1、 O2、When he arrived----- O3、 When he offered to help her dressing-- O4 、When he offered sympathy to her when she said she was not clever O5 、When he offered to help her improve her--- house and herself O6、When he helped her with the--- salesman O7、 caught by Tony O8、When she heard Gladys whispering to another -- woman that she had never seen anyone so Handsome as Tony O9、 Step4: Conclusion 1).Ending of story What is the result of the test?Is it perfect? Claire _______ all night. Tony was taken away, and he would have to be______. The company was very _____ with Tony’s report . 2). Summary

颜色单词大全

颜色单词大全 1. amber 琥珀色 2. antique violet 古紫色 3. antiquewhite 古董白 4. aqua 浅绿色 5. aquamarine 碧绿色 6. azure 天蓝色 7. baby pink 浅粉红色 8. beige 米色 9. bisque 橘黄色 10. black 黑色 11. blanchedalmond 白杏色 12. blue 蓝色 13. blueviolet 紫罗兰色 14. brown 棕色 15. burlywood 实木色 16. cadetblue 军蓝色 17. camel 驼色 18. charcoal gray 炭灰色 19. chartreuse 黄绿色 20. chocolate 巧克力色 21. cobalt blue 艳蓝色 22. coral 珊瑚色 23. cornflowerblue 菊蓝色 24. cornsilk 米绸色 25. crimson 暗深红色 26. cyan 青色 27. darkblue 暗蓝色 28. darkcyan 暗青色 29. darkgoldenrod 暗金黄色 30. darkgray 暗灰色 31. darkgreen 暗绿色 32. darkkhaki 暗卡其色 33. darkmagenta 暗洋红色 34. darkolivegreen 暗橄榄绿色 35. darkorange 暗桔色 36. darkorchid 暗紫色 37. darkred 暗红色 38. darksalmon 暗肉色 39. darkseagreen 暗海蓝色 40. darkslateblue 暗灰蓝色 41. darkslategray 墨绿色 42. darkturquoise 暗宝石绿 43. darkviolet 暗紫色 44. deeppink 深粉色 45. deepskyblue 深天蓝色 46. dimgray 暗灰色 47. dodgerblue 闪蓝色 48. emerald green 艳绿色 49. firebrick 火砖色 50. floralwhite 花白色 51. forestgreen 森林绿 52. fuchsia 紫红色 53. gainsboro 淡灰色 54. ghostwhite 幽灵白 55. gold 金黄色 56. goldenrod 金麒麟色 57. gray 灰色 58. green 绿色 59. greenyellow 黄绿色 60. honeydew 蜜色 61. hotpink 艳粉色 62. indianred 印第安红 63. indigo 靛蓝色 64. ivory 象牙色 65. khaki 卡其色 66. lavender 淡紫色 67. lavenderblush 淡紫红 68. lawngreen 草绿色69. lemonchiffon 柠檬绸色 70. lightblue 浅蓝色 71. lightcoral 浅珊瑚色 72. lightcyan 浅青色 73. lightgoldenrodyellow 浅金黄 色 74. lightgreen 浅绿色 75. lightgrey 浅灰色 76. lightpink 浅粉色 77. lightsalmon 浅肉色 78. lightseagreen 浅海蓝色 79. lightskyblue 浅天蓝色 80. lightslategray 浅蓝灰色 81. lightsteelblue 浅钢蓝色 82. lightyellow 浅黄色 83. lilac 浅紫色 84. lime 酸橙色 85. limegreen 橙绿色 86. linen 亚麻色 87. magenta 洋红色 88. maroon 栗色 89. mauve 紫红 90. mediumaquamarine 间绿色 91. mediumblue 间蓝色 92. mediumorchid 间紫色 93. mediumpurple 间紫色 94. mediumseagreen 间海蓝色 95. mediumslateblue 间暗蓝色 96. mediumspringgreen 间春绿 色 97. mediumturquoise 间绿宝石 色 98. mediumvioletred 间紫罗兰色 99. midnightblue 中灰蓝色 100. mintcream 薄荷色 101. misty gray 雾灰色 102. mistyrose 浅玫瑰色 103. moccasin 鹿皮色 104. moss green 苔绿色 105. navajowhite 纳瓦白 106. navy 藏青 107. off-white 灰白 108. oldlace 老花色 109. olive 橄榄色 110. olivedrab 深绿褐色 111. orange 橙色 112. orangered 橙红色 113. orchid 淡紫色 114. oyster white 乳白色 115. pink 粉红色 116. salmon pink 橙红色 117. baby pink 浅粉红色 118. shocking pink 鲜粉红色 119. brown 褐色, 茶色 120. beige 灰褐色 121. chocolate 红褐色, 赭石色 122. sandy beige 浅褐色 123. camel 驼色 124. amber 琥珀色 125. khaki 卡其色 126. maroon 褐红色 127. green 绿色 128. moss green 苔绿色 129. emerald green 鲜绿色 130. olive green 橄榄绿 131. blue 蓝色 132. turquoise blue 土耳其玉色 133. cobalt blue 钴蓝色, 艳蓝色 134. navy blue 藏青色, 深蓝色, 天蓝色 135. aquamarine blue 蓝绿色 136. red 红色 137. scarlet 绯红, 猩红 138. mauve 紫红 139. wine red 葡萄酒红 140. purple, violet 紫色 141. lavender 淡紫色 142. lilac 浅紫色 143. antique violet 古紫色 144. pansy 紫罗兰色 145. white 白色 146. off-white 灰白色 147. ivory 象牙色 148. snowy white 雪白色 149. oyster white 乳白色 150. gray 灰色 151. charcoal gray 炭灰色 152. smoky gray 烟灰色 153. misty gray 雾灰色 154. palegoldenrod 苍麒麟色 155. palegreen 苍绿色 156. paleturquoise 苍绿色 157. palevioletred 苍紫罗蓝色 158. pansy 紫罗兰色 159. papayawhip 番木色 160. peachpuff 桃色 161. peru 秘鲁色 162. pink 粉红 163. plum 杨李色 164. powderblue 粉蓝色 165. purple 紫色 166. red 红色 167. rosybrown 褐玫瑰红 168. royalblue 宝蓝色 169. rubine 宝石红 170. saddlebrown 重褐色 171. salmon 鲜肉色 172. salmon pink 橙红色 173. sandy beige 浅褐色 174. sandybrown 沙褐色 175. sapphire 宝石蓝 176. scarlet 猩红色 177. seagreen 海绿色 178. seashell 海贝色 179. shocking pink 鲜粉红色 180. sienna 赭色 181. silver 银白色 182. skyblue 天蓝色 183. slateblue 石蓝色 184. slategray 灰石色 185. smoky gray 烟灰色 186. snow 雪白色 187. springgreen 春绿色 188. steelblue 钢蓝色 189. stone 石色 190. tan 茶色 191. teal 水鸭色 192. thistle 蓟色 193. tomato 番茄色 194. turquoise 青绿色 195. turquoise blue 翠蓝色 196. violet 紫色 197. wheat 浅黄色 198. white 白色 199. whitesmoke 烟白色 200. winered 葡萄酒红 201. yellow 黄色 202. yellowgreen 黄绿色

satisfaction guaranteed

Larry Belmont worked for a company that made robots. Recently it had begun experimenting with a household robot. It was going to be tested out by Larry’s wife, Claire. Claire didn’t want the robot in her house, especially as her husband would be absent for three weeks, but Larry persuade her or allow her to be harmed. It would be a bonus. However, when she first saw the robot, she felt alarmed. His name was Tony and he seemed more like a human than a machine. He was tall and handsome with smooth hair and a deep voice although his facial expression never changed. On the second morning Tony, wearing an apron, brought her breakfast and then asked her whether she needed help dressing. She felt embarrassed and quickly told him to go. It was disturbing and frightening that he looked so human. One day, Claire mentioned that she didn’t think she was clever. Tony said that she must feel very unhappy to say that. Claire thought it was ridiculous to be offered sympathy by a robot. But she began to trust him. She told him how she was overweight and this made her feel unhappy. Also she felt her home wasn’t elegant enough for someone like Larry who wanted to improve his social position. She wasn’t like Gladys Claffern, one of the richest and most powerful women around. As a favor Tony promised to help Claire make herself smarter and her home more elegant. So Claire borrowed a pile of books from the library for him to read, or rather, scan. She looked at his fingers with wonder as they turned each page and suddenly reached for his hand. She was amazed by his fingernails and the softness and warmth of his skin. How absurd, she thought. He was just a machine. Tony gave Claire a new haircut and changed the makeup she wore. As he was not allowed to accompany her to the shops, he wrote out a list of items for her. Claire went into the city and bought curtains, cushions, a carpet and bedding. Then she went into a jeweler shop to buy a necklace. When the clerk at the counter was rude to her, she rang Tony up and told the clerk to speak to him. The clerk immediately changed his attitude. Claire thanked Tony, telling him that he was a “dear”.As she turned around, there stood Gladys Claffern. How awful to be discovered by her, Claire thought. By the amused and surprised look on her face, Claire knew that Gladys thought she was having an affair. After all, she knew Claire’s husband name was Larry, not Tony. When Claire got home, she wept with anger in her armchair. Gladys was everything Claire wanted to be.“You can be like her”,Tony told her and suggested that she invite Gladys and her friends to the house the night before he was to leave and Larry was to return. By that time, Tony expected the house to be completely transformed. Tony worked steadily on the improvements. Claire tried to help once but was too clumsy. She fell off a ladder and even though Tony was in the next room, he managed to catch her in time. He held her firmly in his arms and she felt the warmth of his body. She screamed, pushed him away and ran to her room for the rest of the day. The night of the party arrived. The clock struck eight. The guests would be arriving soon and Claire told Tony to go into another room. At that moment, Tony

关于颜色的英语单词大全

关于颜色的英语单词大 全 集团文件版本号:(M928-T898-M248-WU2669-I2896-DQ586-M1988)

关于颜色的英语单词大全red红色 silver 银 sand 沙子色 gunmetal 青铜色 stone浅橄榄灰色 D/melange 米灰色 cream米黄色 coffee咖啡色 wine酒红色 gold金 yellow 黄色 black黑色 olive橄榄色 pink粉红色 anti gold 古铜色 natural 自然色

peach 桃色 daffod 水仙黄 coral 珊瑚色 gilt 青铜色 pewter蓝灰色 turq 湖水蓝 bronze 红古铜色fuchsia 粉玫色 pistac 淡黄绿色rainbow 彩虹色shocking red 憬红色pink 粉红色 salmon pink 橙红色baby pink 浅粉红色shocking pink 鲜粉红色brown 褐色, 茶色 beige 灰褐色

chocolate 红褐色, 赭石色 sandy beige 浅褐色 camel 驼色 amber 琥珀色 khaki 卡其色 maroon 褐红色 green 绿色 moss green 苔绿色 emerald green 鲜绿色 olive green 橄榄绿 blue 蓝色 turquoise blue 土耳其玉色 cobalt blue 钴蓝色, 艳蓝色 navy blue 藏青色, 深蓝色, 天蓝色aquamarine blue 蓝绿色 scarlet 绯红, 猩红 mauve 紫红

相关主题
文本预览
相关文档 最新文档