Tìm kiếm một thuật toán trong vb.net hoặc C# nhưng tôi không biết tên của nó!

Question

Tôi sẽ cố gắng hết sức để giải thích thuật toán phải làm gì:

Có một công thức 'lớp học'. Mỗi Công thức có thể bao gồm các Công thức khác nhưng không thể bao gồm chính nó hoặc bất kỳ Công thức nào khác bao gồm nó.

Vì vậy, một ví dụ đơn giản là chúng tôi chỉ có hai công thức Một & B.

Nếu A cho biết thêm B đầu tiên, sau đó trên B không thể thêm một vì nó sẽ gây ra một vòng lặp.

Một ví dụ phức tạp hơn là:

A, B, C

(1) Recipe C Thêm B
(2) Recipe B Thêm Một
(3) Công thức Một cố gắng thêm C , nhưng không thể vì mối quan hệ. C - B - A.

Tôi có thể tự làm điều này, tôi tự hỏi liệu đây có phải là thuật toán được đặt tên chuẩn và tôi có thể lấy giải pháp tối ưu.

Cảm ơn

Answer 1

Topological ordering/phát hiện vòng lặp? (Thuật toán phân loại topo dừng lại nếu phát hiện thấy vòng lặp.)

Điều này sẽ gần giống với những gì bạn đang làm.

Answer 2

Trong thuật toán Khoa học/Máy tính, cấu trúc của bạn được gọi là directed graph. Bạn muốn có một "Directed Acyclic Graph" - đó là một không có chu kỳ trong đó.

Để tìm hiểu xem có chu kỳ trong biểu đồ, bạn có thể sử dụng thuật toán được gọi là Topological sorting. Nó cố gắng sắp xếp lại một biểu đồ để nếu A đề cập đến B thì A luôn xảy ra trước B theo thứ tự. Nó dừng lại nếu đồ thị có chu kỳ.

Nếu bạn muốn tìm tất cả các chu kỳ trong biểu đồ (hữu ích cho các thông báo lỗi) thì this stackoverflow question and answer cung cấp nhiều trợ giúp.

Là nền:
Graph = bất cứ điều gì với các nút liên kết bởi các cạnh (trong trường hợp các nút của bạn là công thức nấu ăn và tài liệu tham khảo là các cạnh).
Được chỉ định = các cạnh có chỉ đường. Trong trường hợp của bạn, điều này là đúng bởi vì 'A' đề cập đến 'B', không phải 'A' và 'B' với nhau.

Answer 3

Nhìn vào cycle detection.

Answer 4

Với điều kiện của bạn, tôi nghĩ cấu trúc bạn sẽ kết thúc là DAG.

Vì vậy, chúng tôi có thể tìm hiểu xem việc thêm nút mới có tạo chu kỳ nếu có thì chúng tôi không thêm nó nếu không chúng tôi thêm nó.

class Foo 
{ 
    public List<Foo> Reachables { get; set; } 

    public Foo() 
    { 
     this.Reachables = new List<Foo>(); 
    } 

    public bool Add(Foo other) 
    { 
     this.Reachables.Add(other); // add it 

     if(other.IsReachable(this)) // then see if it create a cycle 
     { 
      this.Reachables.Remove(other); // if yes remove it 
      return false; 
     } 
     else 
     { 
      return true; // else keep it 
     } 
    } 

    private bool IsReachable(Foo goal) 
    { 
     // BFS 

     Queue<Foo> nextQueue = new Queue<Foo>(); 
     List<Foo> traversed = new List<Foo>(); 

     bool found = false; 

     nextQueue.Enqueue(this); 

     while (!found) { 

      Foo node = null; 

      try { node = nextQueue.Dequeue(); } 
      catch { break; } 

      traversed.Add(node); 

      if (node.Equals(goal)) { 
       found = true; 
       break; 
      } 
      else 
      { 
       foreach (Foo neighbor in node.Reachables) 
        if (!traversed.Contains(neighbor) && !nextQueue.Contains(neighbor)) 
         nextQueue.Enqueue(neighbor); 
      } 
     } 
     return found; 
    } 

} 

class Program 
{ 
    static void Main(string[] args) 
    { 
     Foo A = new Foo(); 
     Foo B = new Foo(); 
     Foo C = new Foo(); 

     Console.WriteLine(C.Add(B)); 
     Console.WriteLine(B.Add(A)); 
     Console.WriteLine(A.Add(C)); 
     Console.WriteLine(C.Add(A)); 

    } 
} 

Output:

True 
True 
False 
True