Выбор алгоритма для поиска оптимального пути движения в метро

@garkeP91 · Регистрация: 24.10.2010

Студворк — интернет-сервис помощи студентам

Здравствуйте! У меня есть программа, которая ищет маршруты проезда в московском метро. Учитывается время перегонов, время пересадок, время ожидания. Программа работает дольше, чем хотелось бы. Используется предикат findall, затем пузырьковая сортировка и вывод списка станций, через которые необходимо проехать. Размерность задачи большая: порядка 180 станций. Полный перебор точно не оптимален.
Вопрос такой: какой алгоритм выбрать? И, если можно, опишите, как именно мне его использовать. К примеру, выбор направления движения от начального узла к конечному, формирование "коридора". Или каждой станции надо задавать координаты.. Еще мне сказали, нужно формировать путь от начального узла до конечного и, если найденный путь не оптимальнее найденного ранее, его отбрасывать. Но я не знаю, как это сделать, какие использовать предикаты.
Помогите с реализацией. Спасибо

@garkeP91 · 10.01.2011, 15:21 **[ТС]**

Сообщение от rrrFer

тогда мой вопрос выше снят, все понятно

. Но переменную Fin, походу, можно не использовать, на ее место везде напишите h сразу.

Да, с этим вроде понятно. Просто запись типа

Prolog
1
Fin=h

внутри предиката мне тоже не понравилась )) А что все-таки делать с way? Для чего он нужен?
Может быть, он определяет длину списка или еще что-то..

Добавлено через 3 часа 0 минут
Помогите, пожалуйста, определить предикат way.
Я написал

Prolog
1
2
way(0,[]).
way(Длина,[_|Хвост]):-way(Длина1,Хвост),Длина1 = Длина + 1.

А не работает.. Что он должен делать? Возникают ошибки, не совпадают типы

@Грымзик · 10.01.2011, 18:24

Fin=h это на самом деле Finish. Я на другом прологе делала, а потом просто все is на = поменяла

И раз у вас осталась ошибка с безымянной переменной, значит вы просто копировали участки кода из того, что я выложила? Зачем, могли бы полностью взять, тогда бы не было проблем с безымянными переменными и с группировкой предикатов. Кстати, это ошибка возникает когда между правилами одного предиката описываются еще и правила другого.
way - это не предикат, это структура для хранения информации.

Prolog
1
2
3
4
5
6
domains
slist=string*
w=way(integer,slist).
 
predicates
nondeterm prolong(w,w)

@garkeP91 · 10.01.2011, 18:52 **[ТС]**

Спасибо! Вроде стало понятнее )) Только сейчас у меня сообщает об ошибках что-то о неправильных типах аргументов. Посмотрите, наверное дело в первых двух разделах...
Ошибки указывает в коде в предикатах: принадлежит, время_пересадки, placeone, bst

Или напишите, как у вас. Вы, наверное, это писали. Но прислали только CLAUSES и GOAL

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
DOMAINS
 
список=symbol*
список_списков=список*
slist=string*
w=way(integer,slist)
 
PREDICATES
 
nondeterm время_пересадки(symbol,symbol,integer)
nondeterm время_пересадки_(symbol,symbol,integer)
nondeterm время_перегона(symbol,symbol,integer)
nondeterm время_перегона_(symbol,symbol,integer)
nondeterm prolong(w,w)
nondeterm place(список,список,список)
nondeterm placeone(symbol,список,список)
nondeterm bst(список,symbol,список)
nondeterm путь(symbol,symbol)
nondeterm обращ(список,список)
nondeterm обращ(список,список,список)
nondeterm принадлежит(symbol,список)
nondeterm станция(symbol,symbol)
nondeterm оптимальный_путь(symbol,symbol)
nondeterm вывод(список_списков,integer,integer,integer)
nondeterm go

@Грымзик · 10.01.2011, 19:24

Ну тут действительно с типами проблема, будьте внимательнее. Ведь в том же bst, не списки в качестве параметров, а структура w. Я не могу код кинуть, я потому на другом прологе и писала, что на визуале у меня русского нет.

@garkeP91 · 10.01.2011, 19:34 **[ТС]**

