Вершины графа, к которым существует путь заданной длины от выделенной вершины графа

14.11.2010, 14:49. **Показов** 3197. **Ответов** 4

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

Есть стандартная задача:
1. Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа

Решение к ней:

Prolog

domains 
i=integer 
s=char 
list=s* 
database 
arca(s,s,i) 
 
predicates 
path(s,s,i) 
path1(list,s,i)
member(s,list) 
 
clauses 
arca('a','b',1).arca('b','c',3).arca('c','d',1).arca('b','d',2).arca('a','d',1). 
 
member(X,[X|_]):-!. 
member(X,[_|Tail]):- member(X,Tail). 
 
path(V,MP,MC):-path1([V],MP,MC).
 
path1([X|_],X,0):-!.
path1([X|Path],MP,MC):-MC>0,arca(X,Y,CXY),not(member(Y,[X|Path])),
C=MC-CXY,path1([Y,X|Path],MP,C).
 
goal 
write("nВведите длину пути: "),readint(MC), 
write("nВведите вершину, от которой вести поиск: "),readchar(V), 
findall(MP,path(V,MP,MC), Answ),write(Answ).

Мне надо модифицыровать програму:
Найти все вершины графа, к которым существует путь больше заданной длины от выделенной вершины графа

Помогите пожалуйста, уже 2 дня сижу никак не могу сделать)

@freest · 14.11.2010, 14:51

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

Prolog

domains 
i=integer 
s=char 
list=s* 
database 
arca(s,s,i) 
 
predicates 
nondeterm path(s,s,i) 
nondeterm path1(list,s,i)
member(s,list) 
 
clauses 
arca('a','b',1).arca('b','c',3).arca('c','d',1).arca('b','d',2).arca('a','d',1). 
 
member(X,[X|_]):-!. 
member(X,[_|Tail]):- member(X,Tail). 
 
path(V,MP,MC):-path1([V],MP,MC).
 
path1([X|_],X,MC):-MC<=0,!.
path1([X|Path],MP,MC):-arca(X,Y,CXY),not(member(Y,[X|Path])),
C=MC-CXY,path1([Y,X|Path],MP,C).
 
goal 
write("Ââåäèòå äëèíó ïóòè: "),readint(MC), 
write("\nÂâåäèòå âåðøèíó, îò êîòîðîé âåñòè ïîèñê: "),readchar(V), 
findall(MP,path(V,MP,MC), Answ),write(Answ).

У вас все почти верно написано. Только чучуть запутались)

14.11.2010, 15:49

Ух спасибо! На самом деле не все так сложно)

@Грымзик · 14.11.2010, 18:02

freest, маленькое дополнение: это не поиск в ширину. Поиски в глубину и ширину возможны только для безвесовых графов, а тут вы просто находите findall-ом все подходящие пути, а про их порядок ничего не известно.

@freest · 14.11.2010, 18:16

Хммм...Не знал...спс)))
Я думал не важно есть вес или нету... Но если б здесь даже небыло веса, то это был бы поиск в глубину))Я просто не хотел заново писать)

Так вот, хитрый момент состоит в том, что практически везде алгоритм DFS приведён в общем виде, а на форумах его советуют в первую очередь использовать на невзвешенных графах. В связи с этим новичку легко запутаться. В то же время, алгоритм DFS замечательно реализуется и на взвешенных графах, позволяя найти как длину пути, так и восстановить сам путь.

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

Новые блоги и статьи
Как проводить научные вычисления на Python InfoMaster 15.01.2025 Python стал одним из наиболее востребованных языков программирования в области научных вычислений благодаря своей простоте, гибкости и обширной экосистеме специализированных библиотек. Научные. . .	Создание игры типа Minecraft на PyGame/Python: пошаговое руководство InfoMaster 15.01.2025 В данном руководстве мы рассмотрим процесс создания игры в стиле Minecraft с использованием библиотеки PyGame на языке программирования Python. Этот проект идеально подходит как для начинающих. . .	Как создать свою первую игру в стиле Doom на Unreal Engine InfoMaster 15.01.2025 Разработка шутера от первого лица в стиле классического Doom представляет собой увлекательное путешествие в мир игрового программирования, где сочетаются творческий подход и технические навыки. . . .	Параллельное программирование: основные технологии и принципы InfoMaster 15.01.2025 Введение в параллельное программирование Параллельное программирование представляет собой фундаментальный подход к разработке программного обеспечения, который позволяет одновременно выполнять. . .	Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD InfoMaster 15.01.2025 В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .	Что такое CQRS и как это реализовать на C# с MediatR InfoMaster 15.01.2025 Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .
Как настроить CI/CD с Azure DevOps InfoMaster 15.01.2025 CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .	Как настроить CI/CD с помощью Jenkins InfoMaster 15.01.2025 Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .	Как написать микросервис на Go/Golang с Kafka, REST и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS, Swagger и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .

Err0r
	14.11.2010, 15:49	3
	Ух спасибо! На самом деле не все так сложно)

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	14.11.2010, 18:02	4
	freest, маленькое дополнение: это не поиск в ширину. Поиски в глубину и ширину возможны только для безвесовых графов, а тут вы просто находите findall-ом все подходящие пути, а про их порядок ничего не известно. 1

@freest Українець 424 / 318 / 16 Регистрация: 26.09.2009 Сообщений: 844
	14.11.2010, 18:16	5
	Хммм...Не знал...спс))) Я думал не важно есть вес или нету... Но если б здесь даже небыло веса, то это был бы поиск в глубину))Я просто не хотел заново писать) Так вот, хитрый момент состоит в том, что практически везде алгоритм DFS приведён в общем виде, а на форумах его советуют в первую очередь использовать на невзвешенных графах. В связи с этим новичку легко запутаться. В то же время, алгоритм DFS замечательно реализуется и на взвешенных графах, позволяя найти как длину пути, так и восстановить сам путь. Нигде не вижу чтоб написано было, что только для невзвешеных( 0