为深度优先搜索生成状态

Question

所以在USACO上练习的时候，我卡在了这个问题上。

问题描述：房间里有N个lamp（一开始都是开机的）。 lamps 有 4 个开关，每个开关切换特定的 lamps，例如：

Switch 1 : Toggles all the lamps
Switch 2 : Toggles all ordered numbered lamps
Switch 3 : Toggles all even numbered lamps
Switch 4 : Toggles all numbers that have modulus 1 with 3 (1, 4, 9)

提供了一个数字 c，表示按下开关的总数。最初所有 lamp 都打开。还提供了最终状态中某些 lamp 的状态。

工作是列出灯泡可能的所有可能最终状态。

为此我想出了一个基于深度优先搜索的解决方案。我用数组中的一个元素表示每个灯泡，如果数组 [i-1] 为 1，则灯泡 i 打开，如果数组 [i-1] = 0，则关闭。这是我的代码

/**
* Created by hp on 21-05-2015.
*/
import java.util.*;
public class lamps {
public static void main(String[] args) {
    Scanner myScanner = new Scanner(System.in);
    int numLamps = myScanner.nextInt();
    int[] startState = new int[numLamps];
    for(int i = 0; i < numLamps; i++){
        startState[i] = 1;
    }
    int numSwitchPressed = myScanner.nextInt();
    int[] finalState = new int[numLamps];
    /*
        -1 represents the lamp's state in the final state,
        whose state is not stated , can be both on and off
     */
    for(int i = 0; i < numLamps; i++){
        finalState[i] = -1;
    }

    /*
        ON Lamps in the final state
     */
    int on = myScanner.nextInt();
    while(on != -1){
        finalState[on-1] = 1;
        on = myScanner.nextInt();
    }

    /*
        OFF Lamps in the final state
     */
    int off = myScanner.nextInt();
    while(off != -1){
        finalState[off-1] = 0;
        off = myScanner.nextInt();
    }

    //TESTING THE GENERATE STATES METHOD HERE
    ArrayList<int[]> nextStates = nextStates(startState);
    for(int[] x: nextStates){
        for(int y: x){
            System.out.print(y + " ");
        }
        System.out.println();
    }
    System.out.println("========================================");
    System.out.println("========================================");
    callSearch(finalState, numSwitchPressed);
}
/*
    Generate the states that are results of pressing each switch
    Switch 1 : Toggle all
    Switch 2 : Toggle odd numbered lamps(effectively indices 0,2,4,6, )
    Switch 3 : Toggle even numbered lamps(effectively indices 1, 3, 5, 7)
    Switch 4 : Toggle lamps numbered 3x+1 (1, 4, 7, 10, 13)
 */
public static ArrayList<int[]> nextStates(int[] presentState){
    int len = presentState.length;
    ArrayList<int[]> nextState = new ArrayList<int[]>();
    int[] switchOne = new int[len];
    int[] switchTwo = new int[len];
    int[] switchThree = new int[len];
    int[] switchFour = new int[len];

    // Switch One : Toggle All
    for(int i = 0; i < len; i++){
        switchOne[i] = 1 - presentState[i];
    }
    nextState.add(switchOne);

    //Switch Two : Toggle odd numbered lamps
    for(int i = 0; i < len; i++){
        if(i % 2 == 0){
            switchTwo[i] = 1 - presentState[i];
        }
        else{
            switchTwo[i] = presentState[i];
        }
    }
    nextState.add(switchTwo);

    // Switch Three : Toggle even numbered lamps
    // 1, 3, 5, 7 , 9
    for(int i = 0; i < len; i++){
        if(i % 2 != 0){
            switchThree[i] = 1 - presentState[i];
        }
        else{
            switchThree[i] = presentState[i];
        }
    }
    nextState.add(switchThree);

    // Switch four : Toggle 1, 4, 7, 10
    for(int i = 0; i < len; i++){
        if(i % 3 == 1){
            switchFour[i] = 1 - presentState[i];
        }
        else{
            switchFour[i] = presentState[i];
        }
    }
    nextState.add(switchFour);
    return nextState;
}
/*
    def searchFinal (cntSoFar, FixedCnt, currentState, FinalState):
        if cntSoFar == FixedCnt:
            if currentState == FinalState:
                print currentState
                return
            return
        ListOfNextStates = generatenextState(currentState)
        for each new_state in ListOfNextStates:
            searchFinal(cntSoFar+1, FixedCnt, new_state, FinalState)
 */
public static void searchFinal(int cntSoFar, int FixedCnt, int[] currentState, int[] finalState){
    if(cntSoFar == FixedCnt){
        if(same(currentState, finalState)){
            for(int i = 0; i < finalState.length; i++){
                System.out.print(currentState[i] + " ");
            }
            System.out.println();
            return;
        }
        return;
    }
    ArrayList<int[]> nextStates = nextStates(currentState);
    for(int[] states: nextStates){
        searchFinal(cntSoFar+1, FixedCnt, states, finalState);
    }
}
/*
    WRAPPER METHOD FOR searchFinal
 */
public static void callSearch(int[] finalState, int FixedCnt){
    int len = finalState.length;
    int[] start = new int[len];
    for(int i = 0; i < len; i++)
        start[i] = 1;
    ArrayList<int[]> firstCandidates = nextStates(start);
    for(int[] state: firstCandidates){
        searchFinal(0, FixedCnt, state, finalState);
    }
}
public static boolean same(int[] currentState, int[] finalState){
    int len = finalState.length;
    for(int i = 0; i < len; i++){
        if(finalState[i] != -1){
            if(currentState[i] != finalState[i])
                return false;
        }
    }
    return true;
}
}

如您所见，我正在 nextState 方法中生成下一个状态。使用相同的方法检查是否满足最终状态要求。

我的问题（对不起，上下文太长）：如果 lamp 的初始状态是 1111111111（比如 10 lamps，全部打开）并且 c 是 1（按下开关的次数allowed），则搜索的状态只有四种，即：

0000000000（按下开关 1）
0101010101（按下开关 2）
1010101010（按下开关 3）
0111011101（按下开关 4）

最终状态条件是lamp 7 应该关闭。（我们不关心任何其他 lamps）所以答案应该是

0000000000 (All are off)
0101010101 (1,3,5,7,9 are off)

但是评分者将答案显示为

0000000000
0101010101
0110110110

QUESTION: 评分者答案的第三种状态，这是从哪里来的？我的意思是因为 c 是 1（允许按下的开关数），lamp 的唯一可能状态是前面列出的 4。评分者答案中提到的 lamp 的第三种状态如何可能？

Answer 1

Switch 4 : Toggles all numbers that have modulus 1 with 3

开关 #1：0000000000 <-

开关#2：0101010101 <-

开关 #3：1010101010

开关#4：0110110110 <-

Answer 2

7 % 3 = 1

你可能忽略了这个事实。

Answer 3

您的解决方案思路是正确的，但您的代码是一场噩梦:(

将灯的状态想象成一个 N 位向量。对于N=4，0000代表全关，1111代表全开。

如果将 N 位向量分成 6 位的集合（当然不包括任何尾随位），则无论您执行哪些切换，每组都将具有完全相同的值。也就是说，如果 N >= 12，则位 0 到位 5 看起来与位 6 到位 11 完全一样。因此，您可以将每个开关操作表示为应用于 6 位向量的逐位操作。

DFS 是正确的起点，但您当前的 DFS 树有 4^c 个节点。利用循环检测和 6 位向量的有限大小来避免重复计算。

为深度优先搜索生成状态

Generate states for depth first search

java

algorithm

graph

depth-first-search

graph-algorithm