Chủ đề này có 2 trả lời

[L_Euler]

mình đang gặp một vấn đề này chưa biết giải quyết thế nào, nhờ anh em xem giúp:

 

cho trước một vector $f \in \left[0, 1 \right]^N$ với $N$ rất lớn. người ta cần phân hoạch tập hữu hạn $S = \left \{1, 2, 3,...,N \right \}$ thành một số tập con không rỗng $S_i$ chứa các số nguyên liên tiếp và đôi một không giao nhau sao cho i) số lượng các tập con được phân hoạch là ít nhất có thể, và ii) đại lượng  $\sum_i\sigma_i^2$ đạt giá trị cực tiểu, trong đó $\sigma_i^2$ là phương sai của các giá trị của vector $f$ trong tập $S_i$. các giả thiết đặt ra có thể quy về bài toán tối ưu sau đây:

$$    \left [\widehat{n}, \widehat{\sigma}_1,..., \widehat{\sigma}_{\widehat{n}} \right] = argmin_{n, \sigma_1,..., \sigma_{n}} \left(n + \lambda \sum_{i=1}^{n} \sigma_i^2 \right),$$

trong đó $\lambda > 0$ là một giá trị trade off giữa hai đại lượng trong hàm mục tiêu.

 

merci d'avance!

L_Euler

[perfectstrong]

Mình chưa hiểu rõ vấn đề lắm. Mình diễn giải lại như sau có đúng ý bạn không?

Đại để là $f$ biểu diễn việc chọn hay không chọn một số $x$ trong tập $S$: với mọi $x \in S$, $f(x)=1$ nếu $x$ nằm trong vecteur $f$, còn không $f(x)=0$. Sau đó, trong mỗi phân hoạch $S_i$, gọi $f_i = \{ x \in S_i \, | \, f(x) = 1 \}$, và tính $\sigma_i^2$ là phương sai của $f_i$.

Bây giờ phải tìm số phân hoạch $n$ nhỏ nhất để $n + \lambda \sum \sigma_i ^2$ đạt GTNN?

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 26-09-2023 - 02:56

[L_Euler]

không, vector $f$ chứa các số trong đoạn $[0, 1]$ chứ không phải tập $\left \{0, 1 \right \}$.;-)

 

mình vừa mới chứng minh được trong trường hợp $\lambda <1$ thì bài toán không có nghiệm nhưng trong trường hợp còn lại $\lambda \ge 1$ thì bài toán phức tạp hơn hẳn.