Suppose there are five feature A, B,C, D, E with constraints B ！=3,C ！= 2, A ！=B, B！=C,C < D, A = D, E < A, E < B, E < C, E < D, B！=D Define the loss function as val({A = a, . . . , E = e})) = the number of violated constraints。 Apply greedy descent, write down a sequence of solutions obtained.（！=）表示不等于

同样地，我们可以使用贪心下降算法来求解此问题。首先，我们可以随机生成一个初始解，例如 A=1, B=3, C=2, D=2, E=0。然后，我们对每个特征进行局部搜索，以找到可以改进的解。

对于特征 A，由于它不能等于 B，因此我们可以将 A 的值改为 2，这样就满足了限制条件。

对于特征 B，由于它不能等于 3 或 D，因此我们可以将 B 的值改为 1，这样就满足了限制条件。

对于特征 C，由于它不能等于 2，因此我们可以将 C 的值改为 1，这样就满足了限制条件。

对于特征 D，由于它必须等于 A，因此我们可以将 D 的值改为 2，这样就满足了限制条件。

对于特征 E，由于它必须小于 A、B、C 和 D，因此我们无法对其进行改进。

最终，我们得到的最优解为 A=2, B=1, C=1, D=2, E=0，该解中没有违反任何限制条件，因此损失函数的值为 0。

相关问题

Suppose there are five feature A, B,C, D, E with constraints B , 3,C , 2, A , B, B , C,C < D, A = D, E < A, E < B, E < C, E < D, B , D Define the loss function as val({A = a, . . . , E = e})) = the number of violated constraints Apply greedy descent, write down a sequence of solutions obtained.

首先，我们可以通过绘制限制条件图来更好地理解问题：

E --- B --- D
|     |     |
|     C --- A
|_____|

在这个限制条件图中，箭头表示限制条件，例如 "B > C" 表示从 B 到 C 有一条箭头，表示 B 的值必须大于 C 的值。

接下来，我们可以使用贪心下降算法来求解此问题。首先，我们可以随机生成一个初始解，例如 A=1, B=2, C=3, D=1, E=0。然后，我们对每个特征进行局部搜索，以找到可以改进的解。

对于特征 A，由于它必须等于 D，因此我们可以将 A 的值改为 1，这样就满足了限制条件。

对于特征 B，由于它必须大于 E 和 C，因此我们可以将 B 的值改为 3，这样就满足了限制条件。

对于特征 C，由于它必须小于 B 和 D，因此我们可以将 C 的值改为 1，这样就满足了限制条件。

对于特征 D，由于它必须大于 C，因此我们可以将 D 的值改为 2，这样就满足了限制条件。

对于特征 E，由于它必须小于 A、B、C 和 D，因此我们无法对其进行改进。

最终，我们得到的最优解为 A=1, B=3, C=1, D=2, E=0，该解中没有违反任何限制条件，因此损失函数的值为 0。

• 802.11 supports CSMA/CA (CSMA with collision avoidance) for MAC protocol.  Suppose there are 4 stations. A wants to send to B. C is within range of A. D is within range of B but not within range of A.  A begins by sending an RTS (request to send) frame to B to request permission to send.  If B decides to grant permission, it replies a CTS (clear to send) frame.  Upon receipt of the CTS, A sends its frame and starts an ACK timer.  Upon the correct receipt of the data frame, B responds with an ACK frame, terminating the exchange.  For C, it is within range of A, it will receive the RTS frame. Then it asserts a kind of virtual channel busy for itself, indicated by NAV (network allocation vector).  For D, it does not hear the RTS, but it does hear the CTS, so it also asserts the NAV signal for itself翻译

802.11标准支持使用CSMA/CA（带冲突避免的CSMA）作为MAC协议。假设有4个站点，A想向B发送数据，C在A的范围内，D在B的范围内，但不在A的范围内。协议流程如下：

1. A先向B发送一个请求发送（RTS）帧，请求发送数据。

2. 如果B决定允许发送，它会回复一个清除发送（CTS）帧。

3. 收到CTS帧后，A会发送数据帧并启动一个确认（ACK）定时器。

4. 在正确接收到数据帧后，B会回复一个ACK帧，结束交换过程。

5. 对于C，它在A的范围内，会收到RTS帧。然后它为自己声明一种虚拟信道忙状态，即使用网络分配向量（NAV）信号表示。

6. 对于D，它没有收到RTS帧，但它会收到CTS帧，因此它也会为自己声明NAV信号。