文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 骑士巡游问题的贪心算法求解
侵权投诉

骑士巡游问题的贪心算法求解

国际象棋中,最有趣的问题之一就是骑士问题,最初由数学家欧拉提出的。问题如下:能否让骑士在空棋盘上移动,在64个方格中经过且经过一次?说明一下,骑士的移动按L型路线,有点类似中国的马走日。
下面是用贪心算法求解的全部代码。程序是用C#编写的。贪心选择的依据是accessibility数组,这个数组记录了每个格所有可能的移动方向,中间的格子有8种移动方向,而越往边缘可选择的越少。而骑士总是选择数值小的先走,因为数值大更容易到达,所以先把难到达的走完,再走容易的。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _8._22 {
class Program {
static void Main(string[] args)
{
//棋盘
int[,] board = new int[8, 8];
//棋盘上每格可移动的可能
int[,] accessibility = {{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}
};
//8种走法对应的水平和垂直位移量
int[] horizontal = { 2, 1, -1, -2, -2, -1, 1, 2 };
int[] vertical = { -1, -2, -2, -1, 1, 2, 2, 1 };
//记录骑士最多行走的步数
int steps = 0;
//开始循环,定义64个起始位置[0,0]-[7,7]
for(int row=0;row<8;row++)
for (int column = 0; column < 8; column++) {
for (int i = 0; i < board.GetLength(0); i++)
for (int j = 0; j < board.GetLength(1); j++)
board[i, j] = 0;
//骑士起始位置
int currentRow = row;
int currentColumn = column;
//进行64次循环,尝试走64步
for (int i = 1; i <= 64; i++) {
//记录骑士当前位置
try {
board[currentRow, currentColumn] = i;
}
catch {
Console.WriteLine("{0} {1}", currentRow, currentColumn);
}
//初始化nextMove,nextValue
int nextMove = 0;
int nextValue = 9;
//尝试走移动8步
for (int moveNumber = 0; moveNumber < 8; moveNumber++) {
//如果这一步是可行的,即没有跃出棋盘

第1页

你可能喜欢

热门文档

相关文档

  • 使用回溯算法求解骑士游历问题

    骑士游历问题 纯数学方法 5页 免费 骑士巡游问题的贪心算法求... 2页 2... 如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...

  • 【论文】马步遍历问题与骑士巡游问题的回溯算法

    而骑士巡游问题实际是带有约束条件的马步遍历问题,因此在用程序求解的时候可以一并求解。本文给出求解这一问题的回溯算法之c++语言程序。...

  • 骑士巡游问题的回溯法分析

    骑士巡游问题的回溯法分析:骑士巡游问题中骑士每进一步都会面临下一步的多种选择,最终解也由 N 步的单步解 构成,若尝试到某一步时发现已经无法继续,就返回到前一...

  • 【论文】骑士巡游问题的一个遗传算法

    骑士巡游问题的一个遗传算法_数学_自然科学_专业资料。用一个遗传算法来求解骑士巡游问题。算法将骑士巡游问题转化为求解无向图的汉密尔顿通路问题,通过对无向图的...

  • 【论文】基于骑士巡游问题的文件加密算法

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 基于骑士巡游问题的文件加密算法 先简介骑士...

  • 【论文】贪心算法求解k—median问题

    贪心算法求解k—median问题_专业资料。文章讨论了用贪心算法解k-median问题以及其试验结果。首先提出了一个解k-median问题的简单贪心算法.然后对求解质量和求解的...

  • 骑士巡游问题 C++ 报告

    10 3 一、题目描述编写程序求解骑士巡游问题:在 n 行 n 列的棋盘上(如 n=5),假设一位骑士(按象棋 中“马走日”的行走法)从初始坐标位置(x1,y1)出发,...

  • 贪心算法求解最优服务次序问题

    实验名称:贪心算法实例编程 实验名称:贪心算法实例编程 求解最优服务次序问题 1、实验目的: 1) 理解贪心算法的概念 2) 掌握贪心算法的基本要素 3) 掌握设计贪心...

  • 骑士巡游数据结构课程设计完成版

    17 一. 课程设计的目的许多数学家, 程序员在不断寻早改善求解方法。 1. 骑士巡游的求解是一个经典的算法, 对骑士巡游问题的研究中可包括贪心算法,回溯算法,...

  • 贪心算法求解问题(优化版)

    贪心算法求解问题(优化版)_互联网_IT/计算机_专业资料。算法设计与分析贪心算法求解问题问题分析:此问题为程序最优存储问题,问题要求最后存储的两个磁带上的长 度...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email