Окончательная позиция
Cтраница 3
В позициях из Ха выбор альтернативы случаен. Это случайное блуждание определяет вероятностное распределение на множестве окончательных позиций. [31]
Цель состоит в том, чтобы научиться управлять риском и доходностью портфеля акций за счет торговли в начале года. Количество очков, которые вы заработали, определяется по рыночной оценке вашей окончательной позиции следующим образом. [32]
ИГРА НА ГРАФЕ - обобщение позиционной игры на случай, когда граф позиций не древовидный, а произвольный. Ним - антагонистическая игра с полной информацией, в к-рой для каждой окончательной позиции указано, выигрывает или проигрывает последний ходивший игрок. В простейшем варианте игра Ним состоит в следующем: имеется несколько кучек фишек, и игроки поочередно удаляют не менее одной фишки, причем каждый раз удаляемые фишки должны быть взяты из одной кучки. Игрок, удаливший последнюю фишку, выигрывает партию. [33]
Если р е РО, то рассмотренная выше начальная позиция является одновременно и окончательной, и ходы вообще не делаются. С другой стороны, нет никаких гарантий, что в партии будет достигнута окончательная позиция. Таким образом, в общем случае бесконечные партии возможны и допустимы. [34]
Каждый раз после применения шага 1 к подмассиву еще один элемент помещается в свою окончательную позицию в сортированном массиве и появляются два несортированных массива. Когда подмас-сив содержит только один элемент, он отсортирован, поэтому этот элемент находится в своей окончательной позиции. [35]
Ввиду возможного наличия случайного хода каждая ситуация определяет век-рое распределение вероятностей на множестве партий и, следовательно, на множестве окончательных позиций. Под значением функции выигрыша игрока в любой ситуации понимается математич. [37]
Убедимся сначала в том, что относительно утверждения ( Ь) нельзя ожидать ничего большего. Для этого рассмотрим локально конечную игру с дискретными выигрышами, к которой мы добавим одну или несколько позиций, из которых нельзя достичь никакой окончательной позиции. Первоначальная игра обладает функцией решения. Если мы поставим в соответствие добавленным позициям произвольно одну и ту же окончательную позицию, то получим функцию решения расширенной игры. [38]
Применяемый ь ней процесс рлэбиенин по суше - ну шшь немногим отличаете ч от разбиения, рс: шч-зо Eta н ко го в пр01раммс 7.2, за исключен исм того, что в рассма1риьЕ1емом случае ы К ЧССТЕ раиеяяюшсго элемента используется ЧЬН ЕО 2, а не некоторый ключ из файла. Поскольку числа 2Л может н не быть & файле, то не-в ] йранткн того, что конкретный AICMCHT будет помещен в свою окончательную позицию в процессе разбкенин. Рассматриваемый алгоритм отличается от моритму, быстрой сортгнровки, поскольку рекурсивные пы ви выполняютсн JUH ключей, имеющим нц [ бит меньше. ЕШИЯСТ на эффектьнс сть алгоритма, Например, если имеет месте ныропленное разбиение ф ч - Е из Л / элементов, то произойдет рекурсивный вызов для сюдфанлЕь pajwepOM jV для ключей, имеющим рахчср па J разряд меньше, С 1сдотательно1 ншсло так и к оызовов ограничено количеством рзэрнлон в ключе. Hi самого файла в услоаияч стандартной быстрой сортнровкн может привести к возникнойсникз бесконечного рекурсивного цикла. [39]
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента ( partitioning element) произвольно выбирается элемент а [ г ] - он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. [40]
Как и в случае быстрой сортировки, структуру разделения удобно описывать в виде бинарного дерева ( аналогично тому, как она представлена на рис. 10.4): корень дерева соответствует подфайлу, подвергающемуся сортировке, а два его поддерева - двум подфай-лам, полученным в результате выполнения разделения. Мы, по крайней мере, знаем, что в результате выполнения стандартной быстрой сортировки одна из записей помещается в процессе разделения в свою окончательную позицию, следовательно, помещаем этот ключ в корневой узел; мы знаем также, что в условиях бинарной сортировки ключи попадают в свои окончательные позиции, только когда мы доходим до подфайлов размером 1, либо когда все разряды ключа исчерпаны; таким образом, мы помещаем эти ключи на нижний уровень дерева. [41]
СРВ для каждой позиции ( х, i) cl ( x) - оо независимо от того, как определяется соответствующая ( искусственная) окончательная позиция ро ( ср. [42]
Начиная слева, но со следующего после элемента 10, сравниваем каждый элемент с 37 до тех пор, пока не будет найден элемент, больший, чем 37; тогда переставляем 37 и этот элемент. Поскольку элементов, больших, чем 37, не оказалось, то при сравнении 37 с самим собой нам становится ясно, что 37 занимает свою окончательную позицию в сортированном массиве. [43]
Существуют такие типы частично отсортированных файлов, в которых каждый элемент находится достаточно близко к своей окончательной позиции. Например, некоторые игроки в карты сортируют имеющиеся у них на руках карты, сначала располагая их по масти, тем самым помещая близко к их окончательным позициям, а затем упорядочивают карты каждой масти по старшинству. [44]
Наименьший элемент безпрепятственно перемещается при всех таких операциях сравнения влево и всплывает как и пузырек в начале файла. Как и в случае сортировки методом выбора, в условиях которой индекс i перемещается по файлу слева направо, элементы слева от него находятся в своих окончательных позициях. [45]
Страницы: 1 2 3 4