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

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

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

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

@garkeP91 · 19.01.2011, 23:39 **[ТС]**

Спасибо за помощь! Я сдал курсовик на днях, правда на 4. А 4, потому что преподаватель сказал, что он думал, я сделал реальный поиск на основе весовой функции, а у меня используется встроенный предикат findall. Т.е. перебор всего. Не знаю что он хотел увидеть, но findall, по его мнению, видимо, это зацикленность программы, долгая работа и т.д. Я сказал, что так было в умной книге; он сказал, надо было самомому придумать алгоритм, а не из книг брать. Вообще он странный.. )) В общем, спасибо Вам большое! Тема закрыта.

@DebbieHarry · 26.12.2012, 14:04

Сообщение от Грымзик

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

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

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

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

извините,а как будет выглядеть запрос?

@garkeP91 · 26.12.2012, 14:22 **[ТС]**

DebbieHarry, Какой запрос? Ввод входных данных в сообщении #31

@DebbieHarry · 26.12.2012, 18:28

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

DebbieHarry, Какой запрос? Ввод входных данных в сообщении #31

я имею в виду какой запрос должен быть,чтобы программа заработала
через предикат "путь" или "оптимальный_путь"?
в GNU Prolog недостаточно ввести просто ?-go

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .

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

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

@garkeP91 50 / 50 / 20 Регистрация: 24.10.2010 Сообщений: 131
	19.01.2011, 23:39 [ТС]
	Спасибо за помощь! Я сдал курсовик на днях, правда на 4. А 4, потому что преподаватель сказал, что он думал, я сделал реальный поиск на основе весовой функции, а у меня используется встроенный предикат findall. Т.е. перебор всего. Не знаю что он хотел увидеть, но findall, по его мнению, видимо, это зацикленность программы, долгая работа и т.д. Я сказал, что так было в умной книге; он сказал, надо было самомому придумать алгоритм, а не из книг брать. Вообще он странный.. )) В общем, спасибо Вам большое! Тема закрыта. 0

@garkeP91 50 / 50 / 20 Регистрация: 24.10.2010 Сообщений: 131
	26.12.2012, 14:22 [ТС]
	DebbieHarry, Какой запрос? Ввод входных данных в сообщении #31 0