В ширину в прологе
Попробуйте:
CSS="CSS"
COMMENT="COMMENT"
EXCEPTION="EXCEPTION"
FILTER="FILTER"
def is_comment(line):
return line[0]=="!"
def is_css_rule(line):
return '##' in line
def is_exception_rule(line):
return '@' in line
def is_filter_rule(line):
return not is_comment(line) and not is_css_rule(line)
def get_rule_type(line):
if is_comment(line):
return COMMENT
elif is_css_rule(line):
return CSS
elif is_exception_rule(line):
return EXCEPTION
else:
return FILTER
with open("abc.txt") as f:
for line in f:
print('{:12s} {!r}'.format(get_rule_type(line), line))
Примечание: здесь используется Python 3. Кроме того, мы не используем регулярные выражения, поэтому нет необходимости включать пакет re. [ 113]
3 ответа
Преимущество ширины в том, что вы найдете все решения. С первой глубиной вы можете застрять в бесконечной ветви.
Недостатком является то, что первая ширина использует много памяти, поэтому она обычно не используется для выполнения.
Если вы захотите ее использовать, вы нужно реализовать это явно с какой-то очередью.
Редактировать: Если вы хотите использовать преимущества поиска в ширину без использования большого количества памяти, вы можете использовать итеративное углубление. Это поиск в глубину с ограничением по глубине, который вы последовательно увеличиваете. Это приводит к некоторым дублирующим вычислениям, но если ваше пространство поиска не имеет длинных линейных растяжений без ветвления, тогда это дублирование невелико.
Есть кое-что, что я узнал как « поиск по повестке дня ». Обходя дерево (данных, отношений, правил и т. Д.), Вы поддерживаете «повестку дня» (список) того, что делать дальше. Когда вы входите в узел, вы помещаете его дочерние элементы в повестку дня, а затем переходите к первому элементу повестки дня, который вы открываете. Таким образом, если вы поместите новые пункты в конец повестки дня, вы получите широту охвата. Если вы поставите их перед повесткой дня, вы получите глубину в первую очередь.
Это легко реализовать с помощью Prolog.
РЕДАКТИРОВАТЬ: Я мог бы также дать здесь подсказку по реализации. Это очень простая реализация алгоритма поиска по повестке дня.
agenda_search([N|T],Mode):-
doWithNode(N), % do whatever you do the searching for
getNodeChildren(N,C),
(Mode=bf -> % bf or df (depth-first)
append(T,C,A);
append(C,T,A)),
agenda_search(A,Mode).
Он основан на внешних предикатах doWithNode , которые обозначают действие, которое вы хотите выполнить с каждым узлом (например, сравнить данные узла с поисковым запросом, сериализовать содержимое узла, asf.). И getNodeChildren , который привяжет список дочерних узлов данного узла к C (т.е. этот предикат действительно знает древовидную структуру и способы поиска дочерних узлов). Конечно, предикату doWithNode могут потребоваться дополнительные параметры для выполнения своей работы, которые также будут отображаться в списке аргументов scheme_search .
Вы можете вызвать его следующим образом:
agenda_search([RootNode], bf) % for breadth-first search
и
agenda_search([RootNode], df) % for depth-first search
Я также нашел небольшое объяснение поиска по повестке дня на этой веб-странице . Приятная вещь с поиском по повестке дня заключается в том, что вы можете легко переключаться между двумя вариантами df и bf и поиграть с результатами. Алгоритм довольно хорош с точки зрения памяти, так как повестка дня, узлы, которые еще предстоит изучить,
Код для повестки дня_поиск должен работать нормально. Для эффективности вы можете пожелать рассмотреть возможность использования другой структуры данных; действительно, в режиме «в ширину» весь список узлов (T) будет проходить с помощью append (T, C, A). Вы можете, например, использовать модуль библиотеки (очередей) из SICStus. {{1 }} Тогда поиск в ширину будет выглядеть следующим образом (параметризованный предикатами start / 1, предикатом-преемником s / 2 и предикатом цели goal / 1). Обратите внимание, я также добавил проверку петель.
bfs(Res) :- start(Start), empty_queue(EQ),
queue_append(EQ,[e(Start,[])],Q1),
bfs1(Q1,Res).
bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue),
bfs2(Next,Path,NQ,Res).
bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res).
bfs2(H,Path,NQ,Res) :-
findall(e(Succ,[H|Path]),
(s(H,Succ),\+ member(Succ,Path)),AllSuccs),
queue_append(NQ,AllSuccs,NewQueue),
bfs1(NewQueue,Res).
(Вы также можете попробовать заменить / дополнить компонент Path лучшей структурой данных; например, AVL-деревьями.) Пример проблемы, которую необходимо решить:
start(env(0,0)). s(env(X,Y),env(X1,Y)) :- X1 is X+1. s(env(X,Y),env(X,Y1)) :- Y1 is Y+1. goal(env(3,3)).
Вы также можете заменить очередь на очередь приоритетов и вычислить приоритет с помощью эвристической функции. Затем вы получите поиск A * (который может эмулировать поиск в глубину, в ширину, сначала наилучшее, ...). Книга Братко (Логическое программирование для искусственного интеллекта) должна быть хорошим источником для чтения этого материала. .