[Закрыть]
 
popoff.donetsk.ua
Ничего нет внутри у того человека, который вечно все выставляет наружу. /Оноре де Бальзак/
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Форум - Функциональное и логическое программирование - выбор оптимального движения с проездом заданных отрезков

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

форумы popoff.donetsk.ua
Страницы: [1]
<< Новый  |  Старый >>  |  Ответ не возможен

Внимание! Этот топик устарел. Пожалуйста, создайте новый топик, чтобы задать интересующий Вас вопрос.

Автор Сообщение
koly4ii
Николай
Апр, 2010
Сообщений: 1
koly4ii url://forum.message:3050
выбор оптимального движения с проездом заданных отрезков

Здравствуйте!
Помогите пожалуйста с задачкой : дан граф, ребра представляют собой дороги, дорога это участок от перекрестка до перекрестка.
Необходимо составить схему движения снегоочистительной машины, с учётом заданных дорог.
Причём путь должен быть кратчайшим.

Главная задача в этой проге - это обозначение очищенности или просто проезда этой дороги в холостую, т.е. если на входе база (она же точка начала движения и конца) a, а заданный отрезок для очистки eh, то на выходе что-то типа :
совок поднят а ->b -> e совок опущен -> h совок поднят -> q -> i -> a.

Как-то так, оформление не так важно, важна суть маркировки очищенных дорог и не очищенных.

Я пока составил программу, которая проходит по заданным отрезкам оптимальным путём, но с главной задачей я пока что справиться не могу =(
Вот программа, которую я уже написал :

domains
список=symbol*
predicates
nondeterm принадлежит(symbol,symbol,список)
nondeterm карта(список)            
nondeterm путь(symbol,symbol,integer,список,список)
nondeterm смежные(symbol,symbol,список)
nondeterm путь1(symbol,список,список,integer,integer,список)
nondeterm содержит(список,список)
nondeterm опт_путь(symbol,symbol,integer,список,список)
nondeterm путь_короче(symbol,symbol,integer,список)
nondeterm удалить(список,symbol,symbol,список)

clauses
карта([a,b,a,g,b,c,c,i,c,h,c,e,e,f,f,d,d,i,i,h,i,g]).

принадлежит(Нач_пункт,Конеч_пункт,[Нач_пункт,Конеч_пункт|_]).
принадлежит(Нач_пункт,Конеч_пункт,[_,_|Хвост]):-
    принадлежит(Нач_пункт,Конеч_пункт,Хвост).

смежные(Нач_пункт,Конеч_пункт,Карта):-
        принадлежит(Нач_пункт,Конеч_пункт,Карта);
        принадлежит(Конеч_пункт,Нач_пункт,Карта).

путь1(Нач_пункт,[Нач_пункт|Путь],_,Кол_дорог,Кол_дорог,Путь).
путь1(Нач_пункт,[Пром_пункт|Путь1],Карта,Кол_дорог_,Кол_дорог,Путь):-
        смежные(Пром_пункт1,Пром_пункт,Карта),
    not(смежные(Пром_пункт1,Пром_пункт,Путь1)),
        Кол_дорог1=Кол_дорог_+1,
        путь1(Нач_пункт,[Пром_пункт1,Пром_пункт1,Пром_пункт|Путь1],Карта,Кол_дорог1,Кол_дорог,Путь).
                              
путь(Нач_пункт,Конеч_пункт,Кол_дорог,Список,Путь):-
        карта(Карта),
        путь1(Нач_пункт,[Конеч_пункт],Карта,0,Кол_дорог,Путь),
        содержит(Путь,Список).

содержит(Путь,[A,B|Список]):- принадлежит(A,B,Путь), !, содержит(Путь,Список).
содержит(_,[]).

опт_путь(Нач_пункт,Конеч_пункт,Кол_дорог,Список,Опт_путь):-
       Нач_пункт<>Конеч_пункт,
        путь(Нач_пункт,Конеч_пункт,Кол_дорог,Список,Опт_путь),
        not(путь_короче(Нач_пункт,Конеч_пункт,Кол_дорог,Список)).
          
опт_путь(Нач_пункт,Нач_пункт,Кол_дорог,Список,[Нач_пункт,След_пункт|Путь]):-
        карта(Карта),
        смежные(Нач_пункт,След_пункт,Карта),
       удалить(Список,Нач_пункт,След_пункт,Список1),
        путь(След_пункт,Нач_пункт,Кол_дорог1,Список1,Путь),
        not(путь_короче(След_пункт,Нач_пункт,Кол_дорог1,Список1)),
        Кол_дорог=Кол_дорог1+1.
                                
путь_короче(Нач_пункт,Конеч_пункт,Кол_дорог,Список):-        
        путь(Нач_пункт,Конеч_пункт,Кол_дорог1,Список,_),
        Кол_дорог>Кол_дорог1.

удалить([A,B|Список],A,B,Список):- !.
удалить([X,Y|Список],A,B,[X,Y|Список1]):- удалить(Список,A,B,Список1).
удалить([],_,_,[]).
goal
опт_путь(a,a,Кол_дорог,[c,h,i,d],Опт_путь).


Но очищенные и не очищенные дороги выделить не получается, подскажите пожалуйста как это сделать.

Внимание! Этот топик устарел. Пожалуйста, создайте новый топик, чтобы задать интересующий Вас вопрос.

Страницы: [1]
<< Новый  |  Старый >>  |  Ответ не возможен
Вход
Поиск[?]:
Гинеколог, стоматолог, психотерапевт в Донецке