Traversering av et rutenett av noder med maks dypde

[Spartakus]

Hei,

 

jeg har følgende setting:

Et rutenett av 5 kolonner og 4 rader. Hver celle har en bokstav.

Bokstavene i cellene kan man da sette sammen til å forme et ord. Bokstavene kan kun settes sammen fra en nabo-celle. Man kan ikke bruke samme bokstav 2 ganger (dvs man kan ikke besøke noden man kom fra), men samme bokstav kan forekomme flere ganger i et ord

 

Jeg vil lage en algoritme som begynner på første celle og lager mulige ord som er mellom 2 og n lange (n = feks 8)

 

Jeg har laget en klasse for å representere en bokstav (node)

Har brukt himmelretningene for å navngi naboene.

 

Det å opprette nodene og lage referanser til naboene er en grei deal, men det er traverseringen jeg sliter litt med. Det blir åpenbart en rekursiv funksjon som må besøke neste node inntil maks dybde er nådd. For hvert besøk skal jeg legge utforme et ord utifra rekkefølgen jeg har besøkt nodene. Gyldigheten av ordet er ikke så nøye enda, foreløpig er alle bokstavkombinasjoner mellom lengde 2 og n gyldige.

 

Node.cs

public class Node
{
private string _letter = "";
private Node _north = null;
private Node _south = null;
private Node _east = null;
private Node _west = null;
private Node _northeast = null;
private Node _southeast = null;
private Node _southwest = null;
private Node _northwest = null;
private int _row = 0;
private int _col = 0;
public Node(string letter) { this._letter = letter; }
public string Letter
{
 get { return _letter; }
 set { _letter = value; }
}
public Node North
{
 get { return _north; }
 set { _north = value; }
}
public Node South
{
 get { return _south; }
 set { _south = value; }
}
public Node East
{
 get { return _east; }
 set { _east = value; }
}
public Node West
{
 get { return _west; }
 set { _west = value; }
}
public Node NorthEast
{
 get { return _northeast; }
 set { _northeast = value; }
}
public Node SouthEast
{
 get { return _southeast; }
 set { _southeast = value; }
}
public Node SouthWest
{
 get { return _southwest; }
 set { _southwest = value; }
}
public Node NorthWest
{
 get { return _northwest; }
 set { _northwest = value; }
}
public int Row
{
 get { return _row; }
 set { _row = value; }
}
public int Column
{
 get { return _col; }
 set { _col = value; }
}
}

 

string[] letters = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "Æ", "Ø", "Å" };
const int maxcols = 5;
const int maxrows = 4;
const int maxdepth = 8;
MersenneTwister r = new MersenneTwister(Environment.TickCount);
/*
*	C1  C2  C3  C4  C5
* R1   0   1   2   3   4
* R2   5   6   7   8   9
* R3   10  11  12  13  14
* R4   15  16  17  18  19
*/
private List<Node> nodes = null;

 

Har bare tatt med 4 himmelretninger, for enkelhetens skyld

private void initNodes()
{
nodes = new List<Node>(maxcols * maxrows);
for (int i = 0; i < nodes.Capacity; i++)
{
 Node n = new Node(GetRandomLetter());
 n.Column = i % maxcols + 1;
 n.Row = i / maxcols + 1;
 nodes.Add(n);
}
for (int i = 0; i < nodes.Capacity; i++)
{
 switch (nodes[i].Column)
 {
  case 1:
nodes[i].East = nodes[i + 1];
break;
  case maxcols:
nodes[i].West = nodes[i - 1];
break;
  default:
nodes[i].West = nodes[i + 1];
nodes[i].East = nodes[i - 1];
break;
 }
 switch (nodes[i].Row)
 {
  case 1:
nodes[i].South = nodes[i + maxcols];
break;
  case maxrows:
nodes[i].North = nodes[i - maxcols];
break;
  default:
nodes[i].North = nodes[i - maxcols];
nodes[i].South = nodes[i + maxcols];
break;
 }
}
//GUI
for (int i = 0; i < maxrows; i++)
{
 dataGridView1.Rows.Add(nodes[0 + i].Letter, nodes[1 + i].Letter, nodes[2 + i].Letter, nodes[3 + i].Letter, nodes[4 + i].Letter);
}
}

 