Жалко.. Я уже экспериментирую

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
nondeterm время_пересадки(symbol,symbol,integer)
nondeterm время_пересадки_(symbol,symbol,integer)
nondeterm время_перегона(symbol,symbol,integer)
nondeterm время_перегона_(symbol,symbol,integer)
nondeterm prolong(w,w)
nondeterm place(w,slist,w)
nondeterm placeone(w,slist,w)
nondeterm bst(w,symbol,w)
nondeterm путь(symbol,symbol)
nondeterm обращ(список,список)
nondeterm обращ(список,список,список)
nondeterm принадлежит(symbol,slist)
nondeterm станция(symbol,symbol)
nondeterm оптимальный_путь(symbol,symbol)
nondeterm вывод(список,integer,integer,integer)
nondeterm go

Выдает 4 ошибки Type error: The functor does not belong to the domain

Что я не так поменял?

@Грымзик · 10.01.2011, 20:14

Должны строки конкретные указываться с ошибками, а так я пока вижу только в placeone и bst надо не w, а wlist=w*

@garkeP91 · 10.01.2011, 20:29 **[ТС]**

wlist это получается список структур way?
Я сделал вот так:

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
DOMAINS
 
список=symbol*
список_списков=список*
slist=string*
w=way(integer,slist)
wlist=w*
 
PREDICATES
...
nondeterm prolong(w,w)
nondeterm place(wlist,wlist,wlist)
nondeterm placeone(w,wlist,wlist)
nondeterm bst(wlist,symbol,w)
nondeterm путь(symbol,symbol)
nondeterm обращ(список,список)
nondeterm обращ(список,список,список)
nondeterm принадлежит(symbol,slist)
nondeterm станция(symbol,symbol)
nondeterm оптимальный_путь(symbol,symbol)
nondeterm вывод(список,integer,integer,integer)
nondeterm go

Ошибка Type error: Illegal variable type for this position

Prolog
1
2
путь(Старт,Z):- bst([way(0,[Старт])],Z,way(Время_пути,Решение)),
        обращ(Решение,Еинешер),write("Путь:\n"),вывод(Еинешер,Время_пути,0,0).

курсор показывает на вторую строку, после "обращ("

@Грымзик · 10.01.2011, 20:47

Может потому что в обращ в качестве типа symbol*, а на вход подается string*

@garkeP91 · 10.01.2011, 20:53 **[ТС]**

да, изменил:

Prolog
1
2
3
nondeterm обращ(slist,slist)
nondeterm обращ(slist,slist,slist)
nondeterm вывод(slist,integer,integer,integer)

все классно работает! только почему-то иногда после ввода станций и нажатия на Enter выдает ошибку. Наверное, что-то в фактах с узлами напутал. Хотя раньше работало, я посмотрю.
Кстати а что делает предикат bst(wlist,symbol,w) и что есть его параметры? особенно 1 и 3. это списки чего?

@Грымзик · 10.01.2011, 20:56

Приведите пример запроса с ошибкой.
bst(wlist,symbol,w) - главный предикат поиска. Первый параметр - текущий список рассмотренных путей, второй -конечный пункт, третий - ответ, т.е самый короткий путь от до конечного пункта.

@garkeP91 · 10.01.2011, 21:01 **[ТС]**

Программа определения оптимального маршрута движения в метро
Для выхода нажмите Esc
Начальная станция: пролетарская
Конечная станция: университет
----------------------------------------------------------------------
Идет поиск оптимального маршрута движения...

PROGRAM ERROR. 7087
Press any key ...

@Грымзик · 10.01.2011, 21:24

У меня работает

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Путь:
пролетарская   переезд -->   таганская_таганско_краснопресненской_линии
таганская_таганско_краснопресненской_линии   пересадка -->   таганская_кольцевой_линии
таганская_кольцевой_линии   переезд -->   павелецкая_кольцевой_линии
павелецкая_кольцевой_линии   переезд -->   добрынинская_кольцевой_линии
добрынинская_кольцевой_линии   переезд -->   октябрьская_кольцевой_линии
октябрьская_кольцевой_линии   переезд -->   парк_культуры_кольцевой_линии
парк_культуры_кольцевой_линии   пересадка -->   парк_культуры_сокольнической_линии
парк_культуры_сокольнической_линии   переезд -->   фрунзенская
фрунзенская   переезд -->   спортивная
спортивная   переезд -->   воробьевы_горы
воробьевы_горы   переезд -->   университет
Время пути: 39 минут,
Пересадок: 2
Перегонов: 9

