狼和羊的故事

Question

因为离散考试前与老师的争论都已经忘的差不多了,所以我重新构造方法.基本上是以字符串匹配的方法来解决这个问题.如图:
此岸  河 彼岸
人    (( 空
羊    )) 空
狼    (( 空
菜    )) 空这是开始的情况.设M=人(Men),G=羊(Goat),W=狼(Wolf),C=菜(Cabbage),0=空.
把此岸和彼岸的对象使用字符串的形式按顺序记录下来:
则开始的情况是:MGWC0000.
我要求各个对象在此岸和彼岸的位置必须一一对应,如人在此岸,字符串应该是M***0***,人走到彼岸,字符串只能是0***M****,而不能是0****M**,0*****M*或者0******M.
因此可能的字符串的个数是2^4=16.如下:
1.MGWC0000
2.0GWCM000
3.M0WC0G00
4.MG0C00W0
5.MGW0000C
6.00WCMG00
7.0G0CM0W0
8.0GW0M00C
9.M00C0GW0
10.M0W00G0C
11.MG0000WC
12.000CMGW0
13.00W0MG0C
14.0G00M0WC
15.0GWCM000
16.0000MGWC
这样问题变得明朗了,只要稍微加上一些规则,让MGWC0000(字符串1)变化到0000MGWC(字符串16),并且记录下来的变化过程就是可能的解法,使用巧妙的数据结构来防止重复道路,就可以找到最短路了.回顾一下dijkstra最短路算法,它是一种典型的贪心(Greedy)技术,在寻找最短路中,它从所有可能性出发,求极小值群,然后再在极小值群中找到最小值.同时还利用已知的规则和条件来约束计算的复杂度.这些都是贪心的.同类的问题,不一定要画出路或者树图,只要使用到上述的思想,就可以算作dijkstra算法了.(怀疑)下面来制定这个狼和羊的故事的规则:
1,根据羊和狼或者和菜不可共存的要求,凡含有0GWC,0G0C,0GW0的字符串均不合理,在搜索解法的过程中应该舍去.
2,从此岸到彼岸的运送,可以看成一个交换的过程,只允许下面的交换发生:
去→
M0
MG
MW
MC
回←
MG
MW
MC
M0
去表示从此岸到彼岸,回表示从彼岸回此岸.

Answer 1

