Bài học cùng chủ đề
Trọng số của đồ thị và bài toán tìm đường đi ngắn nhất SVIP
Giả sử có sáu địa điểm , , , , , được nối với nhau theo những con đường với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số dưới đây:
Người giao hàng xuất phát từ điểm , đi qua các địa điểm còn lại để giao hàng và trở về địa điểm ban đầu. Độ dài quãng đường đi thỏa mãn điều kiện trên sao cho người giao hàng phải di chuyển là ngắn nhất là
Trả lời:
Sử dụng thuật toán láng giềng gần nhất, độ dài quãng đường của bài toán người giao hàng đối với đồ thị ở hình dưới đây bằng bao nhiêu?
Trả lời:
Một nhân viên của bảo tàng nghệ thuật đang có kế hoạch giới thiệu nội dung cuộc triển lãm của bảo tàng đến ba trường học trong khu vực. Người đó muốn đến từng trường và quay trở lại bảo tàng sau khi thăm cả ba trường. Thời gian di chuyển (đơn vị: phút) giữa các trường học và giữa bảo tàng với mỗi trường học được mô tả trong hình dưới đây. Thời gian đi ít nhất xuất phát từ viện bảo tàng bằng
Cho đồ thị có trọng số như hình vẽ:
Độ dài đường đi bằng
Cho đồ thị có trọng số như hình dưới đây:
Độ dài của đường đi bằng
Cho đồ thị có trọng số như hình vẽ:
Độ dài đường đi bằng
Có bốn địa điểm với độ dài quãng đường giữa các địa điểm (đơn vị: kilômét) mô tả trong hình dưới đây.
Sử dụng thuật toán láng giềng gần nhất, chu trình xuất phát từ một đỉnh đi qua tất cả các địa điểm, mỗi địa điểm đúng một lần sao cho tổng độ dài các cạnh của chu trình nhỏ nhất là
Trả lời:
Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở dưới đây (đơn vị: nghìn đồng).
Xuất phát từ điểm , chi phí thấp nhất đi qua tất cả các địa điểm bằng
