一、农夫带狼、羊、菜过河
状态：农夫、狼、羊、菜都在河的左岸。
初始状态：农夫未带任何东西到右岸。
后继函数：农夫带羊过河，接着带菜过河，又带羊回来，带狼过河，最后又带羊过河。
目标测试：农夫、狼、羊、菜都在河的右岸。
路径耗散：从左岸到右岸算一步，从右岸到左岸亦算一步，故路径耗值为7步。
二、最优路径
状态：起始点在A点，其点它均未被访问。
初始状态：将起始A点加入已访问集，其它点标志为未被访问。
后继函数：用最小生成树普里姆算法遍历所有结点，遍历完成后获得最优路径；最后做一步特殊处理,将最后一个结点联入A，并加上权值。
目标测试：所有城市均只被访问一次且回到A城。
路径消费：每一步的耗值为1，因此整个路径的耗散值是路径中的步数。
原文：http://www.cnblogs.com/zhoulide/p/4366805.html