私は、与えられたポイントのペアについて、グリッド内の交差していないパスのセットを見つけるアルゴリズムに取り組んでいます。これらのペアについては、次のようになります：（9,4）と（12,13）
出力は次のようになります。
9,10,11,7,3,4
13,14,15,16,12
すべてのパスをルーティングできない場合は、「Blocked」と出力します
最初に、グラフまたはグリッド内の2点間のすべての単純なパスを見つけるために、すでに作成されたアルゴリズムを検索しました。そして私はここで@CaseyWatsonと@svickによってこれを見つけました..それは本当にうまく機能しますが、小さなグラフに対してのみです。
私はそれをC＃.NETに変換し、最大長Xのパスを見つけて、それに基づいてアルゴリズム全体を構築できるように少し拡張しました。
私が作成したものは、小さなグラフで正常に機能します。これは、8x8グリッドのルート9ペアです。
しかし、16x16のような大きなものや、16x16x2の3Dモデルである私が意図した最後のモデルでは、非常に時間がかかります。
このアルゴリズムは、深さ優先探索RECURSIVEアルゴリズムとして開発されましたが、ユーザーに値を返すのに非常に時間がかかりました。そこで、.NETのyield return機能の恩恵を受けることができるように、再帰呼び出しではなくループに変換することにしましたが、それでもそれ以上の効果はありませんでした。
アルゴリズムのループバージョンは、1秒未満でポイントのペアのルートを見つけますが、再帰的なルートは90秒以上かかりました。
2ペアで試したところ、ループバージョンは約342秒かかりましたが、再帰バージョンは約200秒かかりました。
だからどちらが速いのかわからない..！？再帰的またはループの1つ。
私は本当にこれを行うための最良の方法を知りたいです。
注：ノード番号の最初の桁がレイヤーを決定します（1から始まります）。
これがコードです
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
namespace AlgorithmTest
{
struct Connection
{
public int FirstNode;
public int SecondNode;
public Connection(int N1,int N2)
{
FirstNode = N1;
SecondNode = N2;
}
}
enum Algorithm
{ Recursion, Loops }
public class Search
{
private const int MAX = 15;
private const int Width = 16;
private const int Length = 16;
private const int Height = 2;
private static void Main(string[] args)
{
var graph = new Graph();
var str = new int[Height,Length, Width];
var level = ((int)Math.Pow(10, (Length * Width).ToString().Length) >= 100) ? (int)Math.Pow(10, (Length * Width).ToString().Length) : 100;
for (var i = 0; i < Height; i++)
{
int num = 0;
for (var j = 0; j < Length; j++)
for (var k = 0; k < Width; k++)
{
str[i, j, k] = ++num + level;
}
level += level;
}
for (var i = 0; i < Height; i++)
{
for (var j = 0; j < Length; j++)
{
for (var k = 0; k < Width; k++)
{
if (i < Height - 1) graph.addEdge(str[i, j, k], str[i + 1, j, k]);
if (i > 0) graph.addEdge(str[i, j, k], str[i - 1, j, k]);
if (k < Width - 1) graph.addEdge(str[i, j, k], str[i, j, k + 1]);
if (k > 0) graph.addEdge(str[i, j, k], str[i, j, k - 1]);
if (j < Length - 1) graph.addEdge(str[i, j, k], str[i, j + 1, k]);
if (j > 0) graph.addEdge(str[i, j, k], str[i, j - 1, k]);
}
}
}
var wt = new Stopwatch();
wt.Start();
var connectedNodes = new List<Connection>()
{
new Connection(1030, 1005),
// new Connection(1002, 1044),
// new Connection(1015, 1064),
// new Connection(1041, 1038),
// new Connection(1009, 1027),
// new Connection(1025, 1018),
// new Connection(1037, 1054),
// new Connection(1049, 1060),
// new Connection(1008, 1031),
// new Connection(1001, 1035),
};
wt.Start();
Console.WriteLine("Using Loops:");
Console.WriteLine();
var allPaths = new Search().FindAllPaths(connectedNodes, graph, MAX, Algorithm.Loops);
wt.Stop();
foreach (var path in allPaths)
{
PrintPath(path);
}
Console.WriteLine("Total Seconds: " + wt.Elapsed.TotalSeconds + ", Number of paths: " + allPaths.Count());
Console.WriteLine("***************************************************************************************************");
Console.WriteLine("Using Recursion:");
Console.WriteLine();
wt.Reset();
wt.Start();
allPaths = new Search().FindAllPaths(connectedNodes, graph, MAX, Algorithm.Recursion);
wt.Stop();
foreach (var path in allPaths)
{
PrintPath(path);
}
Console.WriteLine("Total Seconds: " + wt.Elapsed.TotalSeconds + ", Number of paths: " + allPaths.Count());
Console.WriteLine();
}
private IEnumerable<List<int>> FindAllPaths(List<Connection> connectedNodes, Graph graph, int max, Algorithm algorithm)
{
var paths=new Stack<List<int>>();
var blocked=new List<int>();
for (var i = 0; i < connectedNodes.Count; i++)
{
if (!blocked.Contains(connectedNodes[i].FirstNode)) blocked.Add(connectedNodes[i].FirstNode);
if (!blocked.Contains(connectedNodes[i].SecondNode)) blocked.Add(connectedNodes[i].SecondNode);
}
if (algorithm == Algorithm.Recursion)
{
if (FindAllPaths(connectedNodes, 0, max, graph, paths, blocked))
{
Console.WriteLine("BLOCKED");
return new List<List<int>>();
}
}
else if(algorithm==Algorithm.Loops)
{
if (!FindAllPaths2(connectedNodes, 0, max, graph, paths, blocked))
{
Console.WriteLine("BLOCKED");
return new List<List<int>>();
}
}
return paths;
}
private static bool FindAllPaths(List<Connection> connectedNodes,int order,int max, Graph graph, Stack<List<int>> allPaths, List<int> blocked)
{
if (order >= connectedNodes.Count) return false;
var paths = SearchForPaths(graph, connectedNodes[order].FirstNode, connectedNodes[order].SecondNode, max, blocked);
if (paths.Count == 0) return true;
int i;
for (i = 0; i < paths.Count; i++)
{
var path = paths[i];
allPaths.Push(path);
blocked.AddRange(path);
if (!FindAllPaths(connectedNodes, order + 1,max, graph, allPaths, blocked)) break;
allPaths.Pop();
foreach (var j in path)
{
blocked.RemoveAll(num => num==j);
}
paths.RemoveAll(list => IsListsSimilar(list,path));
i--;
}
if (i == paths.Count) return true;
return false;
}
private static bool IsListsSimilar(List<int> L1,List<int> L2)
{
if (L2.Count > L1.Count) return false;
for (int i = 0; i < L2.Count - 1; i++)
{
if (L1[i] != L2[i]) return false;
}
return true;
}
private static List<List<int>> SearchForPaths(Graph graph, int start, int end, int max, List<int> blocked)
{
blocked.Remove(start);
blocked.Remove(end);
var nodePaths = new List<List<int>>();
var visited = new LinkedList<int>();
visited.AddLast(start);
DepthFirstSearch(graph, visited, end, max, blocked, nodePaths);
nodePaths = nodePaths.OrderBy(list => list.Count).ToList();
return nodePaths;
}
private static void DepthFirstSearch(Graph graph, LinkedList<int> visited, int end, int max, List<int> blocked, List<List<int>> paths)
{
var nodes = graph.adjacentNodes(visited.Last.Value);
// examine adjacent nodes
var nodeCount = blocked.Count;
for (int i = 0; i < nodeCount; i++)
{
if (visited.Contains(blocked[i])) return;
}
if (visited.Count > max) return;
nodeCount = nodes.Count;
for (var i = 0; i < nodeCount; i++)
{
if (visited.Contains(nodes[i]) || nodes[i] != end) continue;
visited.AddLast(nodes[i]);
{
paths.Add(new List<int>(visited));
}
visited.RemoveLast();
break;
}
nodeCount = nodes.Count;
for (var i = 0; i < nodeCount; i++)
{
if (visited.Contains(nodes[i]) || nodes[i] == end) continue;
visited.AddLast(nodes[i]);
DepthFirstSearch(graph, visited, end, max, blocked, paths);
visited.RemoveLast();
}
}
private static bool FindAllPaths2(List<Connection> connectedNodes, int order, int max, Graph graph, Stack<List<int>> allPaths, List<int> blocked)
{
if (order >= connectedNodes.Count) return false;
foreach (var path in SearchForPaths2(graph, connectedNodes[order].FirstNode, connectedNodes[order].SecondNode, max, blocked))
{
allPaths.Push(path);
blocked.AddRange(path);
if (!FindAllPaths2(connectedNodes, order + 1, max, graph, allPaths, blocked)) break;
allPaths.Pop();
foreach (var j in path)
{
blocked.RemoveAll(num => num == j);
}
}
return true;
}
private static IEnumerable<List<int>> SearchForPaths2(Graph graph, int start, int end, int max, List<int> blocked)
{
blocked.Remove(start);
blocked.Remove(end);
var visited = new LinkedList<int>();
visited.AddLast(start);
foreach (var VARIABLE in DepthFirstSearch(graph, visited, end, max, blocked))
{
yield return VARIABLE;
}
}
private static IEnumerable<List<int>> DepthFirstSearch(Graph graph, LinkedList<int> visited, int end, int max, List<int> blocked)
{
var nodes = graph.adjacentNodes(visited.Last.Value);
var nodeCount = blocked.Count;
for (int i = 0; i < nodeCount; i++)
{
if (visited.Contains(blocked[i])) yield break;
}
if (visited.Count > max) yield break;
nodeCount = nodes.Count;
for (var i = 0; i < nodeCount; i++)
{
if (visited.Contains(nodes[i]) || nodes[i] != end) continue;
visited.AddLast(nodes[i]);
yield return (new List<int>(visited));
visited.RemoveLast();
break;
}
nodeCount = nodes.Count;
for (var i = 0; i < nodeCount; i++)
{
if (visited.Contains(nodes[i]) || nodes[i] == end) continue;
visited.AddLast(nodes[i]);
foreach (var P in DepthFirstSearch(graph, visited, end, max, blocked))
{
yield return P;
}
visited.RemoveLast();
}
}
private static void PrintPath(List<int> visited)
{
for (int i = 0; i < visited.Count()-1; i++)
{
Console.Write(visited[i]);
Console.Write(" --> ");
}
Console.Write(visited[visited.Count() - 1]);
Console.WriteLine();
Console.WriteLine();
}
}
public class Graph
{
private readonly Dictionary<int, HashSet<int>> map = new Dictionary<int, HashSet<int>>();
public void addEdge(int node1, int node2)
{
HashSet<int> adjacent = null;
map.TryGetValue(node1, out adjacent);
if (adjacent == null)
{
adjacent = new HashSet<int>();
map.Add(node1, adjacent);
}
adjacent.Add(node2);
}
public List<int> adjacentNodes(int last)
{
HashSet<int> adjacent = null;
map.TryGetValue(last, out adjacent);
if (adjacent == null)
{
return new List<int>();
}
return new List<int>(adjacent);
}
}
}