просмотров: 1 091
1 Star2 Stars3 Stars4 Stars5 Stars (Оцени первым)

 Доброго всем утра! У вас есть компьютер, вы им пользуетесь дома или на работе (возможно, и там и там), и вы скорее всего думаете, что с помощью компьютера можно решить любую задачу. В общем случае это верно, но в науке существуют такие задачи, которые компьютерные специалисты считают трудными для решения на компьютере и они правы.

Специалисты из университета Корнуэлла разработали инструментарий для облегчения решения подобных задач на компьютере, смоделировав при определении верного ответа – остановиться, вернуться назад и попробовать сделать это по-другому. Такой подход в ряде случаев помогает облегчить решение трудных для компьютера заданий и уменьшить время, необходимое для этого.

 

Труднее всего компьютеру даются так называемые комбинаторные задачи, в которых есть большое количество переменных и необходимо подобрать их значения для достижения определенного результата. Примеры таких задач – составление расписания полетов, передача электроэнергии по сетям, экономические прогнозы, и самая известная – игра в шахматы.

Компьютер решает такие задачи «в лоб», перебирая все возможные варианты всех заданных переменных. Например, при анализе расписания полетов необходимо выбрать лучший маршрут для 24 самолетов на ближайшие две недели с количеством вылетов 6 в день под управлением 50 пилотов и 65 вторых пилотов. При этом рейсы совершаются в 15 аэропортов, и надо еще минимизировать общий расход горючего. Компьютер начинает строить дерево вариантов, перебирая варианты, пока не найдет оптимальный или удовлетворяющий определенным граничным условиям. Это вызвано спецификой его работы и тем, что процессор перебирает варианты гораздо быстрее человека.

Проблема в таком решении состоит в том, что в подобном «дереве вариантов» существуют как сравнительно короткие ветви, так и очень длинные, что может занять много времени даже с использованием современной техники. Если в процессе перебора программа не дойдет до такого «длинного» пути, то вычисления займут секунды или минуты, но если в процессе решения мы попадем на один из таких неудачных вариантов, то процесс может затянуться на многие дни.

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

В чем же суть усовершенствований, предложенных исследователями? Они советуют определить так называемый «надежный набор», когда часть переменных могут быть фиксированы наперед. В задаче на расчет расписания полетов, состоящей из тысяч переменных, фиксирование 12 переменных значительно упрощает проблему. Большинство планирования полетов, даже в современное время, производится вручную, когда определенные рейсы назначаются на заранее определенные моменты времени, а остальные «подгоняются» под них впоследствии.

Люди гораздо видят картину в целом и могут определить приоритеты в решении задачи. Компьютерные программы вычисляют все возможные ходы на несколько шагов вперед, а опытный гроссмейстер анализирует всего два-три возможных сценария игры, игнорируя остальные. Возможно, использование алгоритмов оптимизации, предложенных учеными, поможет создать более продвинутые программы, которые облегчат людям жизнь в самое ближайшее время.

 

Статьи на тему:

Добавить комментарий

Ваш адрес email не будет опубликован.