Как реализовать генетический алгоритм на сетке, чтобы найти оптимальный путь ⇐ Python

[Anonymous]

Я готовлю алгоритмы оптимального поиска пути на местности с препятствиями. До сих пор я реализовал алгоритмы Дейсктры и A*. Теперь мне нужно реализовать генетический алгоритм, и у меня возникла проблема.

Сначала я покажу вам, как выглядит мое представление карты. Существует 7 различных типов местности (0 – начало, 7 – конец, 1–4 нормальных, которые можно пройти, 5–6 – нельзя). Вот код для этого на Python (на мой взгляд, самая важная часть кода для понимания проблемы — это соседи функций):

Код: Выделить всё

class Graph():
def __init__(self, x=10, y=10):
self.width = x
self.height = y
self.board = ((1, 1, 1, 5, 1, 1, 1, 1, 1, 7),
(1, 1, 1, 5, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 5, 1, 5, 1, 1, 1, 1),
(0, 1, 1, 1, 1, 5, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 5, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1))
self.time = {0: None,
1: 1,
2: 4,
3: 7,
4: 4,
7: 1}
def cost(self, id):
(x, y)= id
return self.time.get(self.board[y][x])

def canPass(self, id):
(x, y) = id
return self.board[y][x] != 5 and self.board[y][x] != 6 and self.board[y][x] != 0

def inBounds(self, id):
(x, y) = id
return 0