qyyedВероятностное решение не принимается. Алгоритм должен гарантировать отсутствие столкновения.
Уже две страницы бреда в очевидной ситуации:

а) Если алгоритмом пользуются оба участники движения, то "при необходимости сдвинуться в правую от себя полосу" - гарантированно работающий алгоритм и ничего больше изобретать не надо

б) Если алгоритмом пользуется только один участник движения, гарантировать отсутствие столкновений невозможно. Для любого алгоритма участника А можно найти алгоритм участника Б, который таки в него врежется. Обычно такие алгоритмы ставят в ракеты ПВО

qyyedОба участника не хотят столкнуться. Но никаких правил нет.
Тогда невозможно гарантировать результат.

Помню, как-то мы с девушкой бежали на троллейбус, а навстречу шла тётка размером с диван. Я вправо - и она туда, я влево - и она перегораживает дорогу. В итоге я обошёл её финтом, благо в тот момент занимался гандболом. Вот только не сообразил, что девушка за мной так не умеет, и она в тётку таки врезалась

Akina,

я бы сказал иначе. На любой алгоритм, обеспечивающий отсутствие столкновений, найдётся другой, совпадающий в действиях в течение первых N шагов и приводящий к столкновению на N+1-м.

детерминированныйвыше это несуществование softwarer уже доказал, немного переформулирую: для любого воможного алгоритма есть его зеркальное отображение,
Я бы не стал завязываться на зеркальность, там если формально доказывать, придётся делать кучу работы, а построил бы строго опровергающий. Примерно так: для любого алгоритма А есть алгоритм А', который на первых N-1 шагах делает то же, что и алгоритм А, а на N-м шаге выдаёт противоположную команду. Соответственно, автомобиль, едущий по алгоритму А, заведомо столкнётся с автомобилем, едущем по алгоритму А'.

Можно и иначе - автомобиль, едущий по любому алгоритму, не имеет возможности различить, едет ли встречный по алгоритму А или по алгоритму А'. Соответственно, как бы он ни поступил на шаге N, с одним из двоих таких встречных он столкнётся.

д0k1. один участник делает крен в любую сторону,
Лучше сразу ручку на себя.

детерминированныйвот этой смены на противоположность не могу понять, тем более что N не определён
Попробую изложить мысль иначе. У нас есть две возможных ситуации:

а) Водитель способен мгновенно реагировать на дорожную ситуацию, а машина способна мгновенно выполнять его команды по перепрыгиванию из полосы в полосу

б) Условие а) не выполняется.

Для решения достаточно рассмотреть второй вариант. Что касается первого, то с ним всё просто: если второй даёт решение, то оно будет решением и для первого, если же не даёт - решение первого упрётся в парадокс Зенона с понятными последствиями.

Так вот, в варианте б) есть некая точка принятия решения (расстояние между автомобилями), после которой манёвр уже невозможен. Давайте сядем в один из автомобилей и оттуда будем смотреть на встречный. Встречный едет по некоему неизвестному нам алгоритму, назовём его А.

Для каждого детерминированного алгоритма А существует алгоритм А', строящийся следующим образом: вплоть до точки принятия решения он даёт те же команды, что и А. В точке принятия решения он даёт команду перестроиться, если А командует ехать прямо, и даёт команду ехать прямо, если А даёт команду перестроиться.

Мы, сидя в своём автомобиле, приезжаем в точку принятия решения. В этой точке мы никак не можем различить, едет ли встречный автомобиль по алгоритму А или по алгоритму А'. Мы не можем предсказать на основании предыдущих действий, поедет ли он прямо или перестроится. Поэтому какое бы решение мы ни приняли, оно может оказаться приводящим к столкновению. Гарантированного алгоритма не существует.

д0kВсе генераторы частот в радоэлектронике запускаются по случайности,
Случайность - неплохой алгоритм в ряде случаев, но он никогда не гарантирует успех. В поставленных же условиях он обеспечивает успех с вероятностью 50% :)

На практике - даже когда все собеседники заведомо используют один и тот же алгоритм со случайной составляющей, "договориться" иногда занимает слишком много времени (в терминах нашей аналогии - машины столкнутся раньше, чем случайным подёргиваниям удастся их развести).