Форум программистов, компьютерный форум, киберфорум
Наши страницы
Prolog
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Алиша
0 / 0 / 0
Регистрация: 30.05.2011
Сообщений: 1
1

Составить маршрут, который бы проходил через все пункты

02.06.2011, 12:39. Просмотров 910. Ответов 3
Метки нет (Все метки)

Помогите, пожалуйста, решить задачу: Составить маршрут, который бы проходил через все пункты, некоторые из которых связаны напрямую и через каждый пункт проходил только один раз.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2011, 12:39
Ответы с готовыми решениями:

Найти дешевый замкнутый маршрут, проходящий через все населенные пункты
Помогите решить задачу, пожалуйста! Есть N населенных пунктов и известна...

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

Построить маршрут, проходящий точно 1 раз через все населенные пункты и возвращающийся в начальный
Прощу помочь сделать вот такую непростую задачку.... Заранее очень...

Цикл который проходил один раз и выходит
Здравствуйте! Есть такой код для записи в бд циклом foreach: foreach (Works...

Задан исходный маршрут, различные пункты посещения, информация о наличии связи между пунктами i и i+1.
Помогите с программным кодом на c++ Задан исходный маршрут, различные пункты...

3
emppu2007
90 / 90 / 6
Регистрация: 04.05.2011
Сообщений: 171
02.06.2011, 13:55 2
Похоже на задачу коммивояжера.
Это она?
0
Грымзик
2478 / 1454 / 35
Регистрация: 14.09.2009
Сообщений: 2,742
02.06.2011, 14:40 3
Цитата Сообщение от emppu2007 Посмотреть сообщение
Похоже на задачу коммивояжера.
Это она?
Насколько я помню, в задаче коммивояжера надо через все ребра пройти, а не через все вершины.
Алиша, загляните в эту тему Поиск в пространстве состояний (поиск по графам тоже сюда!) в первое сообщение. Надо исправить задачу, чтобы искался путь не между двумя заданными вершинами, а между какими-то двумя, но чтобы длина пути была равна количеству городов.
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
26
27
m(a,b).
m(b,c).
m(a,d).
m(b,d).
m(c,d).
m(c,e).
m(d,e).
 
move(A,B):-m(A,B);m(B,A). %поскольку граф неориентирован
 
point(A):-m(A,_);m(_,A).
 
search:-setof(Point,point(Point),Points),length(Points,N),
    move(Start,_),move(Finish,_),
    dpth([Start],Finish,Way),length(Way,N),
    show_answer(Way).
 
prolong([Temp|Tail],[New,Temp|Tail]):-
        move(Temp,New),not(member(New,[Temp|Tail])).
 
dpth([Finish|Tail],Finish,[Finish|Tail]).
dpth(TempWay,Finish,Way):-
        prolong(TempWay,NewWay),dpth(NewWay,Finish,Way).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
        show_answer([B|Tail]),nl,write(B),write(' -> '),write(A).
0
emppu2007
90 / 90 / 6
Регистрация: 04.05.2011
Сообщений: 171
02.06.2011, 14:44 4
Цитата Сообщение от Грымзик Посмотреть сообщение
Насколько я помню, в задаче коммивояжера надо через все ребра пройти, а не через все вершины.
Через все рёбра?
Эм... Зачем?
Там же, например, даётся список из нескольких городов, рёбра-пути с весами между ними и нужно обойти все города по кратчайшему, самому выгодному, пути.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.06.2011, 14:44

Найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города
Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся...

Вирус, который добавляет пункты меню в контакте
Здравствуйте. При загрузке из интернета поймали целую серию вирусов, которые...

Как добавить в контекстное меню пункт, который разбивается на пункты ?
Всем привет ! Сегодня решил узнать как менять "Контекстное Меню" Прогуглил ! ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru