0

我一直在研究魔方计时器网站，我需要做一个加扰算法。我将讨论加扰算法应该如何工作：每张脸都有自己的字母，它是首字母。例如，如果你想移动正面，你会写“F”。如果你想移动右边的脸，你会写“R”，依此类推。只需注意底面是D，至于向下。所以你有 DURLB F。如果那个字母后面什么都没有，你顺时针转动它。如果有撇号“'”，则逆时针转动。如果有一个 2，你转动它两次。现在的问题是你不能有 2 个相同的字母并排在一起，因为它们会取消（例如“.. U U' ...”与什么都不做一样。到目前为止，我已经在我的算法。当你有一个字母时，问题就来了，然后它正好相反，然后是第一个字母，（例如“.. UD U'...”（表示顺时针向上，顺时针向下，逆时针向上））。我不知道如何检查这些并自动避免它们。这是代码：

<div id=“Scramble”&gt;</div>
<script>
generateScramble();

function generateScramble() {

  // Possible Letters
  var array = new Array(" U", " D", " R", " L", " F", " B")

  // Possible switches
  var switches = ["", "\'", "2"]; 

  var array2 = new Array(); // The Scramble.

  var last = ''; // Last used letter

  var random = 0;

  for (var i = 0; i < 20; i++) {
      // the following loop runs until the last one 
      // letter is another of the new one
      do {
         random = Math.floor(Math.random() * array.length);
      } while (last == array[random]) 

  // assigns the new one as the last one
  last = array[random];

  // the scramble item is the letter
  // with (or without) a switch
  var scrambleItem = array[random] + switches[parseInt(Math.random()*switches.length)];

  array2.push(scrambleItem); // Get letters in random order in the array.
  }

  var scramble = "Scramble: ";

  // Appends all scramble items to scramble variable
  for(i=0; i<20; i++) {
     scramble += array2[i];
  }

  document.getElementById("Scramble").innerHTML = scramble; // Display the scramble
}
</script>
4

1 回答 1

1

对于初学者来说，魔方的上帝数字是 20 ，所以你只有 20 步而不是 25 步。我假设你不是在做加扰（正如你的标题所暗示的那样），而是为genere&test 求解器类型生成解决方案命令字符串。有太多的序列相互抵消，并且检查所有序列很可能比实际尝试它们要慢。

问题是，甚至O(n^20)是巨大的，你需要降低20. 这是通过 LUT 保持半解决状态来完成的。例如，为 5 轮加扰的所有组合创建表保持状态。然后将其用作结束条件，将您的求解器变为O(n^15 + n^5) = O(n^15)...

于 2017-11-13T07:41:20.903 回答