Нерешаемые компьютерные проблемы

1 Star2 Stars3 Stars4 Stars5 Stars (Оцени первым)

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

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

 

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

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

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

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

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

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

 

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

  • Люди одинаково склонны к альтруизму и эгоизму
    Опыт, проведенный группой исследователей, показал, что в обществе в равной степени распространяются как альтруистические чувства, так и эгоизм, — сообщает The Wird по материалам научного ...
Вы можете оставить комментарий, или ссылку на Ваш сайт.

Оставить комментарий

Вы должны быть авторизованы, чтобы разместить комментарий.

Рейтинг блогов Рейтинг блогов Rambler's Top100 free counters

Large Visitor Map