Но достаточно долго, слишком много вариантов пересчитывать надо, наверно просто памяти не хватает. Не знаю можно ли ее в визуал прологе настраивать.

Добавлено через 1 минуту
И Вы точно все правильно с Fin=h изменили?

@garkeP91 · 10.01.2011, 21:33 **[ТС]**

Да, на Finish поменял правильно в 2 предложениях. В принципе все работает, спасибо большое!
а вы можете еще в крации объяснить, зачем нужны и какие имеют параметры предикаты:
nondeterm prolong(w,w)
nondeterm place(wlist,wlist,wlist)
nondeterm placeone(w,wlist,wlist)
nondeterm обращ(slist,slist)
nondeterm обращ(slist,slist,slist)
?

СПАСИБО!!!! )

@Грымзик · 10.01.2011, 21:41

prolong(w,w) для текущего состояния (т.е списка пройденных станций и общего времени, затраченного на путь) возвращает новое, в котором мы проехали еще одну станцию. Если мы текущий путь продлили всеми возможными способами, то их надо так распихать по списку всех рассматриваемых нами путей, чтобы сохранилась отсортированность по времени. Для этого создан предикат place(wlist,wlist,wlist). Он ставит на нужное место голову списка (используя тот самый placeone(w,wlist,wlist)), а потом рекурсивно распихивает хвост. Предикат обращ просто для перестановки списка в обратном порядке.

@garkeP91 · 11.01.2011, 15:40 **[ТС]**

Спс большое!!! Что бы я без вас делал!! Теперь буду ПЗ писать, если что, буду еще спрашивать

Добавлено через 17 часов 19 минут
Помогите, пожалуйста, с блок-схемой программы.. Или не блок-схему уж, а как-нибудь "на пальцах" объяснить как работает)) а то я уже вошел в рекурсию: чтобы составить блок-схему, надо понять программу; чтобы понять программу, надо смотреть блок-схему; чтобы смотреть блок-схему, надо составить блок-схему. Мда..

Можно вот с путь(X,Y) далее -> bst -> prolong -> findall -> place -> placeone. Остальное вроде бы составил, проблем не возникло.

@Грымзик · 11.01.2011, 18:59

Ну, честно говоря, этим мне заниматься совсем не хочется. Если Вы меня просите, значит Вы не поняли алгоритм и что каждый предикат делает. Может Вы лучше спросите, что Вам не понятно, а я объясню.

@garkeP91 · 11.01.2011, 20:45 **[ТС]**

Хорошо, так даже лучше. Я процитирую части кода, в которых у меня есть вопросы, напишу, как я думаю; если не правильно, поправьте.

Prolog
1
2
placeone(way(C,P),[way(C1,P1)|R],[way(C,P),way(C1,P1)|R]):-
                C<C1,!.

R - это список еще не отсортированных путей, каждый путь содержит полное время пути и список станций.
C1, C2 - Время путей, по которым они сортируются по возрастанию.
В конце зеленое отсечение, чтобы, если цель в правиле выполняется, не переходить к рассмотрению следующих предложений с этим же предикатом.

Prolog
1
2
placeone(way(C,P),[X|T],[X|R]):-
                placeone(way(C,P),T,R).

Здесь, как я понял, аналогично правилу выше, Х в головах двух списков путей означает, что первые пути в них совпадают (совпадает и время, и сам путь чтоли?

), рекурсивно вызываем это же правило, отбросив головы этих списков для сортировки следующих путей.

Prolog
1
placeone(way(C,P),[],[way(C,P)]).

Здесь вроде, если список путей состоит из одного пути (2й список пустой), просто записываем этот путь в первый аргумент.. Не совсем понятно здесь. Что есть первый аргумент и что возвращает предикат placeone? Список путей, в котором переставили только один путь?

Prolog
1
bst([way(C,[Finish|T])|_],Finish,way(C,[Finish|T])):-!.

Finish - конечная станция, T - пройденный путь (список станций), при первом вызове пустой.
Отсечение здесь зеленое, нужно, чтобы не искать путь, т.к. начальная и конечная станции совпадают.

