曼哈顿和Misplaced启发式[关闭]

Question

我的道歉，我是python的新手。有点我设法工作我的算法但是 凭借我对Python的了解，我无法做一些事情。这就是我在这里的原因 我需要用我的算法做三件事 1-需要添加Misplaced Tile启发式功能 2 - 需要添加曼哈顿距离启发式功能 3 - 我需要处理val = [0,3,2,5,8,7,1,6,4]而不是start1 =“012634785”字符串。我怎样才能做到这一点？将字符串转换为队列。

最后，我试着用A *搜索来编写8个拼图 初始状态= [0,3,2,5,8,7,1,6,4]这样的事情。 最终状态= [0,1,2,3,4,5,6,7,8] 请帮我学习一下。 我知道要求很多，但我非常感谢你们。

from queue import PriorityQueue
class State(object):
    def __init__ (self, value, parent, start = 0, goal = 0):
        self.children = []
        self.parent = parent
        self.value = value
        self.dist = 0
        if parent:
            self.path = parent.path[:]
            self.path.append(value)
            self.start = parent.start
            self.goal = parent.goal
        else:
            self.path = [value]
            self.start = start
            self.goal = goal

    def GetDist(self):
        pass
    def CreateChildren(self):
        pass

class State_String(State):
    def __init__ (self, value, parent, start = 0, goal = 0):
        super(State_String, self).__init__(value, parent, start, goal)
        self.dist = self.GetDist()
    def GetDist(self):
        if self.value == self.goal:
            return 0
        dist = 0
        for i in range(len(self.goal)):
            letter = self.goal[i]
            dist += abs(i - self.value.index(letter))
        return dist
    def CreateChildren(self):
        if not self.children:
            for i in list(range(len(self.goal)- 1)):
                val = self.value
                val = val[:i] + val[i + 1] + val[i] + val[i + 2:]
                child = State_String(val, self)
                self.children.append(child)

class AStar_Solver:
    def __init__(self, start, goal):
        self.path = []
        self.visitedQueue = []
        self.priorityQueue = PriorityQueue()
        self.start = start
        self.goal = goal

    def Solve(self):
        startState = State_String(self.start, 0, self.start, self.goal)
        count = 0
        self.priorityQueue.put((0, count, startState))
        while (not self.path and self.priorityQueue.qsize()):
            closestChild = self.priorityQueue.get()[2]
            closestChild.CreateChildren()
            self.visitedQueue.append(closestChild.value)
            for child in closestChild.children:
                if child.value not in self.visitedQueue:
                    count += 1
                    if not child.dist:
                        self.path = child.path
                        break
                    self.priorityQueue.put((child.dist, count, child))
        if not self.path:
            print("Goal of ", self.goal, " is not possible")
        return self.path

if __name__ == "__main__":
    start1 = "012634785"
    goal1 = "012345678"
    a = AStar_Solver (start1, goal1)
    a.Solve()
    for i in list(range(len(a.path))):
        print(a.path[i])

Answer 1

如果我得到你所要求的，你需要取“013749520348”并将其变成一个整数列表。要做到这一点：

# initial value
string = "012634785"

# converted to integers
list_nums = [int(i) for i in string]

# sort list
list_nums.sort()

# returns
[0, 1, 2, 3, 4, 5, 6, 7, 8]

如果你想要关于其他内容的答案，比如启发式函数或你发布的任何代码，你需要写一个新的问题来解决你遇到的特定问题以及你想要实现的特定结果。