Алгоритм поиска пути (поезд с развязками) - PullRequest
Новая
       40

Алгоритм поиска пути (поезд с развязками)

0 голосов
/ 15 ноября 2018

Так что это мой упрощенный код на python, я пытаюсь использовать рекурсию, чтобы найти, на какие станции должен идти пользователь, если он хочет перейти от станции 1 к станции 12 (в качестве примера), но я не могу понять этоВ общем, пожалуйста, помогите мне, ребята, я застрял с этим так долго, большое спасибо! 

x = ["station1","station2","station3","station4"]
y = ["station5","station6","station7","station8"]
z = ["station9", "station10"]
e = ["station11", "station12"]
array = x, y, z, e
interchange = [ ["station4", "station5"] , ["station8", "station9"], ["station10, station[11] ]
cur = "station1"
des = "station12"

Так что коды ниже - это алгоритм, который я пытаюсь найти, но это не такработает на всех. 

def find(cur, des):
    check = 0
    for each in array:
        if cur in each and des in each:
            check = 1
            ind = each.index(cur)
            ind2 = each.index(des)
            for i in range(ind, ind2+1):
                print("-->", end = " ")
                print(each[i], end = " ")
            print("\n")
    for each in array:
        if cur in each and check == 0:
            for station in interchange:
                if station in each and cur != station:
                    ind = each.index(cur)
                    ind2 = each.index(station)
                    for i in range(ind, ind2+1):
                        print("-->", end = " ")
                        print(each[i], end = " ")
                    print("\n")
                    find(station, des)

Вот результат, который я пытаюсь получить: станция1 -> станция2 -> станция3 -> станция4 -> станция5 -> станция6 -> станция7--> Station8 -> Station9 -> Station10 -> Station11 -> Station12

РЕДАКТИРОВАТЬ: Ответ Canh : 

def find(cur, des):
    check = 0
    for each in array:
        if cur in each and des in each:
            check = 1
            ind = each.index(cur)
            ind2 = each.index(des)
            for i in range(ind, ind2+1):
                print("-->", end = " ")
                print(each[i], end = " ")
            print("\n")
    for each in array:
        if cur in each and check == 0:
            for station1, station2 in interchange:
                if station1 in each and cur != station1:
                    ind = each.index(cur)
                    ind2 = each.index(station1)
                    for i in range(ind, ind2+1):
                        print("-->", end = " ")
                        print(each[i], end = " ")
                    find(station2, des)

Извините, но у меня все еще есть другой вопрос, как мне нужно изменить код, чтобы он нашел ВСЕ возможные маршруты (примечание: поезд может идти вперед и назад), если условие: 

x = ["station1","station2","station3","station4"]
y = ["station8","station7","station6","station5"]
z = ["station9", "station10"]
e = ["station11", "station12"]

interchange = [ ["station1", "station9"], ["station5", "station4"] , ["station9", "station8"], ["station10", "station11" ],  ["station2", "station9" ] ]

cur = "station12"
des = "station1"

Некоторые из примеров маршрутов должны быть:

станция12 -> станция11 -> станция10 -> станция9 -> станция1

staнация12 -> станция11 -> станция10 -> станция9 -> станция2 -> станция1 -> станция1

станция12 -> станция11 -> станция10 -> станция8 -> станция7 -> станция6 -> Station5 -> Station4 -> Station3 -> Station2 -> Station1

, и если курс и де поменяются местами: 

cur = "station1"
des = "station12"

, то возможные маршруты будут противоположныпредыдущего.

1 Ответ

0 голосов
/ 15 ноября 2018

Ваша переменная interchange является списком списка. В операторе for station in interchange, station является списком, поэтому условие station in each никогда не будет истинным.

Я думаю, что так должно быть 

for station1, station2 in interchange:
    if station1 in each and cur != station1:
        ind = each.index(cur)
        ind2 = each.index(station1)
        for i in range(ind, ind2+1):
            print("-->", end = " ")
            print(each[i], end = " ")
        print("\n")
        find(station2, des)
...