Лаба по искусственному интеллекту

← →
pupus (2004-07-07 08:57) [0]

Привет всем!
Помогите с лабой по Искусственному интеллекту, препод ниче не обьясняет...
Задание такое:
Разработка синтаксического анализатора abaababababbababaaaba -> S. Правила: ab->S, aS->S, Sb->S, SS->S.
Сделал я ему прогу, там функция одна маленькая, проще простого, так он(препод) говорит, что это не правильно, сделай-ка ты мне поиском в ширину
Никак не могу понять, как ? Поиск в ширину - это к графу надо привезти, матрица смежности и т.д. Но как это к графу привезти ума не приложу.....

← →
Fay © (2004-07-07 09:03) [1]

Сначала обходишь все вершины смежные начальной, потом все смежне им, и т.д.

← →
pupus (2004-07-07 09:17) [2]

Что такое поиск по графу то я знаю, а вот как Строку типа ababbbababa графом представить?

← →
Fay © (2004-07-07 09:19) [3]

Покажи старую функцию

← →
BoxTer (2004-07-07 09:21) [4]

у чела вопрос стоит - как к графу привести???

← →
Ega23 © (2004-07-07 09:23) [5]

А при чём здесь ИИ? Это же обычная формальная грамматика с предикатными функциями.

← →
BoxTer (2004-07-07 09:24) [6]

> Сначала обходишь все вершины смежные начальной, потом все
> смежне им, и т.д.

2FAY - а это, случайно, не поиск в глубину ;-)

← →
Fay © (2004-07-07 09:31) [7]

Как запомнил, так и написал. 8) На самом деле незвание роли не играет. Назови хоть "к е#еи матери". 8)

У меня препод, помню, охренел, когда я методом "северо-западного угла" пошёл с "юго-западного". А какая разница?! 8)

← →
pupus (2004-07-07 10:35) [8]

function ReplaceSub(str, sub1, sub2: string): string;
var
aPos: Integer;
rslt: string;
begin
aPos := Pos(sub1, str);
rslt := "";
while (aPos <> 0) do
begin
rslt := rslt + Copy(str, 1, aPos - 1) + sub2;
Delete(str, 1, aPos + Length(sub1) - 1);
aPos := Pos(sub1, str);
end;
Result := rslt + str;
form1.label1.caption:=result;
end;

ReplaceSub(label1.caption,"Sb","S");
ReplaceSub(label1.caption,"aS","S");
ReplaceSub(label1.caption,"SS","S");

Вот так во было сделано, говорит это ты сам руками перебираешь, а ни хе..а не поиск ни в ширь ни в глубь

А что она делает?! Мне кажется ничего.

> BoxTer (07.07.04 09:24) [6]
>
> > Сначала обходишь все вершины смежные начальной, потом
> все
> > смежне им, и т.д.
>
> 2FAY - а это, случайно, не поиск в глубину ;-)

Неа. В глубину - это когда идешь в глубину, доходишь до дна, потом выныриваешь на один уровень, потом ныряешь в другом направлении (если его нету, снова выныриваешь)...

> pupus (07.07.04 08:57)
> Привет всем!
> Помогите с лабой по Искусственному интеллекту, препод ниче
> не обьясняет...
> Задание такое:
> Разработка синтаксического анализатора abaababababbababaaaba
> -> S. Правила: ab->S, aS->S, Sb->S, SS->S.

Имхо если поиск в ширину, то так:
1 если исходная строка = S то выход
2 проходишь строку посимвольно от первого символа до предпоследнего
3 берешь текущий символ + следующий - получаешь пару
4 ищешь и применяешь одно из правил замены (заменяешь напр. ab на S - в примере это будет первым - строка станет Saababababbababaaaba)
5 если прошли строку до конца, то идем на 1

---
при применении правил замены строишь дерево разбора (если надо); правда при обходе в ширину это вроде сложнее; так что лучше делай в глубину; а еще лучше и так и так;

← →
pupus (2004-07-08 12:52) [12]

> Igorek

Спасибо за объяснение, прога вроде написана, попробую сдать, но граф так и не построил

Лаба по искусственному интеллекту Найти похожие ветки