下面使用c#语言来实现解法.其中为了防止道路的重复,使用字符串数组来记录走过的路,每走下一步,就要和数组中已经记录的字符串比较,看有没有重复,如果有,就舍弃下一步,没有的话,说明找到了一条路,继续.
当一个字符串与其他多个字符串有路的时候,按照广度优先搜索的思想,把可行的可能的字符串都记录到一个队列里,进行出队操作,选择其中一个字符串寻找下一步.using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;
namespace wolfandgoat
{
/// <summary>
/// Form1 的摘要说明。
/// </summary>
public class Form1 : System.Windows.Forms.Form
{
private System.Windows.Forms.RichTextBox textout;
private System.Windows.Forms.Button button1;
private System.Windows.Forms.Button button2;
/// <summary>
/// 必需的设计器变量。
/// </summary>
/// 
string source="MGWC0000";
string[] path=new string[16];
Queue myqueue=new Queue ();
private System.ComponentModel.Container components = null;
public Form1()
{
//
// Windows 窗体设计器支持所必需的
//
InitializeComponent();
//
// TODO: 在 InitializeComponent 调用后添加任何构造函数代码
//
} /// <summary>
/// 清理所有正在使用的资源。
/// </summary>
protected override void Dispose( bool disposing )
{
if( disposing )
{
if (components != null) 
{
components.Dispose();
}
}
base.Dispose( disposing );
} #region Windows Form Designer generated code
/// <summary>
/// 设计器支持所需的方法 - 不要使用代码编辑器修改
/// 此方法的内容。
/// </summary>
private void InitializeComponent()
{
System.Resources.ResourceManager resources = new System.Resources.ResourceManager(typeof(Form1));
this.textout = new System.Windows.Forms.RichTextBox();
this.button1 = new System.Windows.Forms.Button();
this.button2 = new System.Windows.Forms.Button();
this.SuspendLayout();
// 
// textout
// 
this.textout.Font = new System.Drawing.Font("宋体", 12F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((System.Byte)(134)));
this.textout.Location = new System.Drawing.Point(16, 16);
this.textout.Name = "textout";
this.textout.ReadOnly = true;
this.textout.Size = new System.Drawing.Size(448, 360);
this.textout.TabIndex = 0;
this.textout.Text = "";
// 
// button1
// 
this.button1.Location = new System.Drawing.Point(64, 384);
this.button1.Name = "button1";
this.button1.TabIndex = 1;
this.button1.Text = "start";
this.button1.Click += new System.EventHandler(this.button1_Click);
// 
// button2
// 
this.button2.Location = new System.Drawing.Point(312, 384);

Answer 2

this.button2.Name = "button2";
this.button2.TabIndex = 2;
this.button2.Text = "exit";
this.button2.Click += new System.EventHandler(this.button2_Click);
// 
// Form1
// 
this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
this.ClientSize = new System.Drawing.Size(480, 414);
this.Controls.AddRange(new System.Windows.Forms.Control[] {
  this.button2,
  this.button1,
  this.textout});
this.Icon = ((System.Drawing.Icon)(resources.GetObject("$this.Icon")));
this.Name = "Form1";
this.Text = "Wolf and Goat";

this.ResumeLayout(false); }
#endregion /// <summary>
/// 应用程序的主入口点。
/// </summary>
[STAThread]
static void Main() 
{
Application.Run(new Form1());
}
private bool Checklegal(string source)
{
string s=source;
if(s.Substring (0,4).Equals("0GWC"))
{
textout.Text =textout.Text +"\n"+s+" 此岸出现羊.狼.菜无人看管.舍弃这一步";
return false;
}
else
if(s.Substring (0,4).Equals ("0G0C"))
{
textout.Text=textout.Text+"\n"+s+" 此岸出现羊和菜无人看管.舍弃这一步";
return false;
}
else
if(s.Substring (0,4).Equals ("0GW0"))
{
textout.Text=textout.Text+"\n"+s+" 此岸出现羊和狼无人看管.舍弃这一步";
return false;
}
else
if(s.Substring (4,4).Equals ("0GWC"))
{
textout.Text=textout.Text+"\n"+s+" 彼岸出现羊.狼.菜无人看管.舍弃这一步";
return false;
}
else
if(s.Substring (4,4).Equals ("0G0C"))
{
textout.Text=textout.Text+"\n"+s+" 彼岸出现羊和菜无人看管.舍弃这一步";
return false;
}
else
if(s.Substring (4,4).Equals ("0GW0"))
{
textout.Text=textout.Text+"\n"+s+" 彼岸出现羊和狼无人看管.舍弃这一步";
return false;
}
else
{
textout.Text=textout.Text+"\n"+s+" 使路的搜索继续下去";
return true;
}


}
private bool Checkrepeat(string source)
{
string s=source;
for(int i=0;i<16;i++)
{
if(s.Equals (path[i]))
{
textout.Text=textout.Text+"\n"+s+" 使路的搜索出现重复.舍弃这一步";

return true;
}
}
return false;
} private void swap(string source)
{

string s=source;
string d;
if(s.Substring (0,1).Equals ("M"))
{
d="0"+s.Substring (1,3)+"M"+s.Substring (5,3);//Man goto that bank ,no one come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}
}
if(s.Substring(0,2).Equals("MG"))
{
d="00"+s.Substring (2,2)+"MG"+s.Substring (6,2);//man and goat goto that bank ,no one come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}
}
if(s.Substring (0,1).Equals ("M")&&s.Substring (2,1).Equals ("W"))
{
d="0"+s.Substring (1,1)+"0"+s.Substring (3,1)+"M"+s.Substring (5,1)+"W"+s.Substring (7,1);// man adn wolf goto that bank ,no one come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}
}
if(s.Substring (0,1).Equals ("M")&&s.Substring (3,1).Equals ("C"))
{
d="0"+s.Substring (1,2)+"0M"+s.Substring (5,2)+"C";//man and cabbage goto that bank ,no one come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}
}
if(s.Substring (4,2).Equals ("MG"))
{
d="MG"+s.Substring (2,2)+"00"+s.Substring (6,2);//no one goto that bank ,but man and goat come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}
}
if(s.Substring (4,1).Equals ("M")&&s.Substring (6,1).Equals ("W"))
{
d="M"+s.Substring (1,1)+"W"+s.Substring (3,1)+"0"+s.Substring (5,1)+"0"+s.Substring (7,1);//no one goto that bank ,but man and wolf come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}

}
if(s.Substring (4,1).Equals ("M")&&s.Substring (7,1).Equals ("C"))
{
d="M"+s.Substring (1,2)+"C0"+s.Substring (5,2)+"0";//no one goto that bank but man and cabbage come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}
}
if(s.Substring (4,1).Equals ("M"))
{
d="M"+s.Substring (1,3)+"0"+s.Substring (5,3);//no one goto that bank but only man come back
if(Checklegal(d))
{
myqueue.Enqueue(d);

}
}

}
private bool CheckEnd(string source)
{
if(source.Equals ("0000MGWC"))
{

return true;
}
return false;
}
private bool Output()
{
string s="";
textout.Text=textout.Text+"\n\n"+"输出可行的路径:"+"\n";
for(int i=0;i<path.Length ;i++)
{
s=path[i];
textout.Text=textout.Text+"\n"+s; }
return true;
}
private void button1_Click(object sender, System.EventArgs e)
{
string s;
path[0]=source;
int i=1;
int j=1;
swap(source);
while(myqueue.Count !=0)
{
s=(string)(myqueue.Dequeue ());
source=s;
if(!Checkrepeat(source))
{
path[i]=source;
swap(source);
j++;
if(CheckEnd(source)) break;
i++;
}
}
Output();
} private void button2_Click(object sender, System.EventArgs e)
{
Application.Exit ();
}
}
}
说明:以上代码在windows xp professional + visual studio.net 2002下调试通过.

