Last active
June 10, 2020 23:47
-
-
Save sampletext32/593fa341ffce3d9430cd12a8354dc47c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Graph | |
{ | |
public class Connection | |
{ | |
public Node n1; | |
public Node n2; | |
public int Distance { get; set; } | |
public Connection(Node n1, Node n2) | |
{ | |
this.n1 = n1; | |
this.n2 = n2; | |
} | |
} | |
public class Node | |
{ | |
public int F { get; set; } | |
public string Name { get; set; } | |
public bool IsSource { get; set; } | |
public Node Parent { get; set; } | |
public Node(bool isSource) | |
{ | |
IsSource = isSource; | |
} | |
} | |
private List<Node> Nodes; | |
private List<Connection> Connections; | |
public Graph() | |
{ | |
Nodes = new List<Node>(); | |
Connections = new List<Connection>(); | |
} | |
public void AddNode(Node node) | |
{ | |
Nodes.Add(node); | |
} | |
public void AddConnection(Connection conn) | |
{ | |
Connections.Add(conn); | |
} | |
public bool WidthSearch(Node start, Node finish) | |
{ | |
List<Node> testQueue = new List<Node>(); | |
List<Node> looked = new List<Node>(); | |
testQueue.Add(start); | |
while (testQueue.Count > 0) | |
{ | |
var node = testQueue[0]; | |
if (node == finish) | |
{ | |
return true; | |
} | |
for (int i = 0; i < Connections.Count; i++) | |
{ | |
if (Connections[i].n1 == node) | |
{ | |
if (!looked.Contains(Connections[i].n2)) | |
{ | |
testQueue.Add(Connections[i].n2); | |
} | |
} | |
if (Connections[i].n2 == node) | |
{ | |
if (!looked.Contains(Connections[i].n1)) | |
{ | |
testQueue.Add(Connections[i].n1); | |
} | |
} | |
} | |
testQueue.RemoveAt(0); | |
looked.Add(node); | |
} | |
return false; | |
} | |
List<Connection> GetFor(Node n) | |
{ | |
List<Connection> connections = new List<Connection>(); | |
for (int i = 0; i < Connections.Count; i++) | |
{ | |
if (Connections[i].n1 == n) | |
{ | |
connections.Add(Connections[i]); | |
} | |
else if (Connections[i].n2 == n) | |
{ | |
var conn = new Connection(Connections[i].n2, Connections[i].n1); | |
conn.Distance = Connections[i].Distance; | |
connections.Add(conn); | |
} | |
} | |
return connections; | |
} | |
public int AStar(Node start, Node goal) | |
{ | |
List<Node> u = new List<Node>(); | |
List<Node> q = new List<Node>(); | |
q.Add(start); | |
start.F = 0; | |
while (q.Count > 0) | |
{ | |
Node current = q.OrderByDescending(n => n.F).First(); | |
if (current == goal) | |
{ | |
return goal.F; | |
} | |
q.Remove(current); | |
u.Add(current); | |
foreach (var v in GetFor(current)) | |
{ | |
int tentativeScore = current.F + v.Distance; | |
if (u.Contains(v.n2) && tentativeScore >= v.n2.F) | |
{ | |
continue; | |
} | |
if (!u.Contains(v.n2) || tentativeScore < v.n2.F) | |
{ | |
v.n2.Parent = current; | |
v.n2.F = tentativeScore; | |
if (!q.Contains(v.n2)) | |
{ | |
q.Add(v.n2); | |
} | |
} | |
} | |
} | |
return -1; | |
} | |
public static void Tttt() | |
{ | |
// создание узлов | |
var graph = new Graph(); | |
graph.Nodes.Add(new Node(true)); | |
graph.Nodes.Last().Name = "1"; | |
graph.Nodes.Add(new Node(false)); | |
graph.Nodes.Last().Name = "2"; | |
graph.Nodes.Add(new Node(false)); | |
graph.Nodes.Last().Name = "3"; | |
// создание соединений | |
graph.Connections.Add(new Connection(graph.Nodes[0], graph.Nodes[1])); | |
graph.Connections.Last().Distance = 10; | |
graph.Connections.Add(new Connection(graph.Nodes[0], graph.Nodes[2])); | |
graph.Connections.Last().Distance = 20; | |
// Разделение на фабрики и производители | |
List<Node> processors = graph.Nodes.Where(n => !n.IsSource).ToList(); | |
List<Node> sources = graph.Nodes.Where(n => n.IsSource).ToList(); | |
// список расстояний от каждой фабрики до ближайшего источника | |
List<int> distances = new List<int>(); | |
// для каждой фабрики ищем ближайший источник | |
foreach (var processor in processors) | |
{ | |
int shortestDist = int.MaxValue; | |
foreach (var source in sources) | |
{ | |
// вызываем поиск в графе A* | |
// https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A* | |
int currentDistance = graph.AStar(processor, source); | |
if (currentDistance < shortestDist) | |
{ | |
shortestDist = currentDistance; | |
} | |
} | |
distances.Add(shortestDist); | |
} | |
int k = 1; // количество элементов к удалению | |
for (int i = 0; i < k; i++) | |
{ | |
var minimum_index = distances.IndexOf(distances.Max()); // находим индекс минимума | |
Console.WriteLine("We delete '{0}' node, with distance {1} to closest source", processors[minimum_index].Name, | |
distances[minimum_index]); | |
processors.RemoveAt(minimum_index); | |
distances.RemoveAt(minimum_index); | |
} | |
// выводим все оставшиеся фабрики | |
foreach (var processor in processors) | |
{ | |
// Вывод оставшихся | |
Console.WriteLine("'{0}' processor left", processor.Name); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment