7
Tôi rơi qua a spreadsheet giải thích phương thức sắp xếp cả hàng và cột của ma trận chứa dữ liệu nhị phân sao cho số lượng thay đổi giữa các hàng liên tiếp và cột được giảm thiểu.Thuật toán để sắp xếp các hàng và cols theo độ tương tự
Ví dụ, bắt đầu với:
Sau 15 bước thủ công được mô tả trong các tab của spreadsheed, bảng dưới đây thu được:
Tôi muốn biết:
- tên chung của thuật toán hoặc phương pháp này là gì?
- cách áp dụng nó vào bảng lớn hơn (trong đó 2^n sẽ tràn ...)
- cách khái quát hóa dữ liệu đó thành dữ liệu nhị phân, chẳng hạn bằng khoảng cách Levenshtein?
- nếu có bất kỳ liên kết đến mã (Excel VBA, Python, ...) đã thực hiện điều này (nếu không tôi sẽ viết nó ...)
Cảm ơn!
Đây là con đường đuilton euclide trong {0,1}^n; Tôi nghĩ rằng có thể có các thuật toán xấp xỉ yếu tố liên tục vì hampath liên quan chặt chẽ với TSP (cả hampath và TSP là khó cho đồ thị chung), và chúng ta có các thuật toán xấp xỉ cho TSP, nhưng không mong đợi để giải quyết nó tối ưu - mặc dù Tôi không hoàn toàn chắc chắn rằng một bằng chứng cứng cho không gian cụ thể này tồn tại, tôi sẽ ngạc nhiên nếu điều này là trong P. Tôi không biết những gì VBA có thể làm, vì vậy tôi không thể cho bạn biết liệu bạn có thể thực hiện một xấp xỉ thuật toán ở đó. –
Có một cái nhìn thứ hai, khoảng cách thực sự không phải là euclide, nhưng khoảng cách Hamming; Tôi không biết bằng chứng về độ cứng hoặc thuật toán xấp xỉ cho cái đó, nhưng chúng có thể tồn tại. –
Liên quan: [Mã màu xám] (https://en.wikipedia.org/wiki/Gray_code), cũng có sẵn dưới dạng biến thể n-ary. – Norman