Answer 3

复制下来调试调试～～HOHO
虽然算法很早就知道了，不过没用C＃写过

Answer 4

将程序中文本框的输出结果列出:0GWCM000 此岸出现羊.狼.菜无人看管.舍弃这一步
00WCMG00 使路的搜索继续下去
0G0CM0W0 此岸出现羊和菜无人看管.舍弃这一步
0GW0M00C 此岸出现羊和狼无人看管.舍弃这一步
MGWC0000 使路的搜索继续下去
M0WC0G00 使路的搜索继续下去
MGWC0000 使路的搜索出现重复.舍弃这一步
00WCMG00 使路的搜索继续下去
000CMGW0 使路的搜索继续下去
00W0MG0C 使路的搜索继续下去
00WCMG00 使路的搜索出现重复.舍弃这一步
MG0C00W0 使路的搜索继续下去
M0WC0G00 使路的搜索继续下去
M00C0GW0 彼岸出现羊和狼无人看管.舍弃这一步
MGW0000C 使路的搜索继续下去
M0WC0G00 使路的搜索继续下去
M0W00G0C 彼岸出现羊和菜无人看管.舍弃这一步
0G0CM0W0 此岸出现羊和菜无人看管.舍弃这一步
000CMGW0 使路的搜索继续下去
0G00M0WC 使路的搜索继续下去
M0WC0G00 使路的搜索出现重复.舍弃这一步
0GW0M00C 此岸出现羊和狼无人看管.舍弃这一步
00W0MG0C 使路的搜索继续下去
0G00M0WC 使路的搜索继续下去
M0WC0G00 使路的搜索出现重复.舍弃这一步
000CMGW0 使路的搜索出现重复.舍弃这一步
MGW0000C 使路的搜索继续下去
MG0C00W0 使路的搜索继续下去
MG0000WC 使路的搜索继续下去
00W0MG0C 使路的搜索出现重复.舍弃这一步
0G00M0WC 使路的搜索出现重复.舍弃这一步
MGW0000C 使路的搜索出现重复.舍弃这一步
MG0C00W0 使路的搜索出现重复.舍弃这一步
0G00M0WC 使路的搜索继续下去
0000MGWC 使路的搜索继续下去
0G00M0WC 使路的搜索出现重复.舍弃这一步
MG0000WC 使路的搜索继续下去
M0W00G0C 彼岸出现羊和菜无人看管.舍弃这一步
M00C0GW0 彼岸出现羊和狼无人看管.舍弃这一步
M0000GWC 彼岸出现羊.狼.菜无人看管.舍弃这一步输出可行的路径:MGWC0000
00WCMG00
M0WC0G00
000CMGW0
00W0MG0C
MG0C00W0
MGW0000C
0G00M0WC
MG0000WC
0000MGWC前半部分是用来调试和跟踪路径生成过程的,可以不做这类,关键的是后面输出可行的路径.
其实这里我没有完全解决多种结果的输出问题,使得这个输出不准确,乍一看像是错了,事实上,它就是
MGWC0000
00WCMG00
M0WC0G00
000CMGW0 00W0MG0C
MG0C00W0 MGW0000C
0G00M0WC
MG0000WC
0000MGWC
以上路径图,描述了小学生都会的那两种解法,证明了我的程序的正确性,我的代码虽然不能把这类广度优先搜索的队列更合理的输出,但是我太困了,要睡觉了,只能到这里结束了,希望以后谁又有了改进版,发给我 [email protected]:10 2003-6-24