Fourier - mạc tì kim tiêu nguyên pháp

Dẫn vào

Fourier —— mạc tì kim tiêu nguyên pháp( nguyên danh Fourier–Motzkin Elimination, tên gọi tắtFMEThuật toán ) là một loại dùng cho từ tuyến tính bất đẳng thức trung tiêu trừ lượng biến đổi toán học phương pháp.

Nó mệnh danh nguyên tự với ở 1827 năm cùng 1936 năm độc lập phát hiện nên thuật toán Joseph Fourier cùng Theodore Motzkin dòng họ.

Quá trình

Từ tuyến tính bất đẳng thức trung tiêu trừ một tổ lượng biến đổi, là chỉ thông qua đem quan hệ thức trung bao nhiêu cái nguyên tố hữu hạn thứ mà biến hóa, đánh tan trong đó nào đó nguyên tố, do đó giải quyết vấn đề một loại phương pháp.

Nếu tuyến tính bất đẳng thức trung sở hữu lượng biến đổi đều bị tiêu trừ, như vậy chúng ta sẽ được đến một cái thường bất đẳng thức. Bởi vì đương thả chỉ đương nguyên bất đẳng thức có giải khi, tiêu nguyên hậu bất đẳng thức mới vì thật, tiêu trừ sở hữu lượng biến đổi nhưng dùng cho kiểm tra đo lường bất đẳng thức hệ thống hay không có giải.

Suy xét một cái hàmCái bất đẳng thức hệ thống,Có từ $x_{1}$ Đến $x_{r}$ Cái lượng biến đổi, trong đó $x_{r}$ Vì muốn tiêu trừ lượng biến đổi. Căn cứHệ số ký hiệu ( chính, phụ hoặc không ),Trung tuyến tính bất đẳng thức có thể chia làm tam loại:

Hình thức vì $x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}$ Bất đẳng thức, đối với phạm vi từĐến $n_{A}$ ( $n_{A}$ Vì loại này bất đẳng thức số lượng ),Dùng $x_{r}\geq A_{j}(x_{1},\dots ,x_{r-1})$ Tỏ vẻ;
Hình thức vì $x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}$ Bất đẳng thức, đối với phạm vi từĐến $n_{B}$ ( $n_{B}$ Vì loại này bất đẳng thức số lượng ),Dùng $x_{r}\leq B_{j}(x_{1},\dots ,x_{r-1})$ Tỏ vẻ;
Không bao hàm $x_{r}$ Bất đẳng thức, thiết chúng nó cấu thành bất đẳng thức tổ vì $\phi$ .

Bởi vậy nguyên hệ thống đồng giá với

\max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq x_{r}\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\wedge \phi

Tiêu nguyên bao gồm sinh ra một cái đồng giá với $\exists x_{r}~S$ Hệ thống. Hiển nhiên, cái này công thức đồng giá với

\max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\wedge \phi

Bất đẳng thức

\max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))

Đồng giá với đối với $1 \leq i \leq n_{A}$ Thả $1\leq j\leq n_{B}$ ,Sở hữu $n_{A}n_{B}$ Cái bất đẳng thức $A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})$ Cấu thành bất đẳng thức tổ.

Bởi vậy, chúng ta đem nguyên hệ thốngThay đổi vì một cái khác tiêu rớt $x_{r}$ Hệ thống, cái này hệ thống có $(n-n_{A}-n_{B})+n_{A}n_{B}$ Cái bất đẳng thức. Đặc biệt mà, nếu $n_{A}=n_{B}=n/2$ ,Như vậy tân hệ thống bất đẳng thức cái số vì $n^{2}/4$ .

Ví dụ mẫu

Suy xét dưới bất đẳng thức hệ thống:

$2x-5y+4z \leq 10$

$3x-6y+3z \leq 9$

$-x+5y-2z \leq -7$

$-3x+2y+6z \leq 12$

Vì tiêu trừ,Chúng ta có thể căn cứViết lại bất đẳng thức:

