Prolog максимальный цикл в графе
Формулировка задачи:
Есть такой код
Он благополучно был взять с форума, и по сути должен работать... Но не выводится максимальный вариант.
В этой строчке выводятся все варианты
При запуске goal выводится только false.... Хелп
Листинг программы
- link( 1, 2). link( 2, 3). link( 3, 4). link( 1, 4).
- link( 4, 5). link( 5, 6). link( 6, 1). link( 2, 9).
- link( 9, 8). link( 8, 7). link( 7, 6). link( 7, 5).
- goal :-
- link(VERTEX, _),
- LENGTH is 0,
- for(VERTEX, VERTEX, [VERTEX], FOR, 0, LENGTH),
- not(another_bigger(LENGTH)).%,
- %write(FOR).
- for(START, FINISH, FOR0, FOR, LENGTH0, LENGTH):-
- link(START, BETWEEN),
- not(have(BETWEEN, FOR0, FINISH)),
- LENGTH2 is LENGTH0 + 1,
- %writeln(FOR0+' = '+LENGTH2),
- for(BETWEEN, FINISH, [BETWEEN|FOR0], FOR, LENGTH2, LENGTH).
- another_bigger(LENGTH):-
- link(VERTEX, _),
- for(VERTEX, VERTEX, [VERTEX], _, 0, LENGTH1),
- LENGTH1 > LENGTH.
- have(VERTEX, _, VERTEX) :- !, fail.
- have(VERTEX, [VERTEX|_], _) :- !.
- have(VERTEX, [_|FOR], FINISH) :- have(VERTEX, FOR, FINISH).
Листинг программы
- writeln(FOR0+' = '+LENGTH2),
Решение задачи: «Prolog максимальный цикл в графе»
textual
Листинг программы
- link( 1, 2). link( 2, 3). link( 3, 4). link( 1, 4).
- link( 4, 5). link( 5, 6). link( 6, 1). link( 2, 9).
- link( 9, 8). link( 8, 7). link( 7, 6). link( 7, 5).
- goal :-
- link(Finish, Start),
- for(Start, Finish, [Finish], FOR, 0, LENGTH),
- %writeln(FOR+' = '+LENGTH),
- not(another_bigger(LENGTH)),
- write(FOR).
- for(FINISH, FINISH, FOR, FOR, LENGTH, LENGTH):- !.
- for(START, FINISH, FOR0, FOR, LENGTH0, LENGTH):-
- link(START, BETWEEN),
- not(have(BETWEEN, FOR0, FINISH)),
- LENGTH2 is LENGTH0 + 1,
- %writeln(FOR0+' = '+LENGTH2),
- for(BETWEEN, FINISH, [BETWEEN|FOR0], FOR, LENGTH2, LENGTH).
- another_bigger(LENGTH):-
- link(Finish, Start),
- for(Start, Finish, [Finish], _, 0, LENGTH1),
- LENGTH1 > LENGTH.
- have(VERTEX, _, VERTEX) :- !, fail.
- have(VERTEX, [VERTEX|_], _) :- !.
- have(VERTEX, [_|FOR], FINISH) :- have(VERTEX, FOR, FINISH).
Объяснение кода листинга программы
Код, представленный в списке, является реализацией алгоритма поиска самого длинного пути в графе с использованием языка программирования Prolog. Вот список, описывающий каждый элемент кода:
link( 1, 2). link( 2, 3). link( 3, 4). link( 1, 4).
- Это определение графа, представленное в виде фактов Prolog. Здесь создаются связи между вершинами графа. Например, первая строка говорит о том, что существует связь между вершинами 1 и 2.goal :-
- Это определение цели или задачи, которую должен выполнить программист. В данном случае цель состоит в нахождении самого длинного пути в графе.link(Finish, Start),
- Это часть условия задачи, которая говорит о том, что вершиныFinish
иStart
должны быть связаны.for(Start, Finish, [Finish], FOR, 0, LENGTH),
- Это часть условия задачи, которая говорит о том, что переменнаяFOR
должна быть равнаFinish
, а переменнаяLENGTH
должна быть равна 0. Здесь также инициируется циклfor
.%writeln(FOR+' = '+LENGTH),
- Это часть кода, которая используется для отладки и вывода информации о состоянии выполнения программы. Здесь в консоль выводится значение переменныхFOR
иLENGTH
.not(another_bigger(LENGTH)),
- Это часть условия задачи, которая говорит о том, что функцияanother_bigger(LENGTH)
должна возвращать ложь (false), если существует путь большей длины.write(FOR).
- Это часть кода, которая используется для вывода результата выполнения программы. Здесь в консоль выводится значение переменнойFOR
.for(FINISH, FINISH, [FINISH], FOR, LENGTH, LENGTH):- !.
- Это часть циклаfor
, которая говорит о том, что еслиFINISH
равноFOR
, то цикл прерывается.for(START, FINISH, [START|FOR0], FOR, LENGTH0, LENGTH):-
- Это часть циклаfor
, которая говорит о том, что еслиSTART
равноFOR
, то переменныеFOR
иLENGTH
обновляются, и в цикле продолжаются поиски.another_bigger(LENGTH):-
- Это определение функцииanother_bigger(LENGTH)
, которая проверяет, существует ли путь большей длины.have(VERTEX, _, VERTEX) :- !, fail.
- Это часть кода, которая используется для проверки наличия вершины в списке путей. Если вершина отсутствует, то выполняется функцияfail
, что приводит к прерыванию выполнения программы.have(VERTEX, [VERTEX|_], _) :- !.
- Это часть кода, которая используется для проверки наличия вершины в списке путей. Если вершина присутствует в списке, то выполнение кода продолжается.have(VERTEX, [_|FOR], FINISH) :- have(VERTEX, FOR, FINISH).
- Это часть кода, которая используется для проверки наличия вершины в списке путей. Если вершина присутствует в спискеFOR
, то выполняется рекурсивный вызов функцииhave
с новыми значениями переменных.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д