Вариант реализации алгоритма «Муравей Лэнгтона»
Invite pending
Хорошо известен алгоритм «Муравей Лэнгтона» — так называемая двумерная машина Тьюринга.
Правила его работы просты: имеется поле, разбитое на клетки, исполнитель — муравей, двигающийся на одну клетку в одном из четырех направлений и закрашивающий текущую клетку либо в черный, либо в белый цвет.
В этом случае алфавит состояний: {вперед, вправо, вниз, влево},
внешний алфавит: {белый, черный}.
Исходя из этого довольно простого набора правил муравей вырисовывает на поле замысловатый рисунок.
Справа представлен вид окна программы после примерно 10 000 итераций.
Удобным инструментом для визуализации данного алгоритма можно считать офисное приложение MS Excel, в состав которого, как известно, входит интерпретируемый язык VBA. Предлагается небольшая программа для исследования данного алгоритма для версии языка VBA 6.0.
Листинг программы
Sub МакросМуравей()
x = Selection.Row: y = Selection.Column
s = 1
For i = 1 To 400
With Selection.Interior
Select Case s Mod 4
Case Is = 1 ' прямо
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
y = y — 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
y = y + 1
Cells(x, y).Select
End If
Case Is = 2 ' направо
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
x = x — 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
x = x + 1
Cells(x, y).Select
End If
Case Is = 3 ' вниз
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
y = y + 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
y = y — 1
Cells(x, y).Select
End If
Case Is = 0 ' налево
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
x = x + 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
x = x — 1
Cells(x, y).Select
End If
For k = 1 To 100000
k = k
Next
End Select
End With
Next
End Sub
x = Selection.Row: y = Selection.Column
s = 1
For i = 1 To 400
With Selection.Interior
Select Case s Mod 4
Case Is = 1 ' прямо
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
y = y — 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
y = y + 1
Cells(x, y).Select
End If
Case Is = 2 ' направо
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
x = x — 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
x = x + 1
Cells(x, y).Select
End If
Case Is = 3 ' вниз
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
y = y + 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
y = y — 1
Cells(x, y).Select
End If
Case Is = 0 ' налево
If .ColorIndex = 1 Then ' черный
s = s — 1
.ColorIndex = xlNone ' белый
.Pattern = xlSolid
x = x + 1
Cells(x, y).Select
Else
s = s + 1
.ColorIndex = 1
.Pattern = xlSolid
x = x — 1
Cells(x, y).Select
End If
For k = 1 To 100000
k = k
Next
End Select
End With
Next
End Sub
Как видно из рисунка, поведение муравья довольно необычно. Начальное движение муравья хаотично и, видимо, не зависит от исходного состояния поля. В дальнейшем муравей выходит на определенное направление и двигается дальше только в этом направлении. Для приведенного примера это влево-вверх. Такое свойство алгоритма получило название аттрактор. На примере муравья Лэнгтона это хорошо видно.
Однако, используемый инструмент имеет недостаток — ограниченность окна Excel. Подобную особенность можно частично обойти, например направив аттрактор в другую сторону — вправо-вниз.