| Апр, 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],Опт_путь).Но очищенные и не очищенные дороги выделить не получается, подскажите пожалуйста как это сделать. |
