alpha-beta剪枝
网站建设哪家好，找创新互联公司！专注于网页设计、网站建设、微信开发、小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了农安免费建站欢迎大家使用！
具体问题具体答。。方法就是设计个估值用的函数就够了
以下是现写的 实现了两人对战 自己复制后运行把 没什么难度 类名 Games
import java.util.Scanner;
public class Games {
private String board[][];
private static int SIZE = 17;
private static String roles = "A玩家";
//初始化数组
public void initBoard() {
board = new String[SIZE][SIZE];
for (int i = 0; i SIZE; i++) {
for (int j = 0; j SIZE; j++) {
// if(i==0){
// String str = "";
// str += j+" ";
// board[i][j]= str;
// }else if(i!=0j==0){
// String str = "";
// str += i+" ";
// board[i][j]= str;
// }else{
board[i][j] = "╋";
// }
}
}
}
//输出棋盘
public void printBoard() {
for (int i = 0; i SIZE; i++) {
for (int j = 0; j SIZE; j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
}
//判断所下棋子位置是否合理
public boolean isOk(int x, int y) {
boolean isRight = true;
if (x = 16 || x 1 || y = 16 | y 1) {
//System.out.println("输入错误，请从新输入");
isRight = false;
}
if (board[x][y].equals("●") || board[x][y].equals("○")) {
isRight = false;
}
return isRight;
}
//判断谁赢了
public void whoWin(Games wz) {
// 从数组挨个查找找到某个类型的棋子就从该棋子位置向右，向下，斜向右下 各查找5连续的位置看是否为5个相同的
int xlabel;// 记录第一次找到某个棋子的x坐标
int ylabel;// 记录第一次找到某个棋子的y坐标
// ●○╋
// 判断人是否赢了
for (int i = 0; i SIZE; i++) {
for (int j = 0; j SIZE; j++) {
if (board[i][j].equals("○")) {
xlabel = i;
ylabel = j;
// 横向找 x坐标不变 y坐标以此加1连成字符串
String heng = "";
if (i + 5 SIZE j + 5 SIZE) {
for (int k = j; k j + 5; k++) {
heng += board[i][k];
}
if (heng.equals("○○○○○")) {
System.out.println(roles+"赢了！您输了！");
System.exit(0);
}
// 向下判断y不变 x逐增5 连成字符串
String xia = "";
for (int l = j; l i + 5; l++) {
xia += board[l][j];
// System.out.println(xia);
}
if (xia.equals("○○○○○")) {
System.out.println(roles+"赢了！您输了！");
System.exit(0);
}
// 斜向右下判断
String youxia = "";
for (int a = 1; a = 5; a++) {
youxia += board[xlabel++][ylabel++];
}
if (youxia.equals("○○○○○")) {
System.out.println(roles+"赢了！您输了！");
System.exit(0);
}
}
}
}
}
// 判断电脑是否赢了
for (int i = 0; i SIZE; i++) {
for (int j = 0; j SIZE; j++) {
if (board[i][j].equals("●")) {
xlabel = i;
ylabel = j;
// 横向找 x坐标不变 y坐标以此加1连成字符串
String heng = "";
if (j + 5 SIZE i + 5 SIZE) {
for (int k = j; k j + 5; k++) {
heng += board[i][k];
}
if (heng.equals("●●●●●")) {
System.out.println(roles+"赢输了！您输了！");
System.exit(0);
}
// 向下判断y不变 x逐增5 连成字符串
String xia = "";
for (int l = i; l i + 5; l++) {
xia += board[l][ylabel];
// System.out.println(xia);
}
if (xia.equals("●●●●●")) {
System.out.println(roles+"赢了！您输了！");
System.exit(0);
}
// 斜向右下判断
String youxia = "";
for (int a = 1; a = 5; a++) {
youxia += board[xlabel++][ylabel++];
}
if (youxia.equals("●●●●●")) {
System.out.println(roles+"赢了！您输了！");
System.exit(0);
}
}
}
}
}
}
public static void main(String[] args) {
Games wz = new Games();
Scanner sc = new Scanner(System.in);
wz.initBoard();
wz.printBoard();
while (true) {
System.out.print("请"+roles+"输入X，Y坐标，必须在0－15范围内，xy以空格隔开,输入16 16结束程序");
int x = sc.nextInt();
int y = sc.nextInt();
if (x == SIZE y == SIZE) {
System.out.println("程序结束");
System.exit(0);
}
if (x SIZE || x 0 || y SIZE | y 0) {
System.out.println("输入错误，请从新输入");
continue;
}
//如果roles是A玩家 就让A玩家下棋，否则就让B玩家下棋。
if (wz.board[x][y].equals("╋")roles.equals("A玩家")) {
wz.board[x][y] = "○";
wz.printBoard();
//判断输赢
wz.whoWin(wz);
}else if(wz.board[x][y].equals("╋")roles.equals("B玩家")){
wz.board[x][y] = "●";
wz.printBoard();
//判断输赢
wz.whoWin(wz);
} else {
System.out.println("此处已经有棋子,从新输入");
continue;
}
if(roles.equals("A玩家")){
roles = "B玩家";
}else if(roles.equals("B玩家")){
roles = "A玩家";
}
}
}
}
同意楼上，最长路径是NPC问题，不存在多项式算法。
证明是简单的：
1、最长无环路问题的判定版本是“给定有向图D和整数k，问D中是否存在长度大于或等于k的无环路”（这一表述对有权图和无权图都有效）。
2、将Hamilton路问题规约到最长无环路问题（的判定版本）是显然的：输入一个n顶点的有向图D，直接问：有向图D中是否存在长度大于等于n-1的无环路？
简言之，对任意n顶点的有向图D，假如能够D中的找到最长无环路P，那么就能立即知道D中是否存在Hamilton路（只需看P的长度是否为n-1即可），从而最长无环路问题是NPC。
小规模就直接DFS吧。大规模的时候DFS剪枝。不过确实不好做呀。
有向无圈图的话可以用dijstra贪心，或者简单用folyed算法就可以了（把最小化变为最大化）。
有圈的话您……或者能缩圈么？可以考虑。总之比较复杂。
1、是选择学习的编程语言，计算机语言的种类繁多，但是大体可以分为机器语言，汇编语言，高级语言以及脚本语言。
2、学习编程的过程中入门是一个很重要的过程，尤其是对于编程一点都不了解的朋友，看着那些密密麻麻看不懂的代码，什么热情都被浇灭了，从而就此放弃了学习编程，因此选择编程的入门方式十分重要。
3、可以从网上获取到我们需要的知识，自然也包括了学习编程，现在很多编程语言都出了视频教程，而且还不止一家，我们可以挑选最适合自己的视频教程来学习。
4、光看不练假把式，每当我们看完一节视频教程的时候，我们就应该把讲述的这些内容自己多练习几遍，直到完全掌握，这样再去看下一节的视频教程，千万不要光看不练，我们的目的不是为了看视频而看视频，而是为了掌握知识，只有掌握了才是自己的。
5、当我们累计到一定程度的知识之后就可以做一个简单的项目了，一是为了巩固所学的知识，把我们所学的知识串联起来，二是为了以后的工作做准备，毕竟早点熟悉以后的工作内容才能早点上手。
编程最容易让人放弃的就是两个阶段，一个就是入门阶段，一个就是觉得什么都会学了，但是什么都做不成的阶段，入门的话我们可以选择视频教程，相对于书籍来说小编觉得比较好，如果遇到第二个阶段可以做个项目，把各个知识点连接起来，在做项目的过程中查漏补缺，这样做的话应该有利于你的编程学习之路。
重庆分公司
重庆分公司
