agent2.htm
Agent2 (вторая серия)
Пример с агентами оказался даже лучше, чем я ожидал, потому что у него оказалось продолжение.
Первый пример работал очень долго. Для 5 агентов где-то одна минута. Для 7 агентов я не дождался конца. Пробовал перейти к другому варианту задания перестановок в виде циклов. Там при дополнительных предположениях можно было убрать одну переменную из семи. Тогда время суперкомпиляции составило 1 час 10 минут. Для 8 агентов я ждал 4 часа и не дождался. Этот другой вариант был сложнее для изложения, и я не стал о нем даже упоминать.
Перестановка - это отображение конечного множества на себя. Такое отображение можно задавать табличкой (что во что переходит). Но отображение, в конце-концов - это функция. Так давайте перестановку и задавать функцией рефала.
Тогда программа выглядит так (функции, видно по их виду, я не писал сам, а получал суперкомпилятором из программы из первой серии). (смешной момент - имя F7 придумал суперкомпилятор, причем два раза, второй раз я исправил на F1).
* InputFormat: <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 >
F7 {
s.1 s.2 s.3 s.4 s.5 s.6 s.7 "001" e.8
= s.1 <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 > ;
s.1 s.2 s.3 s.4 s.5 s.6 s.7 "002" e.8
= s.2 <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 > ;
s.1 s.2 s.3 s.4 s.5 s.6 s.7 "003" e.8
= s.3 <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 > ;
s.1 s.2 s.3 s.4 s.5 s.6 s.7 "004" e.8
= s.4 <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 > ;
s.1 s.2 s.3 s.4 s.5 s.6 s.7 "005" e.8
= s.5 <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 > ;
s.1 s.2 s.3 s.4 s.5 s.6 s.7 "006" e.8
= s.6 <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 > ;
s.1 s.2 s.3 s.4 s.5 s.6 s.7 "007" e.8
= s.7 <F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7 e.8 > ;
s.1 s.2 s.3 s.4 s.5 s.6 s.7 = ;
}
F1 {
"001" e.1 = "002" <F1 e.1 > ;
"002" e.1 = "003" <F1 e.1 > ;
"003" e.1 = "004" <F1 e.1 > ;
"004" e.1 = "005" <F1 e.1 > ;
"005" e.1 = "006" <F1 e.1 > ;
"006" e.1 = "007" <F1 e.1 > ;
"007" e.1 = "001" <F1 e.1 > ;
= ;
}
Eq {
(s.a e.1) (s.a e.2) = <Eq (e.1) (e.2)>;
( ) ( ) = T;
* (e.1) (e.2) = F;
}
|
Теперь составляю MST-схему
<Eq
(
<F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7
<F7 s.1 s.2 s.3 s.4 s.5 s.6 s.7
"001" "002" "003" "004" "005" "006" "007" > >
)
(
<F1 "001" "002" "003" "004" "005" "006" "007" >
)
>;
|
F7 - неизвестная перестановка, F1 - известная циклическая.
Суперкомпилирую и через 11 секунд получаю нужный ответ
/*
$ENTRY Go {
= <Prout <Agentx0071 s.1 s.2 s.3 s.4 s.5 s.6 s.7 >> ;
}
*/
* InputFormat: <Agentx0071 s.1 s.2 s.3 s.4 s.5 s.6 s.7 >
Agentx0071 {
"005" "006" "007" "001" "002" "003" "004" = T ;
}
|
Повторяю все что надо для 8 агентов и через 28 секунд получаю сообщение, что решений нет.
В чем тут дело.Два возможных ответа, которые могут быть, таковы.
(1). В первой серии суперкомпилятору приходилось все интерпретировать, обрабатывать более сложную программу. Здесь же только две функции, и поэтому все происходит быстрее. Вызывает удивление, что настолько быстрее.
(2). Может быть, теперь суперкомпилятор производит не просто перебор всех случаев, а какой-то анализ. В пользу этого говорит отношение времен 28 / 11 - вовсе не 8 раз. Не понятно, сколько случаев перебирает суперкомпилятор.
Для определения количество случаев, которые перебирает суперкомпилятор убрал * в функции Eq - теперь предложения с ложью строятся (в первой серии я пробовал это делать - получается невообразимая программа).
Время суперкомпиляции чуть-чуть увеличивается. Для 7 агентов происходит перебор примерно 200 случаев (в одном случае T, в остальных - F), для 8 - примерно 500 случаев (везде F). Так что суперкомпилятор не просто перебирает, а как-то проявляет свой интеллект.
Приведу остаточную программу для 5 агентов (для обозримости)
* InputFormat: <Agentx1 s.1 s.2 s.3 s.4 s.5 >
Agentx1 {
"001" s.2 s.3 s.4 s.5 = F ;
"002" "002" s.3 s.4 s.5 = F ;
"002" s.2 s.3 s.4 s.5 = F ;
"003" "001" "002" s.4 s.5 = F ;
"003" "002" "002" s.4 s.5 = F ;
"003" "003" "002" s.4 s.5 = F ;
"003" "004" "002" "003" s.5 = F ;
"003" "004" "002" s.4 s.5 = F ;
"003" "005" "002" s.4 "003" = F ;
"003" "005" "002" s.4 s.5 = F ;
"003" s.2 s.3 s.4 s.5 = F ;
"004" "001" s.3 "002" s.5 = F ;
"004" "002" s.3 "002" s.5 = F ;
"004" "003" "003" "002" s.5 = F ;
"004" "003" s.3 "002" s.5 = F ;
"004" "004" s.3 "002" s.5 = F ;
"004" "005" "001" "002" "003" = T ;
"004" "005" "002" "002" "003" = F ;
"004" "005" "003" "002" "003" = F ;
"004" "005" "004" "002" "003" = F ;
"004" "005" "005" "002" "003" = F ;
"004" "005" s.3 "002" s.5 = F ;
"004" s.2 s.3 s.4 s.5 = F ;
"005" "001" s.3 s.4 "002" = F ;
"005" "002" s.3 s.4 "002" = F ;
"005" "003" "003" s.4 "002" = F ;
"005" "003" s.3 s.4 "002" = F ;
"005" "004" "001" "003" "002" = F ;
"005" "004" "002" "003" "002" = F ;
"005" "004" "003" "003" "002" = F ;
"005" "004" "004" "003" "002" = F ;
"005" "004" "005" "003" "002" = F ;
"005" "004" s.3 s.4 "002" = F ;
"005" "005" s.3 s.4 "002" = F ;
"005" s.2 s.3 s.4 s.5 = F ;
}
|
Перебор 35 случаев.
Несколько раз в переписке упоминалось об использовании примера на презентациях. Способ подачи этого примера будет зависеть от публики. Можно только говорить о второй серии. Можно про обе серии сразу.
Советую учитывать тот психологический момент, что эта задача об агентах не является простой (просто как задача). Мне самому пришлось напрячься и подумать минут 10. Попробуйте придумать решение, которое поймет младший школьник (младший - это не первый класс, а 5-6). Поэтому, при наличии времени имеет прямой смысл дать подумать минут 5-10 слушателям.
Мой способ изложения больше напоминает показ фокуса. Целью прошлого и этого писем было только рассказать об экспериментах.