Combinatorial Optimization

• Problem: Given a state space and a scoring function, find the state with maximum score
• Examples: office furniture layout, word chains
• Algorithms: search, A*, simulated annealing

eat $\rightarrow$pat $\rightarrow$pit $\rightarrow$lit $\rightarrow$lil $\rightarrow$ail $\rightarrow$all $\rightarrow$ale $\rightarrow$ate eat $\rightarrow$ear $\rightarrow$err $\rightarrow$ere $\rightarrow$are $\rightarrow$ate