Крыса с рандомизированным путем и двумерным массивом - PullRequest
Новая
       42

Крыса с рандомизированным путем и двумерным массивом

1 голос
/ 27 сентября 2019

Проблема похожа на проблему крысиного лабиринта.Я дал 2-й массив MxN.каждая ячейка массива либо 1, либо 0, где 1 означает блокировку.Я дал 2 балла (начальная точка и конечная точка).Я должен идти от начального индекса до конечного индекса.Но подвох 1) Путь должен быть случайным.2) Должен быть какой-то параметр, который позволит мне решить, насколько случайным он может быть.(то есть, насколько безумно он должен блуждать, прежде чем добраться до места назначения.) 3) Путь не должен пересекаться сам собой (как в игре со змеями).

Этот алгоритм необходим для создания популяции (случайным образом), которая будет использоваться в качестве входных данных.для генетической модели для дальнейшей оптимизации.На данный момент я использовал BFS и создал одно решение.Но проблема в том, что я не могу создать никакой случайный путь с этим (который я буду позже использовать в качестве совокупности) + я не могу формализовать представление о том, насколько случайным он должен быть.

Это мой кодэто дает только минимальный путь, используя bfs 

def isSafe(x,y,length):
if ((x<length) and (x>-1) and (y<length) and (y>-1)):
    return True;
return False;
def path(room,x1,y1,x2,y2,distance):
roomSize=len(room);
if ((x1==x2) and (y1==y2)):
    room[x1][y1]=distance+1
    return
queue=[[x1,y1]]
room[x1][y1]=0
start=0
end=0
while start<=end:
    x,y=queue[start]
    start+=1
    distance=room[x][y]
    for i in [-1,1]:
        if isSafe(x+i,y,roomSize):
            if room[x+i][y]=="O":
                queue.append([x+i,y])
                room[x+i][y]=distance+1
                end+=1;
    for i in [-1,1]:
        if isSafe(x,y+i,roomSize):
            if room[x][y+i]=="O":
                queue.append([x,y+i])
                room[x][y+i]=distance+1
                end+=1;
def retrace(array,x1,y1,x2,y2):
roomSize=len(array)
if not (isSafe(x2,y2,roomSize)):
    print("Wrong Traversing Point");
if type(array[x2][y2])==str:
    print("##################No Pipe been installed due to path constrained################")
    return [];
distance=array[x2][y2];
path=[[x2,y2]]
x=0
while not (array[x2][y2]==0):
    if ((isSafe(x2+1,y2,roomSize)) and type(array[x2+1][y2])==int and array[x2+1][y2]==array[x2][y2]-1):
        x2+=1;
        path.append([x2,y2]);
    elif ((isSafe(x2-1,y2,roomSize)) and type(array[x2-1][y2])==int and array[x2-1][y2]==array[x2][y2]-1):
        x2-=1;
        path.append([x2,y2])
    elif ((isSafe(x2,y2+1,roomSize)) and type(array[x2][y2+1])==int and array[x2][y2+1]==array[x2][y2]-1):
        y2+=1;
        path.append([x2,y2]);
    elif ((isSafe(x2,y2-1,roomSize)) and type(array[x2][y2-1])==int and array[x2][y2-1]==array[x2][y2]-1):
        y2-=1;
        path.append([x2,y2]);
return path;
...