반복적 인 알고리즘을 반복적 인 알고리즘으로 변환하는데 어려움이 있습니다.

Question

저는 자바 스크립트에서 재귀 적 역 추적 미로 생성 알고리즘을 구현하려고했습니다. 이들은 주제에 대한 훌륭한 일련의 글을 읽은 후에 행해졌 다.

알고리즘의 재귀 적 버전은 아무 생각없이했지만, iterative equivalent은 저를 곤혹스럽게 만들었습니다.

나는이 개념을 이해할 수 있다고 생각했지만 내 구현은 분명히 잘못된 결과를 산출합니다. 나는 그 원인이 될 수있는 버그를 집어 넣으려고 노력했지만, 문제는 논리의 실패로 인한 것이라고 믿기 시작했지만, 물론 나는 어디를 보지 않고있다. 다음 반복 알고리즘

내 이해는 다음

• 스택은 셀 상태의 표현을 보유 생성된다.

• 각 표현에는 특정 셀의 좌표와 인접 셀에 액세스하는 방향 목록이 있습니다.

• 스택이 비어 있지는 않지만 스택 상단의 방향을 반복하면서 인접 셀을 테스트합니다.

• 유효 셀이 발견되면 스택 맨 위에 놓고 해당 셀을 계속합니다. 여기

내 재귀 구현 (다시 한 번를 keyDown 앞으로 단계) http://jsbin.com/urilan/14

을 그리고 여기 내 반복 구현 : : (참고 :를 keyDown 앞으로 단계)에 대한 http://jsbin.com/eyosij/2

감사합니다 도움.

편집 : 내 질문에 명확하지 않은 경우 사과드립니다. 나는 나의 문제를 더 설명하려고 노력할 것이다.

반복 솔루션을 실행하면 예기치 않은 다양한 동작이 발생합니다. 가장 먼저 알고리즘은 역 추적하기 전에 사용 가능한 모든 옵션을 모두 사용하지 않습니다. 오히려 하나의 유효 셀이 남아있을 때 무작위로 셀을 선택하는 것처럼 보입니다. 그러나 전반적으로 운동은 무작위로 보이지 않습니다.

var dirs = [ 'N', 'W', 'E', 'S' ]; 
var XD = { 'N': 0, 'S':0, 'E':1, 'W':-1 }; 
var YD = { 'N':-1, 'S':1, 'E':0, 'W': 0 }; 


function genMaze(){ 

var dirtemp = dirs.slice().slice(); //copies 'dirs' so its not overwritten or altered 
var path = [];       // stores path traveled. 

var stack = [[0,0, shuffle(dirtemp)]]; //Stack of instances. Each subarray in 'stacks' represents a cell 
             //and its current state. That is, its coordinates, and which adjacent cells have been 
             //checked. Each time it checks an adjacent cell a direction value is popped from 
             //from the list 

while (stack.length > 0) { 

    var current = stack[stack.length-1]; // With each iteration focus is to be placed on the newest cell. 

    var x = current[0], y = current[1], d = current[2]; 
    var sLen = stack.length;    // For testing whether there is a newer cell in the stack than the current. 
    path.push([x,y]);     // Store current coordinates in the path 

    while (d.length > 0) { 
    if(stack.length != sLen){ break;}// If there is a newer cell in stack, break and then continue with that cell 

    else { 
     var cd = d.pop(); 
     var nx = x + XD[ cd ]; 
     var ny = y + YD[ cd ]; 

     if (nx >= 0 && ny >= 0 && nx < w && ny < h && !cells[nx][ny]){ 

     dtemp = dirs.slice().slice(); 
     cells[nx][ny] = 1; 
     stack.push([ nx, ny, shuffle(dtemp) ]); //add new cell to the stack with new list of directions. 
                // from here the code should break from the loop and start again with this latest addition being considered. 


     } 
    } 

    } 

    if (current[2].length === 0){stack.pop(); } //if all available directions have been tested, remove from stack 


} 
return path; 
} 

나는 당신을 위해 질문을 정리하는 데 도움이되기를 바랍니다. 아직 물질이 누락 된 경우 알려 주시기 바랍니다.

다시 한번 감사드립니다.

Answer 1

저는 자바 스크립트가 좋지 않지만 반복적 인 코드를 구현하려고합니다. 스택에 For 색인도 저장해야합니다. 따라서 코드는 다음과 같습니다.

function genMaze(cx,cy) { 

    var dirtemp = dirs; //copies 'dirs' so its not overwritten 
    var path = [];       // stores path traveled.  
    var stack = [[cx, cy, shuffle(dirtemp), 0]]; // we also need to store `for` indexer 

    while (stack.length > 0) { 

     var current = stack[stack.length - 1]; // With each iteration focus is to be placed on the newest cell. 

     var x = current[0], y = current[1], d = current[2], i = current[3]; 
     if (i > d.length) { 
      stack.pop(); 
      continue; 
     } 
     stack[stack.length - 1][3] = i + 1; // for next iteration 

     path.push([x, y]); // Store current coordinates in the path 
     cells[x][y] = 1; 

     var cd = d[i]; 
     var nx = x + XD[cd]; 
     var ny = y + YD[cd]; 

     if (nx >= 0 && ny >= 0 && nx < w && ny < h && !cells[nx][ny]) { 

      dtemp = dirs; 
      stack.push([nx, ny, shuffle(dtemp), 0]); 
     } 
    } 
    return path; 
    } 

Answer 2

이 작은 코드가 도움이 될 수 있습니까?

/** 
Examples 
var sum = tco(function(x, y) { 
    return y > 0 ? sum(x + 1, y - 1) : 
     y < 0 ? sum(x - 1, y + 1) : 
     x 
}) 
sum(20, 100000) // => 100020 
**/ 

function tco(f) { 
    var value, active = false, accumulated = [] 
    return function accumulator() { 
    accumulated.push(arguments) 
    if (!active) { 
     active = true 
     while (accumulated.length) value = f.apply(this, accumulated.shift()) 
     active = false 
     return value 
    } 
    } 
} 

크레딧, 설명의 ANS 더 많은 정보를 정기적으로는 github에 https://gist.github.com/1697037

입니다 귀하의 코드를 수정하지에 이점이 있습니다, 그래서 너무 다른 상황에 적용 할 수있다.희망이 도움이 :)