$x \leq (10 + 5y - 4z)/2$

$x \leq (9 + 6y - 3z)/3$

$x \geq 7 + 5y - 2z$

$x \geq (-12 + 2y + 6z)/3$

Như vậy chúng ta được đến hai cái $\leq$ Bất đẳng thức cùng hai cái $\geq$ Bất đẳng thức; nếu mỗi cái $\leq$ Bất đẳng thức phía bên phải ít nhất là mỗi cái $\geq$ Bất đẳng thức phía bên phải, tắc hệ thống có một cái giải. Chúng ta có $2\times2$ Như vậy tổ hợp:

$7 + 5y - 2z \leq (10 + 5y - 4z)/2$

$7 + 5y - 2z \leq (9 + 6y - 3z)/3$

$(-12 + 2y + 6z)/3 \leq (10 + 5y - 4z)/2$

$(-12 + 2y + 6z)/3 \leq (9 + 6y - 3z)/3$

Hiện tại chúng ta có một cái tân thiếu một cái lượng biến đổi bất đẳng thức hệ thống.

Thời gian phức tạp độ

ỞCái bất đẳng thức thượng tiêu nguyên có thể nhiều nhất được đến $n^{2}/4$ Cái bất đẳng thức, bởi vậy liên tục vận hànhBước có thể được đến nhiều nhất $4(n/4)^{2^{d}}$ Song chỉ số phức tạp độ. Đây là bởi vì thuật toán sinh ra rất nhiều không cần thiết ước thúc ( mặt khác ước thúc ẩn hàm ước thúc ). Tất yếu ước thúc số lượng lấy chỉ một chỉ số tăng trưởng.

Có thể sử dụng quy hoạch tuyến tính (Linear Programming, LP) kiểm tra đo lường không cần thiết ước thúc.

Ứng dụng

Lý thuyết thông tin nhưng thực hiện tính chứng minh bảo đảm tồn tại tính năng tốt đẹp mã hóa phương án điều kiện. Này đó điều kiện thông thường sử dụng tuyến tính bất đẳng thức hệ thống miêu tả. Hệ thống lượng biến đổi bao gồm truyền tốc độ cùng phụ gia phụ trợ tốc độ. Thông thường, mọi người chỉ ở chỉ căn cứ vấn đề tham số ( tức truyền tốc độ ) tới miêu tả thông tín cơ bản hạn chế, bởi vậy thuật phụ trợ suất yêu cầu tiêu trừ thượng. Mà chúng ta đúng là thông qua phó lập diệp - mạc tì kim tiêu nguyên pháp tới làm được điểm này.

Thực hiện

Tại lập trình ngôn ngữ trung,Racket,Một loại căn cứ vào Lisp nhiều phạm thức biên trình ngôn ngữ ởfme - Fourier–Motzkin Elimination for Integer Systems)Trung đối FME thuật toán làm đơn giản hàm số đại số thực hiện.

Tham khảo tư liệu cùng mở rộng đọc

Rui-Juan Jing, Marc Moreno-Maza, Delaram Talaashrafi, "Complexity Estimates for Fourier-Motzkin Elimination",Journal of Functional Programming 16:2 (2006) pp 197-217.
Fourier–Motzkin elimination - Wikipedia
Fourier-Motzkin elimination and its dual
GE Liepins,Fourier-Motzkin elimination for mixed systems,1983

Bổn giao diện gần nhất đổi mới:2023/6/27 13:39:08,Đổi mới lịch sử
Phát hiện sai lầm? Tưởng cùng nhau hoàn thiện?Ở GitHub thượng biên tập này trang!
Bổn giao diện cống hiến giả:Enter-tainer,hbghlyj,iamtwz,isdanni,sshwy,Tiphereth-A,Xeonacid
Bổn giao diện toàn bộ nội dung ởCC BY-SA 4.0CùngSATAHiệp nghị chi điều khoản hạ cung cấp, phụ gia điều khoản cũng khả năng ứng dụng