1

Необходимо было написать программу, выполняющую алгоритм А*, вот ее код:

import heapq
import sys


class Graph:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.walls = []

    def in_bounds(self, id):
        (x, y) = id
        return 0 <= x < self.width and 0 <= y < self.height

    def passable(self, id):
        return id not in self.walls

    def neighbors(self, id):
        (x, y) = id
        results = [(x + 1, y), (x, y - 1), (x - 1, y), (x, y + 1)]
        results = filter(self.in_bounds, results)
        results = filter(self.passable, results)
        return results


class GraphWithWeights(Graph):
    def __init__(self, width, height):
        super().__init__(width, height)
        self.weights = {}

    def cost(self, to_node):
        return self.weights.get(to_node)


class PriorityQueue:
    def __init__(self):
        self.elements = []

    def empty(self):
        return len(self.elements) == 0

    def put(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def get(self):
        return heapq.heappop(self.elements)[1]


def heuristic(a, b):
    (x1, y1) = a
    (x2, y2) = b
    return abs(x1 - x2) + abs(y1 - y2)


def a_star_search(graph, start, goal):
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while not frontier.empty():
        current = frontier.get()

        if current >= goal:
            break

        for next in graph.neighbors(current):

            new_cost = cost_so_far[current] + GraphWithWeights.cost(next)  # current
            if (next not in cost_so_far) or (new_cost < cost_so_far[next]):
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(goal, next)
                frontier.put(next, priority)
                came_from[next] = current

    return cost_so_far


def main():
    ctrl_num = 0
    while ctrl_num == 0:
        try:
            width = int(input('введите ширину графа (ось х) '))
        except ValueError:
            print('ошибка: введите натуральное целое число')
            continue
        if width > 0:
            break
        else:
            print('ошибка: число должно быть натуральным')
            continue
    while ctrl_num == 0:
        try:
            height = int(input('введите высоту графа (ось у) '))
        except ValueError:
            print('ошибка: введите натуральное целое число')
            continue
        if height > 0:
            break
        else:
            print('ошибка: число должно быть натуральным')
            continue

    weights = {}
    while ctrl_num == 0:
        try:
            check = int(input(f'по умолчанию стоимость всех путей графа = 1\n'
                              'введите 1, если хотите задать стоимость графа, \n'
                              'введите 0, если хотите оставить стоимость по умолчанию '))
        except ValueError:
            print('ошибка: введите натуральное целое число')
            continue
        if (check == 0) or (check == 1):
            break
        else:
            print('ошибка: введеной команды не существует. Введите число 1 или 0')
            continue
    if check == 1:
        for i in range(height):
            for k in range(width):
                while ctrl_num == 0:
                    try:
                        weights[(i, k)] = int(input('введите стоимость пути в точку ({}, {}) '.format(i+1, k+1)))
                    except ValueError:
                        print('ошибка: вес может быть только целым натуральным числом')
                        continue
                    if weights[(i, k)] > 0:
                        break
                    else:
                        print('ошика: вес может быть только положительным числом')
                        continue
    else:
        for i in range(height):
            for k in range(width):
                weights[(i, k)] = 1

    graph = Graph(width, height)
    weights = GraphWithWeights(graph, height)

    while ctrl_num == 0:
        try:
            x_start = int(input('введите координату х точки старта '))
        except ValueError:
            print('ошибка: координата точки может быть только целым положительным числом')
            continue
        if x_start <= width:
            break
        else:
            print('ошибка: данной координаты не существует')
            continue
    while ctrl_num == 0:
        try:
            y_start = int(input('введите координату у точки старта '))
        except ValueError:
            print('ошибка: координата точки может быть только целым положительным числом')
            continue
        if y_start <= height:
            break
        else:
            print('ошибка: данной координаты не существует')
            continue
    while ctrl_num == 0:
        try:
           x_end = int(input('введите координату х точки финиша '))
        except ValueError:
            print('ошибка: координата точки может быть только целым положительным числом')
            continue
        if x_end <= width:
            break
        else:
            print('ошибка: данной координаты не существует')
            continue
    while ctrl_num == 0:
        try:
            y_end = int(input('введите координату у точки финиша '))
        except ValueError:
            print('ошибка: координата точки может быть только целым положительным числом')
            continue
        if y_end <= height:
            break
        else:
            print('ошибка: данной координаты не существует')
            continue

    cost = a_star_search(graph, (x_start, y_start), (x_end, y_end))
    print('точка старта и стоимость оптимального пути равны: '.format(cost))


if __name__ == '__main__':
    sys.exit(main())

В какой-то момент все запускалось без ошибок, потом была добавлена проверка входных значений и теперь программа выполняется ровно до этого момента:

 for next in graph.neighbors(current):

        new_cost = cost_so_far[current] + GraphWithWeights.cost(next)

Дальше возникает ошибка

Traceback (most recent call last):
  File "C:\Users\Я\Desktop\study\labs_op\labs_op.py\venv\lab4_op_1.py", line 192, in <module>
    sys.exit(main())
  File "C:\Users\Я\Desktop\study\labs_op\labs_op.py\venv\lab4_op_1.py", line 187, in main
    cost = a_star_search(graph, (x_start, y_start), (x_end, y_end))
  File "C:\Users\Я\Desktop\study\labs_op\labs_op.py\venv\lab4_op_1.py", line 71, in a_star_search
    new_cost = cost_so_far[current] + GraphWithWeights.cost(next)  # current
TypeError: cost() missing 1 required positional argument: 'to_node'

Что именно требуется ввести я не понимаю, ведь следующая координата как раз задается в функции.

1
  • 1
    Вы вызываете GraphWithWeights.cost(next) в данном случае cost() как метод класса, коим он не является. Вам требуется сначала объявить экземляр класса GraphWithWeights, а потом уже вызвать метод экземпляра. Так как вы определили это экземпляр раньше, то просто требуется передать его в функцию.
    – asanisimov
    26 фев 2021 в 12:38

1 ответ 1

1

Думаю, вам нужно сделать такую замену:

def a_star_search(graph, weights, start, goal):
    ...
    new_cost = cost_so_far[current] + weights.cost(next)  # current

...

cost = a_star_search(graph, weights, (x_start, y_start), (x_end, y_end))

Смотрите, выражение GraphWithWeights.cost(next) это вызов метода класса, а не объекта, а у вас метод def cost(self, to_node): именно объекта, т.к. имеет обязательный параметр self.

А вот этот код вызывает метод cost у объекта weights и в этом случае в параметр self попадет ссылка на объект weights, а в параметр to_node ссылка на next:

weights = GraphWithWeights(graph, height)
...
weights.cost(next)

Поэтому, при выполнении GraphWithWeights.cost(next) в self попала ссылка на класс GraphWithWeights, а параметр next не был заполнен, поэтому именно такая ошибка: missing 1 required positional argument: 'to_node'

2
  • После замены появилась ошибка > File "C:\Users\Я\Desktop\study\labs_op\labs_op.py\venv\lab4_op_1.py", line 71, in a_star_search new_cost = cost_so_far[current] + weights.cost(next) # current TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' Если верить дебагу, то словарь с весами просто не заполнился. Можно ли это как-то решить?
    – newcomer
    9 дек 2019 в 12:23
  • @newcomer, ну да self.weights = {}, не заполнено. Вам нужно заполнить словарь весов, ваш же код :)
    – gil9red
    9 дек 2019 в 13:12

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.