Zimano Zimano - 2 months ago 28
C# Question

Depth-first search never returning an answer

I was studying search algorithms and wanted to solve the missionaries and cannibals problem in order to practice. However, my code never provides a solution. At first, I thought this was because I had recurring states, causing an infinite loop, so I added a state history to make sure states weren't being repeated. However, this still has not worked.

Below is the code I have written. I am using vectors to represent the states of the missionaries, cannibals and the boat and the children of the nodes get added if they pass a check that checks if the move is within the range (0,0,0) and (3,3,1).

I have tried stepping through the code but since the tree is fairly large I can only keep track of so many things, so I have a hard time seeing the fault in my code.

This was written in Visual Studio as a console program.

Vector3 class

public class Vector3
{
public int m;
public int c;
public int b;
public Vector3(int M, int C, int B)
{
m = M;
c = C;
b = B;
}
public override bool Equals(System.Object obj)
{
if (obj == null)
return false;

Vector3 p = obj as Vector3;
if ((System.Object)p == null)
return false;

return (m == p.m) && (c == p.c) && (b == p.b);
}
}


Node class

public class Node
{
public Vector3 State;
public Node(Vector3 st)
{
State = st;
}
}


My Program.cs

class Program
{
static void Main(string[] args)
{
Program p = new Program();
p.DFS(new Node(new Vector3(3, 3, 1)));
Console.ReadKey();
}

List<Vector3> History = new List<Vector3>();
Vector3[] Operators = new Vector3[]
{
new Vector3(1,0,1),
new Vector3(2,0,1),
new Vector3(0,1,1),
new Vector3(0,2,1),
new Vector3(1,1,1),
};

public bool TryMove(Vector3 current, Vector3 toApply, bool substract)
{
if (substract)
{
if (current.c - toApply.c < 0 || current.m - toApply.m < 0 || current.b - toApply.b < 0 || (current.c - toApply.c) > (current.m - toApply.m))
{
return false;
}
else return true;
}
else
{
if (current.c + toApply.c > 3 || current.m + toApply.m > 3 || current.b + toApply.b > 1 || (current.c + toApply.c) > (current.m + toApply.m))
{
return false;
}
else return true;
}
}
public void DFS(Node n)
{
Stack<Node> stack = new Stack<Node>();
stack.Push(n);
while (stack.Count > 0)
{

Node curNode = stack.Pop();
if (History.Contains(curNode.State))
{

}
else
{
History.Add(curNode.State);
if (curNode.State == new Vector3(0, 0, 0))
{
Console.WriteLine("Solution found.");
return;
}
else
{
if (curNode.State.b == 0) //Boat is across the river
{
for (int x = 0; x < 5; x++)
{
if (TryMove(curNode.State, Operators[x], false))
{
stack.Push(new Node(new Vector3(curNode.State.m + Operators[x].m, curNode.State.c + Operators[x].c, curNode.State.b + Operators[x].b)));
}
}
}
else //Boat == 1
{
for (int x = 0; x < 5; x++)
{
if (TryMove(curNode.State, Operators[x], true))
{
stack.Push(new Node(new Vector3(curNode.State.m - Operators[x].m, curNode.State.c - Operators[x].c, curNode.State.b - Operators[x].b)));
}
}
}
}
}
}
Console.WriteLine("No solution found.");
return;
}
}


My code keeps hitting the 'No solution found' block. When I remove the history I keep infinite looping between states (3,3,1) and (2,2,1) and get an OutOfMemoryException at the 2 gigabyte mark, so I'm not even sure about keeping track of history anymore.

What steps should I take in order to implement the DFS in the context of the problem correctly, given the code I provided above?

Answer

Your algorithm is fine. The problem is that you used == operator in curNode.State == new Vector3(0, 0, 0); line. In C#, by default, == compares objects by reference, so this condition will always return false. Either use node.State.Equals(new Vector3(0, 0, 0)) or override == operator to use your Equals method.

See MSDN Guidelines on custom comparison in C#.

Comments