用贪心法解决八数码问题8-puzzle python实现

用贪心法解决八数码问题8-puzzle python实现

1、问题描述

3×3九宫棋盘，放置数码为1 -8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。

要求：根据给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局，找到合法的走步序列。

2、解题思路

如果从初始状态可以到达目标状态，贪心法可以采用如下的步骤。
1、首先将初始状态s放入open表，计算代价函数f(s)。（这里代价函数f我用的是此状态与目标状态各数字不同的个数）

2、判断open表是否为空：
若为空，结束
若不为空，取出open表里面代价值最小的状态a移到closed列表。

3、判断a是否为目标状态：
若a为目标状态，成功并结束；
若a不是目标状态，扩展a，将得到的后继状态放入open表中。

4、重复2-3直到结束条件出现。

3、代码实现（Python）

# -*- coding: utf-8 -*-
"""
Created on Wed May  9 15:45:01 2021

@author: DJ MR.L
"""

import copy

#获取状态函数
def get_state():
    ls = []
    for i in range(3):
        tmp = input(f"请输入状态{i}：").split()
        ls.append([int(j) for j in tmp])
    return ls

#获取差别个数函数,相当于代价函数
def diff(vcc1,vcc2):
    count = 0
    n = len(vcc1)
    for i in range(n):
        for j in range(n):
            if vcc1[i][j] != vcc2[i][j]:
                count += 1
    return count

#找到0的位置
def get_index(vcc):
    row, col = 0, 0 #初始化0的位置
    n = len(vcc)
    for i in range(n):
        for j in range(n):
            if vcc[i][j] == 0:
                row, col = i, j
                break
    return row, col


#记录当前矩阵可移动的方向
def can_move(vcc):
    move = []
    (row, col) = get_index(vcc)
    #判断能移动的位置
    if row:
        move.append([-1, 0]) #如果0不在第一行，可以上移
    if row != 2:
        move.append([1, 0]) #下移
    if col:
        move.append([0, -1]) #左移
    if col != 2:
        move.append([0, 1]) #右移
    #返回列表
    return move

#移动函数，返回移动后的列表
def move(vcc, ls):
    (row, col) = get_index(vcc)
    #移动
    vcc[row][col], vcc[row+ls[0]][col+ls[1]] = vcc[row+ls[0]][col+ls[1]], vcc[row][col]
    return vcc

#根据移动后的列表，找出并返回与目标矩阵差别最小的矩阵
def min_vcc(vcc_ls, ls):
    a = ls.index(min(ls))
    return vcc_ls[a]


#运行函数
def main():
    open_list = []
    closed_list = []
    print("请输入初始状态矩阵")
    init_vcc = get_state()
    print("请输入目标状态矩阵")
    goal_vcc = get_state()
    #open表保存矩阵和代价值
    open_list.append([init_vcc, diff(init_vcc, goal_vcc)])
    while open_list:
        node = open_list[0]  #初始化选一个节点
        for i in open_list:
            #如果该节点的代价值小，选择
            if i[1] < node[1]:
                node = i

        #从open表里移除该节点
        open_list.remove(node)

        closed_list.append(node[0])
        ls = can_move(node[0])
        for ls1 in ls:
            #扩展open表
            temp_vcc = copy.deepcopy(node[0])
            open_list.append([move(temp_vcc, ls1), diff(temp_vcc, goal_vcc)])

        if closed_list[-1] == goal_vcc:
            #找到目标节点，结束循环
            break
    for i in range(len(closed_list)):
        print(f"第{i+1}步\n{closed_list[i]}")



if __name__ == "__main__":
    main()

4、运行结果