Begynnelse på en traverseringsalgoritme, her begynner hodet mitt å svikte, for jeg sliter med å skjønne hvordan det skal gjøres.

private string traverseNode(Node origin, Node current, int depth)
{
string ret = "";
//For hvert besøk økes dybden i node-traverseringen (ordlengden)
depth++;
//Hvis dybden er nådd, avbryt
if(depth > maxdepth)
 return ret;
//Hvis noden ovenfor (i rutenettet) finnes og noden vi kom fra ikke er lik denne:
if (current.North != null && current.North != origin)
{
 ret += current.Letter;
 ret += traverseNode(current, current.North, depth);
}
//Tilsvarende logikk på de andre naboene:
if (current.South != null && current.South != origin)
{
 ret += current.Letter;
 ret += traverseNode(current, current.South, depth);
}
if (current.West != null && current.West != origin)
{
 ret += current.Letter;
 ret += traverseNode(current, current.West, depth);
}
if (current.East != null && current.East != origin)
{
 ret += current.Letter;
 ret += traverseNode(current, current.East, depth);
}

return ret;
}

 

 

 

Loope nodene

for(int i = 0; i < nodes.Count; i++)
{
string word = traverseNode(nodes[i], nodes[i], 0);
}

 

Det er i allefall en begynnelse, noen som har noen tanker om hvordan jeg kan løse dette?

 

Jeg sitter fortsatt litt fast i .NET 2.0 rammerverket, så vennligst avstå fra å nevne LINQ og andre fancy greier her

[etse]

Jeg lagde en versjon som er basert på rekursiv dybdre først søk. Denne er skrevet i python og viser deg hvordan jeg ser for meg algoritmen. Burde ikke være noe problem å skrive den i C#, men da det tar lengre tid får det være din jobb

 

Rett og slett ser jeg på hver bokstav i rute-nettet som en node i en graf, og ser på alle ord som veiene dybde-først-søket ville ta når det søker gjennom grafen.

 

http://pastesite.com/35837

 

Edit: Så nå at du sa at ord måtte ha minst 2 bokstaver (1 er ikke gyldig) La dette til. Så ogstå at du snakket om diagonaler, så la til disse og. Grafen bli plutselig veldig stor da. Husk forresten at problemstillingen din, sidne du vil ha ALLE ord er det relativt algoritmisk tungt problem. Og kjøretiden vokser fort med størrelsen på tabellen din.

 

http://pastesite.com/35839

Endret 8. mai 2012 av etse

[Spartakus]

Takk for hjelp, python er dog noe ukjent for meg.

 

Jeg oppdaget også at jeg må sjekke at jeg ikke har brukt samme noden to ganger utifra der jeg startet, ikke bare noden jeg kom fra. Jeg må dermed ta vare på en besøksliste over steder jeg allerede har vært.

[etse]

Python er jånesten kjørbar psaudokode så burde være øesbart, hvis ikke vil jeg anbefale deg å lære litt basic python, da språken er meget kraftig på å vise hvordan man vil skrive avanserte algoritmer, pp en enkel måte og uten masse ekstra rot. Selv pleier jeg alltid å implementere og teste ting ut i python først, før jeg impøementerer i andre språk.

 

Om du ser på algoritmen min er den nesten helt lik dybde først søk. Så søk opp det om du vil lære mer. Algoritmen baserer seg på enkel rekursjon, med backtracking.

[etse]

Skrev et nytt eksempel, i C#. Om du ikke forstår åythonkodne kan du se på den i stede. Personlig følte jeg den var mye mindre lesbar. Algoritmen er forresten akkurat den samme.

 

http://pastesite.com/35867

[GeirGrusom]

