Преобразование рекурсивного алгоритма в Iterative

Question

Я пытаюсь реализовать следующий алгоритм для итеративного, но я не могу сделать это правильно. Может кто-нибудь, пожалуйста, помогите мне с этим. Его двухпартийный алгоритм совпадения, и у меня возникают проблемы с преобразованием функции bpm в итеративную.

// A DFS based recursive function that returns true if a 
// matching for vertex u is possible 
bool bpm(bool bpGraph[M][N], int u, bool seen[], int matchR[]) 
{ 
    // Try every job one by one 
    for (int v = 0; v < N; v++) 
    { 
     // If applicant u is interested in job v and v is 
     // not visited 
     if (bpGraph[u][v] && !seen[v]) 
     { 
      seen[v] = true; // Mark v as visited 

      // If job 'v' is not assigned to an applicant OR 
      // previously assigned applicant for job v (which is matchR[v]) 
      // has an alternate job available. 
      // Since v is marked as visited in the above line, matchR[v] 
      // in the following recursive call will not get job 'v' again 
      if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)) 
      { 
       matchR[v] = u; 
       return true; 
      } 
     } 
    } 
    return false; 
} 

// Returns maximum number of matching from M to N 
int maxBPM(bool bpGraph[M][N]) 
{ 
    // An array to keep track of the applicants assigned to 
    // jobs. The value of matchR[i] is the applicant number 
    // assigned to job i, the value -1 indicates nobody is 
    // assigned. 
    int matchR[N]; 

    // Initially all jobs are available 
    memset(matchR, -1, sizeof(matchR)); 

    int result = 0; // Count of jobs assigned to applicants 
    for (int u = 0; u < M; u++) 
    { 
     // Mark all jobs as not seen for next applicant. 
     bool seen[N]; 
     memset(seen, 0, sizeof(seen)); 

     // Find if the applicant 'u' can get a job 
     if (bpm(bpGraph, u, seen, matchR)) 
      result++; 
    } 
    return result; 
} 

Answer 1

Хитрость в том, что вам нужен пакет действий. Поэтому, когда вы входите в цикл, вы сначала добавляете в стек все, что будете делать после того, что было бы вашим рекурсивным вызовом, и THEN введет рекурсивный вызов. Они будут выполняться в обратном порядке, и когда вы будете делать во второй половине вы знаете, что произошло в первом тайме.

В псевдо-коде что-то вроде этого

function somethingRecursive(stuff): 
    beforeRecursive(stuff) 
    somethingRecursive(whatever) 
    afterRecursive(stuff) 

становится чем-то вроде этого:

while actions: 
    action = actions.pop() 
    if action.unwind: 
     afterRecursive(action.stuff) 
    else: 
     beforeRecursive(action.stuff) 
     actions.push(new Action(unwind, stuff)) 
     actions.push(new Action(recurse, whatever)) 

Answer 2

Наконец я получил это работает.

typedef struct 
{ 
    int uParam; 
    int vLocal; 
    int location; 
}bpmState; 

bool bpm_nr(bool bpGraph[M][N], int uParam, int matchR[]) 
{ 
    bool seen[N]; 
    memset(seen, 0, sizeof(seen)); 
    stack<bpmState> states; 
    states.push({ uParam, 0, 1 }); 
    bool rvalue = false; 
    while (!states.empty()) 
    { 
     auto state = states.top(); 
     states.pop(); 
     switch (state.location) 
     { 
     case 1: 
      for (int v = state.vLocal, u = state.uParam; v < N; v++) 
      { 
       if (bpGraph[u][v] && !seen[v]) 
       { 
        seen[v] = true; 
        if (matchR[v] < 0) 
        { 
         matchR[v] = u; 
         rvalue = true; 
        } 
        else 
        { 
         states.push({ u, v, 2 }); 
         states.push({ matchR[v], 0, 1 }); 
        } 
        break; 
       } 
      } 
      break; 
     case 2: 
      if (rvalue) 
      { 
       matchR[state.vLocal] = state.uParam; 
       rvalue = true; 
      } 
      else 
      { 
       states.push({ state.uParam, state.vLocal + 1, 1 }); 
      } 
      break; 
     } 
    } 
    return rvalue; 
}