棋盘上骑士的最短路径

Question

我一直在为即将到来的编程比赛进行练习，我偶然发现了一个我完全困惑的问题。然而，我觉得这是一个我现在应该学习的概念，而不是祈祷它永远不会出现。

基本上，它涉及棋盘上的骑士棋子。您有两个输入：起始位置和结束位置。目标是计算并打印骑士到达目标位置可以采取的最短路径。

我从来没有处理过最短路径式的事情，我什至不知道从哪里开始。我采用什么逻辑来解决这个问题？

附：如果有任何相关性，他们希望您通过允许骑士移动到由骑士可以进行的（可能）八个动作形成的正方形的四个角来补充骑士的正常动作，假设正方形的中心是骑士的位置。

Answer 1

你有曲线图在这里，在那里所有可用的动作是连接(value=1)，并且不可用的动作是连接断开(value=0)，稀疏矩阵将如：

(a1,b3)=1,
(a1,c2)=1,
  .....

和最短的路径的两点在一个曲线图可以发现使用 http://en.wikipedia.org/wiki/Dijkstra's_algorithm

伪码从维基百科页:

function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

编辑：

1. 作为白痴，所述的使用 http://en.wikipedia.org/wiki/A*_algorithm 可以更快。
2. 最快的方式， 预先计算的距离 并保存到一个8×8充分的矩阵。好吧，我会叫这作弊， 和工作仅仅是因为问题 是很小的。但有时候比赛 将检查如何快速程序 运行。
3. 主要的一点是，如果你正在准备 用一种编程的竞争，你必须知道 共同的算法，包括Dijkstra的。一个好的起点是阅读 Introduction to Algorithms ISBN0-262-03384-4.或者你可以尝试维基百科 http://en.wikipedia.org/wiki/List_of_algorithms

Answer 2

编辑： 看人妖的回答，在那里他固定的公式这里介绍

实际上有一个O（1）式

这是我已对其进行可视化的图像（平方骑士可以在N个到达^个移动都涂上同一颜色）。

你能在这里看到的模式？

虽然我们可以看到的图案，实在是很难找到的功能f( x , y )回返的移动次数须广场( 0 , 0 )原点( x , y )去

但这里是公式作品时0 <= y <= x

int f( int x , int y )
{
    int delta = x - y;

    if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );
}

注意：此问题针对于 SACO 2007第1天点击 而解决方案是这里

Answer 3

这里有一个正确的O(1)解决方案，但是对的情况下骑士的动作就像一个国际象棋骑士才，并在一个无限的国际象棋委员会：

https://jsfiddle.net/graemian/5qgvr1ba/11/

关键找到这是要注意的模式出现的，当你提请委员会。在下面的示意图，编号在广场移动的最小数量需要达到这方(可使用的广度优先的搜索，找到这个):

因为解决方案是对称的全轴线和斜杆，我只画x>=0和y>=x的情况。

的左下方框是起始位置和数字在块代表最小数量的移动到达到这些区块。

有3个模式来通知：

• 递增的蓝色的垂直组的4
• "主要的"红线(他们跑左上到底-对，就像一个反斜杠)
• "二级"绿线(相同的方向红色)

(让你看到这两组条对角线以左上到下的权利。他们有一个不断移动计数。左右上角的对角线都复杂得多。)

你可以推导出公式中的每一个。黄色区块是特殊情况。这样的解决方案变为：

function getMoveCountO1(x, y) {

    var newXY = simplifyBySymmetry(x, y);

    x = newXY.x;
    y = newXY.y;

    var specialMoveCount = getSpecialCaseMoveCount(x ,y);

    if (specialMoveCount !== undefined)
        return specialMoveCount;

    else if (isVerticalCase(x, y))
        return getVerticalCaseMoveCount(x ,y);

    else if (isPrimaryDiagonalCase(x, y))
        return getPrimaryDiagonalCaseMoveCount(x ,y);

    else if (isSecondaryDiagonalCase(x, y))
        return getSecondaryDiagonalCaseMoveCount(x ,y);

}

最难受的垂直组：

function isVerticalCase(x, y) {

    return y >= 2 * x;

}

function getVerticalCaseMoveCount(x, y) {

    var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);

    var groupIndex = Math.floor( normalizedHeight / 4);

    var groupStartMoveCount = groupIndex * 2 + x;

    return groupStartMoveCount + getIndexInVerticalGroup(x, y);

}

function getIndexInVerticalGroup(x, y) {

    return getNormalizedHeightForVerticalGroupCase(x, y) % 4;

}

function getYOffsetForVerticalGroupCase(x) {

    return x * 2;

}

function getNormalizedHeightForVerticalGroupCase(x, y) {

    return y - getYOffsetForVerticalGroupCase(x);

}

看到小提琴的其他情况。

也许还有更简单的或更典雅的模式，我错过了什么？如果是这样，我很想看到他们。特别是，我注意到一些对角线模式在蓝色的垂直的情况，但我没有探讨它们。无论如何，这种解决方案仍然满足O(1)款的约束。

Answer 4

这是我最近遇到了非常有趣的问题。寻找一些解决方案后，我试图恢复在中美合作所给出的解析公式（O(1) time and space complexity） 2007年1日 的解决方案

我想要欣赏格雷姆·派尔获得非常好的可视化这帮助我解决公式。首先

出于某种原因（可能为了简化或美容或只是一个错误）他们移动minus符号到floor操作，其结果是他们有错式floor(-a) != -floor(a) for any a。

下面是正确的解析公式：

var delta = x-y;
if (y > delta) {
    return delta - 2*Math.floor((delta-y)/3);
} else {
    return delta - 2*Math.floor((delta-y)/4);
}

在公式适用于所有（X，Y）对除了（1,0）（施加轴和对角对称性之后）和（2,2）角的情况下，这是不能满足于图案，并在下面的代码片断硬编码：

function distance(x,y){
     // axes symmetry 
     x = Math.abs(x);
     y = Math.abs(y);
     // diagonal symmetry 
     if (x < y) {
        t = x;x = y; y = t;
     }
     // 2 corner cases
     if(x==1 && y == 0){
        return 3;
     }
     if(x==2 && y == 2){
        return 4;
     }
    
    // main formula
    var delta = x-y;
		if(y>delta){
  		return delta - 2*Math.floor((delta-y)/3);
  	}
  	else{
  		return delta - 2*Math.floor((delta-y)/4);
  	}
}


$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
	html += '<tr>';
	for (var x = 0; x <= 20; x++){
  	html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
  }
  html += '</tr>';
}

html = '<table>'+html+'</table>';
$body.append(html);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>