渡河问题一个人带了一只狼、一只山羊和一棵白菜想要渡河。河上有一只独木船,每次除人外只能带一样东西,另外如果人不在时狼就要吃山羊,羊就要吃白菜。问应该怎样安排渡河,
才能做到既把所有东西都带过河,而且在河上来回的次数又最少?
设 M代表人,W代表狼,S代表山羊,V代表白菜。
渡河问题算法思想:
用集合表示在某岸上的所有情况( 16种):
[MWSV] [MWS] [MWV] [MSV] [WSV] [MW]
[MS] [MV] [WS] [WV] [SV] [M] [S]
[V] [空 ]
剩下的 10种情况,按若甲经过一次渡河可变成乙,
那么就在甲与乙之间连一条边,由此得到如下图 G:
MWSV MWS MWV MSV MS
MS W S V 空结论,在 G中找一条连接顶点 MWSV与空,并且包含边数最少的路,