Thông báo

Collapse
No announcement yet.

[bài tập lớn] Xây dựng một tập không dư thừa các đường đi ngắn nhất của một đoạn mạch logic

Collapse
X
 
  • Lọc
  • Giờ
  • Show
Clear All
new posts

  • [bài tập lớn] Xây dựng một tập không dư thừa các đường đi ngắn nhất của một đoạn mạch logic

    Chào các anh chị và các bạn em đang cần giúp đỡ để tìm hướng làm để thực hiện thuật toán như sau:

    Thuật toán: xây dựng một tập không dư thừa các đường đi ngắn nhất của một đoạn mạch đi qua một tập hợp các cung cho trước của đồ thị biểu diễn một mạch tổ hợp.

    Cho một tập M gồm các cung, cần phải xây dựng một tập S không dư thừa các đường đi qua mỗi cung của tập M ít nhất một lần.

    1. Chọn cung a tiếp theo từ M, tìm tất cả các đường nối cung này với các đầu vào của mạch, bắt đầu từ cung a. Ở đây chúng ta di chuyển theo hướng ngược lại dọc theo các cung của đồ thị biểu diễn mạch tổ hợp.

    2. Tìm tất cả các đường nối cung a với các đầu ra của mạch tổ hợp, bắt đầu từ cung a. Ta di chuyển dọc theo các cung thẳng của đồ thị biểu diễn mạch tổ hợp.

    3. Chọn đường đi ngắn nhất tìm được ở bước 1 và đường đi ngắn nhất tìm được ở bước 2. Chúng ta soạn từ chúng đường đi ngắn nhất s, bắt đầu từ đầu vào tương ứng của mạch tổ hợp và kết thúc ở đầu ra tương ứng của nó.

    4. Chúng ta có các đường dẫn s trong tập S.

    5. Thực hiện các bước 1-4 cho mỗi cung từ tập M.

    6. Kiểm tra từng con đường s từ S để tìm xem nó có thể bị loại bỏ hay không, sao cho tất cả các cung từ M đều bị che bởi các con đường còn lại. Nếu bạn có thể vứt nó đi, hãy vứt nó đi và quay lại bước 6. Nếu tất cả các đường dẫn ở bước 6 đã được xem xét, hãy chuyển sang bước 7.

    7. Tập các đường dẫn S không dư thừa được xây dựng. Thuật toán kết thúc.

    Vấn đề là em không thấy có thể sử dụng một ngôn ngữ mô tả phần cứng nào như VHDL, Verilog... để thực hiện được nó, nếu sử dụng một ngôn ngữ bậc cao kết hợp với ngôn ngữ mô tả phần cứng thì phải làm như thế nào để kết hợp được chúng nó để giải bài toán này ạ. Mong mọi người chỉ cho em hướng để giải quyết.

Về tác giả

Collapse

buffer Tìm hiểu thêm về buffer

Bài viết mới nhất

Collapse

Đang tải...
X