Vil bare nevne at du skal kunne bruke C# 3.0 selv om du bruker .NET 2.0 som mål.

Endret 9. mai 2012 av GeirGrusom

[Spartakus]

Takker, ser du er "hakket" skarpere i algoritmeimplementering enn det jeg er =)

[The Jackal]

Har en litt annen tilnærming her. Denne løsningen kan ta inn hvilken som helst array og generere strenger ut av objektene. Tror den skal tilfredsstille kravene dine. Om den ikke gjør det, så er det vel uansett noe man kan lære av

 

namespace Traverse
{
public class Node : IEquatable<Node>
{
	private readonly object _value;
	public Node(object value)
	{
		_value = value;
	}
	public Node Left { get; set; }
	public Node Right { get; set; }
	public Node Up { get; set; }
	public Node Down { get; set; }
	public bool IsVisited { get; set; }
	public object Value
	{
		get { return _value; }
	}
	public bool Equals(Node other)
	{
		if (other == null)
			return false;
		if (Value == null)
			return false;
		return Value.Equals(other.Value);
	}
}

public class Generator
{
	private int _depth;
	private readonly List<Node> _nodes = new List<Node>();
	private readonly List<string> _result = new List<string>();
	private void SetupRelations(object[,] values, int depth)
	{
		_depth = depth;
		_nodes.Clear();
		for (var i = 0; i < values.GetLength(0); i++)
		{
			for (var j = 0; j < values.GetUpperBound(0); j++)
			{
				var value = values[i, j];
				var node = new Node(value);
				if (i - 1 >= 0)
				{
					var node2 = new Node(values[i - 1, j]);
					var existingNode = _nodes.Find(n => n.Equals(node2));
					existingNode.Down = node;
					node.Up = existingNode;
				}
				if (j - 1 >= 0)
				{
					var node2 = new Node(values[i, j - 1]);
					var existingNode = _nodes.Find(n => n.Equals(node2));
					existingNode.Right = node;
					node.Left = existingNode;
				}
				_nodes.Add(node);
			}
		}
	}
	public List<string> Generate(object[,] values, int depth)
	{
		SetupRelations(values, depth);
		_result.Clear();
		foreach (var node in _nodes)
		{
			var builder = new StringBuilder();
			GenerateRecursive(node, builder);
		}
		return _result.ToList();
	}
	private void GenerateRecursive(Node node, StringBuilder builder)
	{
		builder.Append(GetValue(node));
		if (builder.Length == _depth)
		{
			_result.Add(builder.ToString());
			builder.Remove(_depth - 1, 1);
			node.IsVisited = false;
			return;
		}
		if (node.Right != null && !node.Right.IsVisited)
			GenerateRecursive(node.Right, builder);
		if (node.Left != null && !node.Left.IsVisited)
			GenerateRecursive(node.Left, builder);
		if (node.Up != null && !node.Up.IsVisited)
			GenerateRecursive(node.Up, builder);
		if (node.Down != null && !node.Down.IsVisited)
			GenerateRecursive(node.Down, builder);
		builder.Remove(builder.Length - 1, 1);
		node.IsVisited = false;
	}
	private string GetValue(Node node)
	{
		node.IsVisited = true;
		return node.Value.ToString();
	}
}
internal class Program
{
	private static void Main(string[] args)
	{
		object[,] table = {
							  {'a', 'b', 'c', 'd'},
							  {'e', 'f', 'g', 'h'},
							  {'i', 'j', 'k', 'l'},
							  {'m', 'n', 'o', 'p'},
							  {'q', 'r', 's', 't'}
						  };
		object[,] table2 = {
							   {0, 1, 2},
							   {3, 4, 5},
							   {6, 7, 8}
						   };
		var generator = new Generator();
		foreach (var word in generator.Generate(table, 3))
		{
			Console.WriteLine(word);
		}
		foreach (var word in generator.Generate(table2, 3))
		{
			Console.WriteLine(word);
		}
		Console.ReadLine();
	}
}
}