| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Prolog] Найти самую длинную цепь в графе |
| Автор: Pashot 24.3.2008, 20:22 |
| Задание. Найти самую длинную цепь в неореентированом связном графе используя стратегию поиска в ширину. Вот прога которая ищет путь от начальной вершины к конечной используя поиск в ширину, помогите изменить прогу чтоб она искала самую длинную цепь в графе. Пожалуйста main(Decision):- initial_state(FirstV), bfs([s(FirstV,[])],[],[],Decision). /* + Current Frontier, Next Frontier, + Opened States List, - List of Moves from Current State to Final State */ bfs([s(State,Path)|_],_,_,[State|Path]):- final_state(State). bfs([s(State,Path)|Fr],NextFr,History,EndPath):- findall(M,move(State,M),Ms), next_fr_add(Ms,NextFr,NextFr1,History,State,Path), history_add(State,History,History1), bfs(Fr,NextFr1,History1,EndPath). bfs([],[],_,_):- !, fail. bfs([],NextFr,History,EndPath):- bfs(NextFr,[],History,EndPath). /* + Moves List from Current State, + Next Frontier, - Added Next Frontier, + Opened States List, + Current State, + Path from Initial States to Current State */ next_fr_add([Move|Ms],NextFr,[s(State1,[State|Path])|NextFr1], History,State,Path):- update(State,Move,State1), not_member(History,State1), next_fr_add(Ms,NextFr,NextFr1,History,State,Path). next_fr_add([],NextFr,NextFr,_,_,_). /* + Current State, + Opened States List, - Added Opened States List */ history_add(State,History,History):- final_state(State), !. history_add(State,History,[State|History]). /* + List, + Member of List */ not_member([X|_],X):- !, fail. not_member([_|Xs],X):- not_member(Xs,X). not_member([],_). % Data Base initial_state(2). final_state(6). update(_,B,B). move(1,0). move(1,2). move(1,3). move(2,a). move(2,5). move(2,6). move(8,10). move(8,a). move(6,8). move(3,33). move(33,a). move(33,7). move(6,a). |