Rose
Reputation: 359
How to search for an optimal solution that depends on a specific values in a matrix in C#
I need to extract the best path in terms of its length from a rectangular array like this array:
The pathfinding rules:
- Start from the indexes provided in the method signature where the
rowIndexandcolIndexare the positions of the starting point.`- The ones must be able to connect with each other either horizontally, vertically, or diagonally.
- The last point on the path is the cell with a value of one that has no path to any other surrounding cells with a value of one.
I tried the following recursion algorithm, but it does not work for me and generate wrong output i.e. not as expected!!.
Here are the results: Results
using System;
using System.IO;
using System.Text;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;
using System.Threading;
using AUV_Topology;
using System.Collections.Generic;
using System.Media;
using System.Linq;
namespace AUVtopology
{
public partial class Form1 : Form
{
static int[,] array;
static List<int[]> path;
// *******************************************************************************************************************************//
//This method is used to make sure the coordinate array
//is contained in the list. List.contains(new int[] {val1,val2}) was not enough.
static Boolean containsArray(List<int[]> list, int[] array)
{
if (array == null || array.Length == 0)
{
return false;
}
foreach (var listArray in list)
{
if (listArray != null && listArray.Length == array.Length)
{
for (int i = 0; i < listArray.Length; i++)
{
if (i != listArray.Length - 1)
{
if (array[i] != listArray[i] && array[i + 1] != listArray[i + 1])
{
continue;
}
return true;
}
}
}
}
return false;
}
// *******************************************************************************************************************************//
//This is the recursive method of the algorithm. It finds the
//maximum path of 1 cells in a matrix of 0/1 cells
static List<int[]> getMaxPath(int[,] array, List<int[]> maxPath, int rowIndex, int colIndex)
{
//Add the current cell to the path.
maxPath.Add(new int[] { rowIndex, colIndex });
//Get the array limits.
int rowLength = array.GetLength(0);
int colLength = array.GetLength(1);
//If the path contains all the cells in the matrix, stop
if (maxPath.Count >= rowLength * colLength)
{
return maxPath;
}
//remove one from lengths to make it the maximum index
colLength = colLength - 1;
rowLength = rowLength - 1;
//We'll use this variable to see which of the
//potential 7 paths are the longest.
List<int[]> futurePath;
//Go over all 8 possible adjoining cells:
//If we can go one down, one right, and it's a spot we
//have not yet visited
if (colIndex < colLength && rowIndex < rowLength &&
array[rowIndex + 1, colIndex + 1] == 1 &&
!containsArray(maxPath, new int[] { rowIndex + 1, colIndex + 1 }))
{
//We use maxPath first, since this is the first
//direction and by default is the longest
maxPath = getMaxPath(array, maxPath, rowIndex + 1, colIndex + 1);
}
//If we can go one down, and it's a spot we have not
//yet visited
if (colIndex < colLength &&
array[rowIndex, colIndex + 1] == 1 &&
!containsArray(maxPath, new int[] { rowIndex, colIndex + 1 }))
{
//We use futurePath now, since this is a second
//direction and a potential contender
futurePath = getMaxPath(array, maxPath, rowIndex, colIndex + 1);
//We only need the maximum path.
if (futurePath.Count > maxPath.Count)
{
maxPath = futurePath;
}
}
//If we can go one down and one left, and it's a spot
//we have not yet visited
if (rowIndex > 0 && colIndex < colLength &&
array[rowIndex - 1, colIndex + 1] == 1 &&
!containsArray(maxPath, new int[] { rowIndex - 1, colIndex + 1 }))
{
futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex + 1);
if (futurePath.Count > maxPath.Count)
{
maxPath = futurePath;
}
}
//If we can go one left, and it's a spot we have not
//yet visited
if (rowIndex > 0 &&
array[rowIndex - 1, colIndex] == 1 &&
!containsArray(maxPath, new int[] { rowIndex - 1, colIndex }))
{
futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex);
if (futurePath.Count > maxPath.Count)
{
maxPath = futurePath;
}
}
//If we can go one left and one up, and it's a spot we
//have not yet visited
if (rowIndex > 0 && colIndex > 0 &&
array[rowIndex - 1, colIndex - 1] == 1 &&
!containsArray(maxPath, new int[] { rowIndex - 1, colIndex - 1 }))
{
futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex - 1);
if (futurePath.Count > maxPath.Count)
{
maxPath = futurePath;
}
}
//If we can go one up, and it's a spot we have not yet
//visited
if (colIndex > 0 &&
array[rowIndex, colIndex - 1] == 1 &&
!containsArray(maxPath, new int[] { rowIndex, colIndex - 1 }))
{
futurePath = getMaxPath(array, maxPath, rowIndex, colIndex - 1);
if (futurePath.Count > maxPath.Count)
{
maxPath = futurePath;
}
}
//If we can go one up and one right, and it's a spot we
//have not yet visited
if (colIndex > 0 && rowIndex < rowLength &&
array[rowIndex + 1, colIndex - 1] == 1 &&
!containsArray(maxPath, new int[] { rowIndex + 1, colIndex - 1 }))
{
futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex - 1);
if (futurePath.Count > maxPath.Count)
{
maxPath = futurePath;
}
}
//If we can go one right, and it's a spot we have not
//yet visited
if (rowIndex < rowLength &&
array[rowIndex + 1, colIndex] == 1 &&
!containsArray(maxPath, new int[] { rowIndex + 1, colIndex }))
{
futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex);
if (futurePath.Count > maxPath.Count)
{
maxPath = futurePath;
}
}
//We return the max path. Note: If none of the directions around
//us was applicable, we simply return the path we started
//with our cell included.
return maxPath;
}
Is prim algorithm the best choice ?
Upvotes: 0
Views: 175
Answers (2)
jdweng
Reputation: 34421
I finally had some time to work this out. I did it with an enumerator to simplify the if loop. Did like having 8 if statements. I've been doing code like this for 40 years and know all the pitfalls.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace AUV_Topology
{
class Program
{
public static object[] PopulationChromosomes = {
new int[,] {
{ 1,0,1,1},
{ 1,1,1,0},
{ 1,0,1,0},
{ 0,1,0,0}
},
new int[,] {
{ 1,1,0,1},
{ 1,1,0,0},
{ 0,1,0,0},
{ 1,0,1,0}
},
new int[,] {
{ 1,0,0,0},
{ 1,1,1,1},
{ 1,0,0,1},
{ 0,0,0,1}
},
new int[,] {
{ 0,1,0,0},
{ 1,1,1,0},
{ 1,0,0,1},
{ 0,1,0,1}
},
new int[,] {
{ 0,1,0,1},
{ 0,1,1,0},
{ 1,1,0,1},
{ 0,0,0,1}
},
new int[,] {
{ 0,1,1,0},
{ 1,1,0,1},
{ 0,1,0,1},
{ 1,0,0,0}
}
};
public static int[] auvChromosomeLocationsIndexesX = { 3, 0, 1, 3, 2, 2 };
public static int[] auvChromosomeLocationsIndexesY = { 2, 1, 0, 1, 3, 0 };
const string FILENAME = @"C:/temp/TreeParser.txt";
static void Main(string[] args)
{
StreamWriter sw = new StreamWriter(FILENAME);
int tt = 0;
foreach (int[,] chromosome in PopulationChromosomes)
{
new SpanningTree(auvChromosomeLocationsIndexesY[tt], auvChromosomeLocationsIndexesX[tt], chromosome);
SpanningTree.OrderHighLow(SpanningTree.root, 0);
SpanningTree.Print(SpanningTree.root, 0, tt, sw);
tt++;
}
sw.Flush();
sw.Close();
Console.ReadLine();
}
}
/* Class Cell */
/*****************************************************************************************************************************/
public class Cell
{
public int row { get; set; }
public int col { get; set; }
public int value { get; set; }
public Boolean visited { get; set; }
}
/* Class EnumCell */
/*****************************************************************************************************************************/
public class EnumCell : IEnumerator<Cell>
{
public EnumCell() { }
public EnumCell(int startRow, int startCol, List<List<Cell>> graph)
{
row = startRow;
col = startCol;
numberOfRows = graph.Count;
numberOfCols = graph[0].Count;
EnumCell.graph = graph;
this.position = LOCATIONS.RESET;
}
public enum XY
{
Y = 0, //row
X = 1 //col
}
public enum LOCATIONS : byte
{
RESET = 0xFF,
TOP_LEFT = 0,
TOP_MIDDLE,
TOP_RIGHT,
LEFT,
RIGHT,
BOTTOM_LEFT,
BOTTOM_MIDDLE,
BOTTOM_RIGHT,
END,
INVALID
}
public static List<List<Cell>> graph { get; set; }
public static int row { get; set; }
public static int col { get; set; }
public static int numberOfRows { get; set; }
public static int numberOfCols { get; set; }
//offsets are in same order as enum location as y-offset(row), x-offset (col)
private static List<List<int>> offsets = new List<List<int>>() {
new List<int>() { -1, -1 },
new List<int>() { -1, 0 },
new List<int>() { -1, +1 },
new List<int>() { 0, -1 },
new List<int>() { 0, +1 },
new List<int>() { +1, -1 },
new List<int>() { +1, 0 },
new List<int>() { +1, +1 }
};
public LOCATIONS position { get; set; }
public EnumCell GetEnumerator()
{
return new EnumCell(row, col, graph);
}
object IEnumerator.Current
{
get
{
return Current;
}
}
/* Class Current Cell */
/*****************************************************************************************************************************/
public Cell Current
{
get
{
try
{
// move to first valid postion
if (position == LOCATIONS.RESET) position = LOCATIONS.TOP_LEFT;
for (LOCATIONS location = position; location < LOCATIONS.END; location++)
{
if ((row + offsets[(byte)location][(int)XY.Y] >= 0) && (row + offsets[(byte)location][(int)XY.Y] < numberOfRows) &&
(col + offsets[(byte)location][(int)XY.X] >= 0) && (col + offsets[(byte)location][(int)XY.X] < numberOfCols))
{
position = (LOCATIONS)location;
int newRow = row + offsets[(byte)location][(int)XY.Y];
int newCol = col + offsets[(byte)location][(int)XY.X];
return graph[newRow][newCol];
}
}
throw new InvalidOperationException();
}
catch (IndexOutOfRangeException)
{
throw new InvalidOperationException();
}
}
}
public Boolean MoveNext()
{
Boolean results = false;
for (LOCATIONS location = ++position; location < LOCATIONS.END; location++)
{
int y = offsets[(byte)location][(int)XY.Y];
int x = offsets[(byte)location][(int)XY.X];
if ((row + y >= 0) && (row + y < numberOfRows) &&
(col + x >= 0) && (col + x < numberOfCols))
{
if (graph[row + y][col + x].value == 1)
{
position = (LOCATIONS)location;
return true;
}
}
}
return results;
}
public void Reset()
{
position = LOCATIONS.RESET;
}
public void Dispose()
{
}
}
/* Class Graph */
/*****************************************************************************************************************************/
public class Graph
{
public Graph(int[,] graph)
{
this.graph = new List<List<Cell>>();
for (int row = 0; row < graph.GetLength(0); row++)
{
List<Cell> newRow = new List<Cell>();
this.graph.Add(newRow);
for (int col = 0; col < graph.GetLength(1); col++)
{
Cell newCell = new Cell();
newRow.Add(newCell);
newCell.row = row;
newCell.col = col;
newCell.value = graph[row, col];
newCell.visited = false;
}
}
}
public List<List<Cell>> graph;
}
/* Class SpanningTree */
/*****************************************************************************************************************************/
class SpanningTree
{
public static Graph graph = null;
public static SpanningTree root = null;
public static int counter = 0;
public int row { get; set; }
public int col { get; set; }
public int length { get; set; }
public List<SpanningTree> children { get; set; }
public SpanningTree() { }
public SpanningTree(int startRow, int startCol, int[,] graph)
{
root = new SpanningTree();
SpanningTree.graph = new Graph(graph);
RecursiveTree(root, SpanningTree.graph.graph[startRow][startCol]);
}
public int RecursiveTree(SpanningTree parent, Cell currentCell)
{
int length = 0;
int maxLength = 0;
parent.row = currentCell.row;
parent.col = currentCell.col;
graph.graph[currentCell.row][currentCell.col].visited = true;
EnumCell enumCell = new EnumCell(currentCell.row, currentCell.col, graph.graph);
foreach (Cell cell in enumCell)
{
if (!cell.visited)
{
SpanningTree newBranch = new SpanningTree();
if (parent.children == null) parent.children = new List<SpanningTree>();
length = RecursiveTree(newBranch, SpanningTree.graph.graph[cell.row][cell.col]);
if (length > maxLength)
{
if ((EnumCell.numberOfRows > 7) || (EnumCell.numberOfCols > 7))
{
if (parent.children.Count == 0)
{
parent.children.Add(newBranch);
}
else
{
parent.children[0] = newBranch;
}
}
else
{
parent.children.Add(newBranch);
}
maxLength = length;
}
}
}
graph.graph[currentCell.row][currentCell.col].visited = false;
parent.length = maxLength;
return maxLength + 1;
}
public static void OrderHighLow(SpanningTree parent, int level)
{
if (parent.children != null)
{
parent.children = parent.children.OrderByDescending(x => x.length).ToList();
foreach (SpanningTree child in parent.children)
{
OrderHighLow(child, level + 1);
}
}
}
public static void Print(SpanningTree parent, int level, int chromosomeNum, StreamWriter sw)
{
sw.WriteLine("------------------- Chromosome : {0} -------------------", chromosomeNum);
//Print(parent, level, sw);
sw.WriteLine("---------Longest----------");
PrintLongest(parent, level, sw);
counter = 0;
}
private static void Print(SpanningTree parent, int level, StreamWriter sw)
{
//////////////////////////////////////////////////////////////////////
sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, parent.row, parent.col, parent.length);
//////////////////////////////////////////////////////////////////////
if (parent.children != null)
{
foreach (SpanningTree child in parent.children)
{
Print(child, level + 1, sw);
if (child.length == 0)
{
sw.WriteLine("||,,,,,,Branch {0},,,,,,||", counter);
sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, root.row, root.col, root.length);
counter += 1;
}
}
}
}
public static void PrintLongest(SpanningTree parent, int level, StreamWriter sw)
{
//////////////////////////////////////////////////////////////////////
sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, parent.row, parent.col, parent.length);
//////////////////////////////////////////////////////////////////////
if (parent.children != null)
{
PrintLongest(parent.children[0], level + 1, sw);
}
}
}
}// end name space
Upvotes: 1
jdweng
Reputation: 34421
Here is code using a Class Project that works without compiler errors
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Auv_Topology
{
public class Cell
{
public int row { get; set; }
public int col { get; set; }
public int value { get; set; }
public Boolean visited { get; set; }
}
public class EnumCell : IEnumerator<Cell>
{
public EnumCell() { }
public EnumCell(int startRow, int startCol, List<List<Cell>> graph)
{
this.row = startRow;
this.col = startCol;
this.numberOfRows = graph.Count;
this.numberOfCols = graph[0].Count;
this.graph = graph;
}
public enum XY
{
Y = 0, //row
X = 1 //col
}
public enum LOCATIONS : byte
{
TOP_LEFT = 0,
TOP_MIDDLE,
TOP_RIGHT,
LEFT,
RIGHT,
BOTTOM_LEFT,
BOTTOM_MIDDLE,
BOTTOM_RIGHT,
END,
INVALID
}
public List<List<Cell>> graph { get; set; }
public int row { get; set; }
public int col { get; set; }
public int numberOfRows { get; set; }
public int numberOfCols { get; set; }
//offsets are in same order as enum location as y-offset(row), x-offset (col)
private List<List<int>> offsets = new List<List<int>>() {
new List<int>() { -1, -1 },
new List<int>() { -1, 0 },
new List<int>() { -1, +1 },
new List<int>() { 0, -1 },
new List<int>() { 0, +1 },
new List<int>() { +1, -1 },
new List<int>() { +1, 0 },
new List<int>() { +1, +1 }
};
public LOCATIONS position { get; set; }
public EnumCell GetEnumerator()
{
return new EnumCell(row, col, graph);
}
object IEnumerator.Current
{
get
{
return Current;
}
}
public Cell Current
{
get
{
try
{
// move to first valie postion
for (LOCATIONS location = position; location < LOCATIONS.END; location++)
{
if ((row + offsets[(byte)location][(int)XY.Y] >= 0) && (row + offsets[(byte)location][(int)XY.Y] < numberOfRows) &&
(col + offsets[(byte)location][(int)XY.X] > 0) && (col + offsets[(byte)location][(int)XY.X] < numberOfCols))
{
position = (LOCATIONS)location;
int newRow = row + offsets[(byte)location][(int)XY.Y];
int newCol = col + offsets[(byte)location][(int)XY.X];
return graph[newRow][newCol];
}
}
throw new InvalidOperationException();
}
catch (IndexOutOfRangeException)
{
throw new InvalidOperationException();
}
}
}
public Boolean MoveNext()
{
Boolean results = false;
for (LOCATIONS location = ++position; location < LOCATIONS.END; location++)
{
int y = offsets[(byte)location][(int)XY.Y];
int x = offsets[(byte)location][(int)XY.X];
if ((row + y >= 0) && (row + y < numberOfRows) &&
(col + x > 0) && (col + x < numberOfCols))
{
if (graph[row + y][col + x].value == 1)
{
position = (LOCATIONS)location;
return true;
}
}
}
return results;
}
public void Reset()
{
position = LOCATIONS.TOP_LEFT;
}
public void Dispose()
{
}
}
}
Upvotes: 1
Related Questions
- Maximum sum path in a matrix from top to bottom
- Finding a specific Sub-Matrix of a given Matrix
- Using Linear search
- Two dimensional array game - walk and find c#
- finding a specific index on a two dimensional array
- Get Max Path Sum Recursive with huge 2d array
- how to find the best postions in a matrix?
- Choose one element from each row and column in matrix and the sum is minimized
- How do I search a multi-dimensional array?
- What Algorithm can i use to find any valid result depending on variable integer inputs