Prolog
1
2
3
4
bst([Path|Rest],Finish,R):-
                findall(Z,prolong(Path,Z),NewPathes),
                place(NewPathes,Rest,NewQueue),!,
                bst(NewQueue,Finish,R).

как здесь работает findall? prolong продлевает путь, возвращает новый путь Z. По этому пути findall "строит" NewPathes. NewPathes - это структура way(integer,slist).
Так.. А дальше place сортирует очередь из структур, формирует путь NewQueue. (или это какая-то очередь путей?)
Какое здесь отсечение? Для чего? И когда оно выполняется, когда нет и к чему это приводит?
bst ищет оптимальный путь среди списка этих путей, результат - это 3й аргумент R.

@Грымзик · 11.01.2011, 21:16

Предикат placeone абсолютно не правильно понимаете. placeone(A,B,C) имеет смысл, что у нас есть новый найденный путь A, список найденных до этого путей B, который еще при этом и отсортирован по возрастанию времени пути, и надо получить новый список путей C, добавив на положенное место этот новый путь А.

Prolog
1
placeone(way(C,P),[way(C1,P1)|R],[way(C,P),way(C1,P1)|R]):- C<C1,!.

Если длина нашего нового пути короче, чем длина первого в списке пути (т.е значит и короче всех остальных), то ставим новый путь на первое место.

Prolog
1
placeone(way(C,P),[X|T],[X|R]):- placeone(way(C,P),T,R).

Если длина не короче (а из-за отсечения сюда попадаем только в этом случае), то первый путь в списке остается на своем месте и мы уже смотрим куда бы в хвост впихнуть этот наш новый путь.

Prolog
1
placeone(way(C,P),[],[way(C,P)]).

Если список путей пуст, то наш новый путь просто занимает свое место.

Prolog
1
bst([way(C,[Finish|T])|_],Finish,way(C,[Finish|T])):-!.

Это правило выполняется, когда мы уже достигли нашей конечной станции, и ставим отсечение, чтобы поиск дальше не продолжался, т.к если и найдется другой путь между станциями, то он точно будет не короче, бессмысленно искать дальше.

Prolog
1
2
3
4
bst([Path|Rest],Finish,R):-
                findall(Z,prolong(Path,Z),NewPathes),
                place(NewPathes,Rest,NewQueue),!,
                bst(NewQueue,Finish,R).

Что такое findall следовало бы самому почитать. Этот предикат ищет все Z, удовлетворяющие условию prolong(Path,Z), и помещает их в список NewPathes. Т.е мы смотрим текущий путь, находим все способы его продолжения, т.е генерим некоторые новые пути, с помощью place помещаем их на нужные места в списке до этого найденных путей, и продолжаем поиск уже с новым списком путей.

@garkeP91 · 12.01.2011, 14:58 **[ТС]**

Спасибо! А зачем кстати в конце кода правило:

Prolog
1
2
bst([_|T],F,R):-
                bst(T,F,R).

Без него все также работает.. вроде

@Грымзик · 12.01.2011, 16:08

В gnu прологе, на котором программы в книге и написаны, если в findall не найдено ни одного решения, то не пустой список возвращается, а просто завершается неудачей. Я это не утверждаю, как-то сомнительно мне, просто автор сам на это внимание на 162 стр. обращает. И тогда без этого правила действительно не обойтись.

