/**************************************************************
Коммивояжёр. Поиск в глубину.
**************************************************************/
domains ss = string*
database - путь
путь(string,integer,string)
оценка(ss,integer)
predicates
оптим_маршрут(ss,integer)
nondeterm маршруты(string,integer,ss,integer)
nondeterm вариант(string,integer,string,ss,integer)
nondeterm участок(string,integer,string)
уник(ss,ss,integer)
удалить(string,ss,ss)
принадлеж(string,ss)
goal
оптим_маршрут(Маршрут,Длина).
clauses
оптим_маршрут(Маршрут,Длина):-
путь(Начало,_,_),!,
findall(Город,путь(Город,_,_),Города),
уник(Города,_,Количество),
маршруты(Начало,Количество,Маршрут,Длина),!.
маршруты(Начало,Количество,_,_):-
вариант(Начало,Количество,Начало,[Начало],0),fail.
маршруты(_,_,Маршрут,Длина):-
оценка(Маршрут,Длина).
вариант(Начало,0,От,Маршрут,Длина):-
участок(От,Участок,Начало),
Длина1=Длина+Участок,
not(оценка(_,_)),
assert(оценка([Начало|Маршрут],Длина1)).
вариант(Начало,0,От,Маршрут,Длина):-
участок(От,Участок,Начало),
Длина1=Длина+Участок,
оценка(_,Длина0),Длина1<Длина0,
retract(оценка(_,Длина0)),
assert(оценка([Начало|Маршрут],Длина1)).
вариант(Начало,К,От,Маршрут,Длина):-К>0,
участок(От,Участок,До),
not(принадлеж(До,Маршрут)),
Длина1=Участок+Длина, К1=К-1,
вариант(Начало,К1,До,[До|Маршрут],Длина1).
уник([Э|Х],[Э|Х2],Число):-удалить(Э,Х,Х1),!,
уник(Х1,Х2,Число1),Число = Число1+1.
уник([],[],0).
удалить(Э,[Э|Х],Х1):-!,удалить(Э,Х,Х1).
удалить(Э,[А|Х],[А|Х1]):-!,удалить(Э,Х,Х1).
удалить(_,[],[]).
участок(От,Длин,До):-путь(От,Длин,До).
участок(От,Длин,До):-путь(До,Длин,От).
принадлеж(Город,[Город|_]):-!.
принадлеж(Город,[_|Города]):-принадлеж(Город,Города).
путь("Курск",12,"Орёл").
путь("Курск",120,"Магадан").
путь("Курск",40,"Азов").
путь("Магадан",110,"Орёл").
путь("Магадан",52,"Колыма").
путь("Орёл",32,"Азов").
путь("Орёл",105,"Колыма").
путь("Азов",112,"Колыма").
Проверка:
путь("Курск",12,"Орёл").
путь("Курск",120,"Магадан").
путь("Курск",40,"Азов").
путь("Курск",90,"Колыма").
путь("Магадан",110,"Орёл").
путь("Магадан",52,"Колыма").
путь("Магадан",100,"Азов").
путь("Орёл",32,"Азов").
путь("Орёл",105,"Колыма").
путь("Азов",112,"Колыма").
Ответ:
Маршрут=["Курск","Колыма","Магадан","Азов","Орёл","Курск"], Длина=286
1 Solution |
Главная
Каталог файлов
