第十讲 最短路模型
（教材：第十章 最短路模型）
2.人、狗、鸡、米过河问题(问题详见教材
)
建立最短路模型求解这一问题的详细过程可参见教材
。
下面对书上的这一解题过程做几点补充说明。
(1) 根据题意“当人不在时，狗要吃鸡，鸡要吃米”来确定哪些状态是可取的，哪些状态是不可取的。先讨论人不在此岸，即人在对岸时的情况，人在此岸时的情况可以与人在对岸的情况一一对应给出。人在对岸时共有8种不同的状态，分别为(0,0,0,0)、(0,1,0,0)、(0,1,1,0)、(0,1,1,1)、(0,1,0,1)、(0,0,1,0)、(0,0,1,1)和(0,0,0,1)。根据题意，人不在时，狗和鸡不能在一起，鸡和米不能在一起，故(0,1,1,0)、(0,1,1,1)和(0,0,1,1)不可取。剩下的五种状态可取，对应于这五种状态可得人在对岸时的五种状态。由此得本问题的十种可取状态，得教材
上的表格。
(2) 由题意“除船需要人划外，最多只能载一物过河”可知，转移向量只能是(1,1,0,0)、(1,0,1,0)、(1,0,0,1)和(1,0,0,0)四种。上述每种转移向量称为可取转移。
(3) 用点表示每种可取状态，将10个可取状态用10个点表示。确定两个点之间是否有边连接的原则是：对应的两个可取状态之间存在一个可取转移时，这两个点之间有边连接。例如：点
和 
之间的转移向量为(1,1,0,0)，是个可取转移，故这两点之间有边连接；而点 
和 
之间的转移向量为(1,0,1,1)，此转移不可取，故这两点之间没有边连接。由此可以构成一个图
(教材
图10.5)。如图红色线表示一条最短路，数字为从开始到该状态的最短路的长度（视每一步长度为一）。
3.中心选址问题
（问题详见教材
的例 4 和例 5。）
注意此处的目标是“使大家都方便”。因而可以取拟建学校的居民区到各居民区的最长距离作为衡量这个方案优劣的指标，把问题转变为，求一个使该指标最小的居民区建校。