Новые блоги и статьи Все статьи Все блоги /
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	День 5 из 28: Codex подсказывает следующий запрос and_y87 12.10.2026 9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .	Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@garkeP91 50 / 50 / 20 Регистрация: 24.10.2010 Сообщений: 131

	Выбор алгоритма для поиска оптимального пути движения в метро 08.01.2011, 13:08. Показов 8389. Ответов 43 Метки нет (Все метки) Здравствуйте! У меня есть программа, которая ищет маршруты проезда в московском метро. Учитывается время перегонов, время пересадок, время ожидания. Программа работает дольше, чем хотелось бы. Используется предикат findall, затем пузырьковая сортировка и вывод списка станций, через которые необходимо проехать. Размерность задачи большая: порядка 180 станций. Полный перебор точно не оптимален. Вопрос такой: какой алгоритм выбрать? И, если можно, опишите, как именно мне его использовать. К примеру, выбор направления движения от начального узла к конечному, формирование "коридора". Или каждой станции надо задавать координаты.. Еще мне сказали, нужно формировать путь от начального узла до конечного и, если найденный путь не оптимальнее найденного ранее, его отбрасывать. Но я не знаю, как это сделать, какие использовать предикаты. Помогите с реализацией. Спасибо 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	10.01.2011, 19:24
	Ну тут действительно с типами проблема, будьте внимательнее. Ведь в том же bst, не списки в качестве параметров, а структура w. Я не могу код кинуть, я потому на другом прологе и писала, что на визуале у меня русского нет. 1

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	10.01.2011, 20:14
	Должны строки конкретные указываться с ошибками, а так я пока вижу только в placeone и bst надо не w, а wlist=w* 1

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	10.01.2011, 20:47
	Может потому что в обращ в качестве типа symbol, а на вход подается string 1

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	10.01.2011, 20:56
	Приведите пример запроса с ошибкой. bst(wlist,symbol,w) - главный предикат поиска. Первый параметр - текущий список рассмотренных путей, второй -конечный пункт, третий - ответ, т.е самый короткий путь от до конечного пункта. 1

@garkeP91 50 / 50 / 20 Регистрация: 24.10.2010 Сообщений: 131
	10.01.2011, 21:01 [ТС]
	Программа определения оптимального маршрута движения в метро Для выхода нажмите Esc Начальная станция: пролетарская Конечная станция: университет ---------------------------------------------------------------------- Идет поиск оптимального маршрута движения... PROGRAM ERROR. 7087 Press any key ... 0

@garkeP91 50 / 50 / 20 Регистрация: 24.10.2010 Сообщений: 131
	10.01.2011, 21:33 [ТС]
	Да, на Finish поменял правильно в 2 предложениях. В принципе все работает, спасибо большое! а вы можете еще в крации объяснить, зачем нужны и какие имеют параметры предикаты: nondeterm prolong(w,w) nondeterm place(wlist,wlist,wlist) nondeterm placeone(w,wlist,wlist) nondeterm обращ(slist,slist) nondeterm обращ(slist,slist,slist) ? СПАСИБО!!!! ) 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	10.01.2011, 21:41
	prolong(w,w) для текущего состояния (т.е списка пройденных станций и общего времени, затраченного на путь) возвращает новое, в котором мы проехали еще одну станцию. Если мы текущий путь продлили всеми возможными способами, то их надо так распихать по списку всех рассматриваемых нами путей, чтобы сохранилась отсортированность по времени. Для этого создан предикат place(wlist,wlist,wlist). Он ставит на нужное место голову списка (используя тот самый placeone(w,wlist,wlist)), а потом рекурсивно распихивает хвост. Предикат обращ просто для перестановки списка в обратном порядке. 1

@garkeP91 50 / 50 / 20 Регистрация: 24.10.2010 Сообщений: 131
	11.01.2011, 15:40 [ТС]
	Спс большое!!! Что бы я без вас делал!! Теперь буду ПЗ писать, если что, буду еще спрашивать Добавлено через 17 часов 19 минут Помогите, пожалуйста, с блок-схемой программы.. Или не блок-схему уж, а как-нибудь "на пальцах" объяснить как работает)) а то я уже вошел в рекурсию: чтобы составить блок-схему, надо понять программу; чтобы понять программу, надо смотреть блок-схему; чтобы смотреть блок-схему, надо составить блок-схему. Мда.. Можно вот с путь(X,Y) далее -> bst -> prolong -> findall -> place -> placeone. Остальное вроде бы составил, проблем не возникло. 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	11.01.2011, 18:59
	Ну, честно говоря, этим мне заниматься совсем не хочется. Если Вы меня просите, значит Вы не поняли алгоритм и что каждый предикат делает. Может Вы лучше спросите, что Вам не понятно, а я объясню. 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	12.01.2011, 16:08
	В gnu прологе, на котором программы в книге и написаны, если в findall не найдено ни одного решения, то не пустой список возвращается, а просто завершается неудачей. Я это не утверждаю, как-то сомнительно мне, просто автор сам на это внимание на 162 стр. обращает. И тогда без этого правила действительно не обойтись. 0