Bishop：找到从 A 到 B 的最短路径
Bishop: find shortest path from A to B
我目前正在尝试为以下问题找到解决方案：给定一个 8x8 的棋盘和一个主教和障碍物的数量，需要找到从当前主教位置到其他特定位置的最短路径。
更新
感谢所有响应者，我已经实施了一个解决方案。这是：
https://jsfiddle.net/heximal/teya2pcc/
/**************************************
Chess board logic functions
***************************************/
function p(x, y) {
return {
x: x,
y: y
};
}
function pos_equals(p1, p2) {
if (p1 == null || p2 == null) return false;
return p1.x == p2.x && p1.y == p2.y;
}
function human_pos(pos) {
return pos2alpha(pos.x, pos.y);
}
function pos2alpha(x, y) {
return alpha[x] + (y + 1);
}
function intpos2alpha(intpos) {
y = Math.trunc(intpos / 10);
x = intpos - (y * 10);
return alpha[x] + (y + 1);
}
function pos2int(pos) {
return pos.y * 10 + pos.x;
}
function int2pos(intpos) {
var y = Math.trunc(intpos / 10);
var x = pos_int - (y * 10);
return p(x, y);
}
function pos2path(pos, delim) {
if (pos == null) return "[]";
var res = [];
for (var i = 0; i < pos.length; i++) {
var p1 = pos[i];
var x = 0,
y = 0;
if (typeof p1 === 'object') {
x = p1.x;
y = p1.y;
} else {
y = Math.trunc(p1 / 10);
x = p1 - (y * 10);
}
res.push(pos2alpha(x, y));
}
if (delim == null) delim = "->"
return res.join(delim);
}
function cell_color(location) {
var color = 1;
if (location.x % 2 == 0 && location.y % 2 == 0)
color = 1;
if (location.x % 2 != 0 && location.y % 2 == 0)
color = 0;
if (location.x % 2 == 0 && location.y % 2 != 0)
color = 0;
if (location.x % 2 != 0 && location.y % 2 != 0)
color = 1;
return color;
}
function board_obj(pos) {
var res = 0;
if (pos.x < 0 || pos.x > 7 || pos.y < 0 || pos.y > 7)
res = "o";
else
res = board[7 - pos.y][pos.x];
return res;
}
/**************************************
Major find path functions
***************************************/
var iterations = 0;
// let's prevent scanning with particular iterations count
// to avoid very long execution
var max_iterations_count = 10000;
/*
----------------
| nw | | ne |
----------------
| | Bs | |
----------------
| sw | | se |
----------------
*/
var nw_vector = p(-1, 1);
var ne_vector = p(1, 1);
var se_vector = p(1, -1);
var sw_vector = p(-1, -1);
function find_path() {
if (target_pos == null || bishop_pos == null) {
alert("bishop and target both must be set");
return;
}
var path = [];
var start = new Date().getTime();
if (cell_color(bishop_pos) == cell_color(target_pos)) {
path = search_bfs(bishop_pos);
}
var end = new Date().getTime();
var dur = end - start;
output_result(path, dur);
}
function vector_point(pos, vector, shift) {
return p(pos.x + shift * vector.x, pos.y + shift * vector.y);
}
function possible_moves_from(pos) {
var vectors = [{
active: true,
vector: se_vector
}, {
active: true,
vector: sw_vector
}, {
active: true,
vector: nw_vector
}, {
active: true,
vector: ne_vector
}];
var shift = 1;
var res = [];
while (vectors[0].active || vectors[1].active || vectors[2].active || vectors[3].active) {
for (var j = 0; j < vectors.length; j++) {
if (vectors[j].active) {
iterations++;
var v_pos = vector_point(pos, vectors[j].vector, shift);
var l_obj = board_obj(v_pos);
if (l_obj == "o" || l_obj == "b") {
vectors[j].active = false;
} else {
res.push(v_pos.y * 10 + v_pos.x);
}
}
}
shift++;
}
return res;
}
function search_bfs(original_pos) {
// reset global iterations counter
iterations = 0;
var original_pos_int = pos2int(original_pos);
// create undirected graphs with all possible bishop positions
var vertices = {};
var pos = p(0, 0);
// if bishop cell color differs from color of left-bottom cell color (A1)
// than start with cell (A2)
if (cell_color(pos) != cell_color(original_pos)) {
pos.x = 1;
}
// let's convert cell positions {x: n, y: m} to integer representation
// int_pos = y+10 + x, e.g. B2 = 1 * 10 + 1 = 11
var target_pos_int = pos2int(target_pos);
for (var i = 0; i < 32; i++) {
var intpos = pos2int(pos);
var l_obj = board_obj(pos);
// if pos doesn't contain obstacle
// get a collection of all moves that bishop can make from pos
if (l_obj != "o") {
var possible_moves = possible_moves_from(pos);
vertices[intpos] = possible_moves;
}
pos.x += 2;
if (pos.x > 7) {
pos.x = pos.x % 2 == 0 ? 1 : 0;
pos.y++;
}
}
// initialize BFS queue (enqueue bishop position)
var queue = [original_pos_int];
// initialize BFS explored nodes collection
var explored = [original_pos_int];
// initialize parent nodes map
var parents = {};
while (queue.length > 0) {
iterations++;
if (iterations >= max_iterations_count) {
console.log("max iterations exceeded (" + max_iterations_count + "). stop searching");
return [];
}
var pos_int = queue.pop();
var y = Math.trunc(pos_int / 10);
var x = pos_int - (y * 10);
var pos = p(x, y);
var possible_moves = vertices[pos_int];
if (possible_moves == null) continue;
for (var j = 0; j < possible_moves.length; j++) {
var possible_move = possible_moves[j];
if (explored.indexOf(possible_move) < 0) {
parents[possible_move] = pos_int;
explored.push(possible_move);
if (target_pos_int == possible_move) {
queue = [];
break;
} else {
queue.splice(0, 0, possible_move);
}
}
}
}
// start backward traverse from target to bishop position
// and compose result path
var path = [];
var current = target_pos_int;
while (current != null) {
path.push(current);
current = parents[current];
}
// if path contains only one element, then path is not found
return path.length > 1 ? path : [];
}
一件重要的事情你在使用 BFS 时必须牢记：当你将元素入队时，你必须将它放在队列的开头而不是队列的结尾。
这就是我之前没能得到想要的结果的原因。
要弄清楚最短路径指的是最少的移动次数还是最少走过的田地数。无论哪种情况，都可以使用修改后的 depth-first search; 来解决问题。一个人必须存储当前的最短路径，这使得迭代实现成为可取的，因为它可能无法从调用堆栈中显式读取信息。
创建一个无向图，其中节点数为 32 减去障碍物数。每个节点代表一个黑色方块（对于黑色象）或白色方块（对于白色象）。每条边代表两个方块之间可能的移动。
在可以直接移动的任意两个节点之间添加一条边。如果您正在寻找最少的移动次数 - 该图可能未加权。如果您正在寻找最小移动距离 - 根据移动长度设置边缘权重。
您现在要做的就是找到两个所需节点之间的最短路径。如果图形未加权，则使用 BFS 或 modified-DFS。如果图表是加权的 - Dijkstra 会做。
使用BFS寻找最短路径：
给定无向无权图G，节点u和v之间的最短路径可以查到如下：
// --- BFS(u, v)-----------------------------
for each vertex w
do flag[w] := false;
pred[w] := -1 ; // predecessor of w
Q := empty queue;
flag[u] := true; // already visited
enqueue(Q, u)
while Q not empty
do w:= dequeue(Q);
for each x adjacent to w
if flag[x] = false
flag[x] := true;
pred[x] := w ;
if x = v
empty Q;
break;
else
enqueue(Q, x);
// --- ReportShortestPath(u, v)---------------
// backward path - v to u:
current := v;
do output current;
current := pred[currrent];
while current != -1
我目前正在尝试为以下问题找到解决方案：给定一个 8x8 的棋盘和一个主教和障碍物的数量，需要找到从当前主教位置到其他特定位置的最短路径。
更新
感谢所有响应者，我已经实施了一个解决方案。这是：
https://jsfiddle.net/heximal/teya2pcc/
/**************************************
Chess board logic functions
***************************************/
function p(x, y) {
return {
x: x,
y: y
};
}
function pos_equals(p1, p2) {
if (p1 == null || p2 == null) return false;
return p1.x == p2.x && p1.y == p2.y;
}
function human_pos(pos) {
return pos2alpha(pos.x, pos.y);
}
function pos2alpha(x, y) {
return alpha[x] + (y + 1);
}
function intpos2alpha(intpos) {
y = Math.trunc(intpos / 10);
x = intpos - (y * 10);
return alpha[x] + (y + 1);
}
function pos2int(pos) {
return pos.y * 10 + pos.x;
}
function int2pos(intpos) {
var y = Math.trunc(intpos / 10);
var x = pos_int - (y * 10);
return p(x, y);
}
function pos2path(pos, delim) {
if (pos == null) return "[]";
var res = [];
for (var i = 0; i < pos.length; i++) {
var p1 = pos[i];
var x = 0,
y = 0;
if (typeof p1 === 'object') {
x = p1.x;
y = p1.y;
} else {
y = Math.trunc(p1 / 10);
x = p1 - (y * 10);
}
res.push(pos2alpha(x, y));
}
if (delim == null) delim = "->"
return res.join(delim);
}
function cell_color(location) {
var color = 1;
if (location.x % 2 == 0 && location.y % 2 == 0)
color = 1;
if (location.x % 2 != 0 && location.y % 2 == 0)
color = 0;
if (location.x % 2 == 0 && location.y % 2 != 0)
color = 0;
if (location.x % 2 != 0 && location.y % 2 != 0)
color = 1;
return color;
}
function board_obj(pos) {
var res = 0;
if (pos.x < 0 || pos.x > 7 || pos.y < 0 || pos.y > 7)
res = "o";
else
res = board[7 - pos.y][pos.x];
return res;
}
/**************************************
Major find path functions
***************************************/
var iterations = 0;
// let's prevent scanning with particular iterations count
// to avoid very long execution
var max_iterations_count = 10000;
/*
----------------
| nw | | ne |
----------------
| | Bs | |
----------------
| sw | | se |
----------------
*/
var nw_vector = p(-1, 1);
var ne_vector = p(1, 1);
var se_vector = p(1, -1);
var sw_vector = p(-1, -1);
function find_path() {
if (target_pos == null || bishop_pos == null) {
alert("bishop and target both must be set");
return;
}
var path = [];
var start = new Date().getTime();
if (cell_color(bishop_pos) == cell_color(target_pos)) {
path = search_bfs(bishop_pos);
}
var end = new Date().getTime();
var dur = end - start;
output_result(path, dur);
}
function vector_point(pos, vector, shift) {
return p(pos.x + shift * vector.x, pos.y + shift * vector.y);
}
function possible_moves_from(pos) {
var vectors = [{
active: true,
vector: se_vector
}, {
active: true,
vector: sw_vector
}, {
active: true,
vector: nw_vector
}, {
active: true,
vector: ne_vector
}];
var shift = 1;
var res = [];
while (vectors[0].active || vectors[1].active || vectors[2].active || vectors[3].active) {
for (var j = 0; j < vectors.length; j++) {
if (vectors[j].active) {
iterations++;
var v_pos = vector_point(pos, vectors[j].vector, shift);
var l_obj = board_obj(v_pos);
if (l_obj == "o" || l_obj == "b") {
vectors[j].active = false;
} else {
res.push(v_pos.y * 10 + v_pos.x);
}
}
}
shift++;
}
return res;
}
function search_bfs(original_pos) {
// reset global iterations counter
iterations = 0;
var original_pos_int = pos2int(original_pos);
// create undirected graphs with all possible bishop positions
var vertices = {};
var pos = p(0, 0);
// if bishop cell color differs from color of left-bottom cell color (A1)
// than start with cell (A2)
if (cell_color(pos) != cell_color(original_pos)) {
pos.x = 1;
}
// let's convert cell positions {x: n, y: m} to integer representation
// int_pos = y+10 + x, e.g. B2 = 1 * 10 + 1 = 11
var target_pos_int = pos2int(target_pos);
for (var i = 0; i < 32; i++) {
var intpos = pos2int(pos);
var l_obj = board_obj(pos);
// if pos doesn't contain obstacle
// get a collection of all moves that bishop can make from pos
if (l_obj != "o") {
var possible_moves = possible_moves_from(pos);
vertices[intpos] = possible_moves;
}
pos.x += 2;
if (pos.x > 7) {
pos.x = pos.x % 2 == 0 ? 1 : 0;
pos.y++;
}
}
// initialize BFS queue (enqueue bishop position)
var queue = [original_pos_int];
// initialize BFS explored nodes collection
var explored = [original_pos_int];
// initialize parent nodes map
var parents = {};
while (queue.length > 0) {
iterations++;
if (iterations >= max_iterations_count) {
console.log("max iterations exceeded (" + max_iterations_count + "). stop searching");
return [];
}
var pos_int = queue.pop();
var y = Math.trunc(pos_int / 10);
var x = pos_int - (y * 10);
var pos = p(x, y);
var possible_moves = vertices[pos_int];
if (possible_moves == null) continue;
for (var j = 0; j < possible_moves.length; j++) {
var possible_move = possible_moves[j];
if (explored.indexOf(possible_move) < 0) {
parents[possible_move] = pos_int;
explored.push(possible_move);
if (target_pos_int == possible_move) {
queue = [];
break;
} else {
queue.splice(0, 0, possible_move);
}
}
}
}
// start backward traverse from target to bishop position
// and compose result path
var path = [];
var current = target_pos_int;
while (current != null) {
path.push(current);
current = parents[current];
}
// if path contains only one element, then path is not found
return path.length > 1 ? path : [];
}
一件重要的事情你在使用 BFS 时必须牢记：当你将元素入队时，你必须将它放在队列的开头而不是队列的结尾。
这就是我之前没能得到想要的结果的原因。
要弄清楚最短路径指的是最少的移动次数还是最少走过的田地数。无论哪种情况，都可以使用修改后的 depth-first search; 来解决问题。一个人必须存储当前的最短路径，这使得迭代实现成为可取的，因为它可能无法从调用堆栈中显式读取信息。
创建一个无向图，其中节点数为 32 减去障碍物数。每个节点代表一个黑色方块（对于黑色象）或白色方块（对于白色象）。每条边代表两个方块之间可能的移动。
在可以直接移动的任意两个节点之间添加一条边。如果您正在寻找最少的移动次数 - 该图可能未加权。如果您正在寻找最小移动距离 - 根据移动长度设置边缘权重。
您现在要做的就是找到两个所需节点之间的最短路径。如果图形未加权，则使用 BFS 或 modified-DFS。如果图表是加权的 - Dijkstra 会做。
使用BFS寻找最短路径：
给定无向无权图G，节点u和v之间的最短路径可以查到如下：
// --- BFS(u, v)-----------------------------
for each vertex w
do flag[w] := false;
pred[w] := -1 ; // predecessor of w
Q := empty queue;
flag[u] := true; // already visited
enqueue(Q, u)
while Q not empty
do w:= dequeue(Q);
for each x adjacent to w
if flag[x] = false
flag[x] := true;
pred[x] := w ;
if x = v
empty Q;
break;
else
enqueue(Q, x);
// --- ReportShortestPath(u, v)---------------
// backward path - v to u:
current := v;
do output current;
current := pred[currrent];
while current != -1